課程概述 |
1. PRELIMINARIES: Introduction. Asymptotic Notations, Algorithm Analysis
2. ABSTRACT DATA TYPES: Stacks. Queues. Lists. List operations. List representations. List traversals. Doubly linked lists.
3. TREES: Tree operations. Tree representations. Tree traversals. Threaded trees. Binary trees. AVL trees. 2-3 trees. B-trees. Red-black trees. Binomial trees. Splay trees, AA-trees and more.
4. HASHING: Chaining. Open addressing. Collision handling.
5. PRIORITY QUEUES: Binary heaps. Binomial heaps. Fibonacci heaps. Leftist heaps, Skew heaps, Min-max heaps, Pairing heaps
6. AMORTIZED ANALYSIS
7. SORTING: Insertion sort. Selection sort. Quicksort. Heapsort. Mergesort. Shellsort. Lower bound of sorting.
8. DISJOINT SETS: Set operations. Set representations. Union-find. Path compression.
9. GRAPHS: Graph operations. Graph representations. Basic graph algorithms. Algorithm design techniques
10. ADVANCED DATA STRUCTURES: Tries, Skip lists Treaps, Top-down splay trees |