週次 |
日期 |
單元主題 |
第1週 |
2/24 |
Introduction
1. What are algorithms?
2. Asymptotic Notations (Chapter 3)
3. Examples:
- Bubble Sort (Problem 2-2)
- Insertion Sort (Section 2.1) |
第2週 |
3/3 |
Divide and Conquer (Chapter 4)
1. MergeSort (Section 2.3.1)
2. Substitution Method (Section 4.3)
3. The recursion tree method (Section 4.4.)
4. The master method (Section 4.5)
5. Strassen's algorithm (Section 4.1-4.2)
|
第3週 |
3/10 |
Sorting Algorithms
1. Heap and HeapSort (Chapter 6)
2. Counting Sort (Section 8.2)
3. Radix Sort (Section 8.3)
4. Bucket Sort (Section 8.4) |
第4週 |
3/17 |
Sorting Algorithm (continue)
5. QuickSort (Chapter 7)
6. Lower Bounds for Sorting (Section 8.1) |
第5週 |
3/24 |
Selection
1. Quick Selection (Section 9.1)
2. Median of Medians (Section 9.2)
Dynamic Programming
1. Fibonacci Numbers
2. Longest Common Subsequence (Section 14.4) |
第6週 |
3/31 |
Dynamic Programming
3. Matrix Chain Multiplication (Section 14.2)
Greedy Algorithms
1. Activity Selection (Section 15.1)
2. Hoffman Code (Section 15.2) |
第7週 |
4/7 |
Greedy Algorithms
2. Hoffman Code ( continued)
Brushup for the Midterm Exam |
第8週 |
4/14 |
Midterm Exam |
第9週 |
4/21 |
Elementary Graph Algorithms (Chapter 20)
1. Basic Definitions
2. Depth-First Search
3. Breadth-First Search |
第10週 |
4/28 |
Elementary Graph Algorithms (Chapter 20, continued)
4. Topological Sort
5. Strongly Connected Components
Minimum Spanning Trees (Chapter 21)
1. Key Properties
2. Prim Algorithm
|
第11週 |
5/5 |
Minimum Spanning Trees (Chapter 21, continued)
3. Kruskal Algorithms
Single-Source Shortest Paths (Chapter 22)
1. Basic Properties
2. Bellman-Ford Algorithm
3. Directed Acyclic Graph
4. Dijkstra Algorithm
|