指定用書
1.Introuction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
2.Fundamentals of Data Structures in C＋＋
Ellis Horowitz, Sartaj Sahni, Dinesh Mehta
參考資料
Algorithms in C＋＋; Robert Sedgewick
----------------------课程目录------------------------------
课程大纲：
Week 0
Overview
课程介绍
Week 1
Getting Started; Heap
Sorting的方法&分析
Sorting的分析
Growth of Function
Insertion Sort上机
Exercises
Heap-1
Heap-2
Exercises
Week 2
Sorting Lower Bound
Lower Bound on Comparison Sorts- 1
Lower Bound on Comparison Sorts- 2
Exercises
Basic Data Structures I (List, Queue, Stack)
Pointers in C
Basic Data StructureⅠ- 1
Basic Data StructureⅠ- 2
Josephus上机
Balanced括号上机
List上机_insert
List上机_delete
Exercises
Week 3
Basic Data Structures II (Tree, Graph)
Tree and Graph
Exercises
Graph and Tree Traversals I (BFS, DFS)
Breadth First Search
Depth First Search
Depth First Search分析
Exercises
Week 4
Graph and Tree Traversals II (Tree Traversals, Expression Tree )
Tree Traversal
Expreesion Tree&Postfix Notation of an Expression
Infix-Postfix Coversion
Exercises
Graph and Tree Traversals III (Topological Sort)
Topological Sort
Topological 证明
Two IQ questions
Exercises
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
Exercises
Week 6
Searching Set Data II (AVL Tree)
AVL Tree
AVL Tree- Rotation
AVL Tree- Insertion的情形
AVL Tree- Insertion实作Case2.2
AVL Tree- Insertion实作Case2.3
AVL Tree Insert 补充& Delete
Augmenting Data Structure
Exercises
Week 7
Searching Set Data III (B-Tree)
B-tree EM Model
B-tree insert
B-tree delete
Exercises
Week 8
Hashing (Chaining, Open Addressing)
Hashing
Common Hash Function
Exercises
Suffix Tree and Suffix Array
Indexing Strings& Suffix Array
Exercises
