層級: | 課程資料 |
媒體: | 影音 講義 |
2022-11-23-2030-12-30
國立清華大學 資訊工程學系 韓永楷
關鍵字: Introduction to Data Structure Sorting Lower Bound Searching Set Data Hashing Suffix Tree and Suffix Array
「資料結構」是學習以聰明的方法去儲存資料,使得我們在有需要的時候能夠快速有效地把資料擷取....
課程說明
Course Description
「資料結構」是學習以聰明的方法去儲存資料,使得我們在有需要的時候能夠快速有效地把資料擷取。例如我們希望把學生某一科的考試成績整理,使得我們能隨時查詢任何學生的排名。為了節省查詢的時間,我們或許會把學生們的成績從高至低排好,而不會以隨意的順序排列。〈對此問題,其實還有一個更好的方法呢!〉
Week 1 | Getting Started、Heap |
● Introduction ● Sorting 的方法 & 分析 ● Exercise - Insertion Sort ● Sorting 的分析 ● Exercise - Merge Sort ● Growth of Functions ● Exercise - Growth of Functions ● Insertion Sort 上機 ● Heap-1 ● Exercise - Heap I ● Heap-2 ● Exercise - Heap II | |
Week 2 | Sorting Lower Bound、Basic Data Structures I (List, Queue, Stack) |
● Lower Bound on Comparison Sorts - 1 ● Exercise - Lower Bound on Comparison Sorts I ● Lower Bound on Comparison Sorts - 2 ● Exercise - Lower Bound on Comparison Sorts II ● Pointers in C ● Basic Data Structure Ⅰ - 1 ● Basic Data Structure Ⅰ - 2 ● Exercise - Basic Data Structure I ● Josephus 上機 ● Exercise - Josephus Problem ● Balanced 括號上機 ● Exercise - Balanced Parentheses ● List 上機_insert ● List 上機_delete | |
Week 3 | Basic Data Structures II (Tree, Graph)、Graph and Tree Traversals I |
(BFS, DFS) | |
● Tree and Graph ● Exercise - Tree ● Breadth First Search ● Exercise - Breadth First Search ● Depth First Search ● Exercise - Depth First Search ● Depth First Search 分析 | |
Week 4 | Graph and Tree Traversals II (Tree Traversals, Expression Tree )、 |
| Graph and Tree Traversals III (Topological Sort) |
● Tree Traversal ● Exercise - Tree Traversal ● Expression Tree & Postfix Notation of an Expression ● Infix-Postfix Coversion ● Exercise - Expression ● Topological Sort ● Topological Sort 證明 ● Exercise - Topological Sort ● Two IQ Questions ● Exercise - Josephus Problem Revisited | |
Week 5 | Searching Set Data I (Binary Search Tree) |
● Binary Search Tree ● Binary Search Tree 實作 (Min / Max) ● Binary Search Tree 實作 (Search / Predecessor) ● Binary Search Tree 實作 (Insert / Delete) ● Binary Search Tree 實作 (Delete) - Case 1 & 2 ● Binary Search Tree 實作 (Delete) - Case 3 ● BST上機_insert ● BST上機_delete_1 ● BST上機_delete_2 ● BST上機 - 3 ● Exercise - Binary Search Tree | |
Week 6 | Searching Set Data II (AVL Tree) |
● AVL Tree ● AVL Tree - Rotation ● AVL Tree - Insertion 的情形 ● AVL Tree - Insertion實作 Case 2.2 ● AVL Tree - Insertion 實作 Case 2.3 ● AVL Tree Insert 補充 & Delete ● Augmenting Data Structure ● Exercise - AVL Tree | |
Week 7 | Searching Set Data III (B-Tree) |
● B-tree EM Model ● B-tree insert ● B-tree delete ● Exercise - B Tree I ● Exercise - B Tree II | |
Week 8 | Hashing (Chaining, Open Addressing)、Suffix Tree and Suffix Array |
● Hashing ● Common Hash Function ● Exercise - Hashing ● Indexing Strings & Suffix Array ● Exercise - Suffix Array | |
♠ | Introuction to Algorithms |
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein | |
♠ | Fundamentals of Data Structures in C++ |
Ellis Horowitz, Sartaj Sahni, Dinesh Mehta |
♠ | Algorithms in C++Robert Sedgewick |
♠ | C/C++ Programming |