| Week | Dates | Day | Topics | Readings | Homework |
|---|---|---|---|---|---|
| 1 | Nov. 28 - Dec. 2 | 1 | Course introduction | 1 | |
| 2 | Fundamentals of the analysis of complexity
Analysis of iterative algorithms | 2.1-2.3 | 23:59: Assignment 0 | ||
| 3 | Analysis of recursive algorithms | 2.4-2.5 | 23:59: Assignment 1 | ||
| 4 | Master theorem
Recurrence trees Practice of Analysis of algorithms | None | |||
| 2 | Dec. 5-9 | 5 | Brute-force solutions
Practice precise analysis of algorithms | 3.1-3.3 | 23:59: Assignment 2 |
| 6 | Brute force: exhaustive search | 3.4 | |||
| 7 | Graph search
DFS, BFS Topological sort | 3.5, 4.2 | 23:59 Assignment 3 | ||
| 8 | Decrease and conquer
Constant decrease Insertion sort | 4.0, 4.1 | |||
| 3 | Dec. 12-16 | 9 | Variable decrease
Insertion sort | 4.4, 4.5 | 23:59: Assignment 4 |
| 10 | Mergesort
Quicksort | 5.1-5.2 | |||
| 11 | Divide and conquer
Closest-pair problem | 5.4-5.5 | 7-8:30pm: Exam 1 | ||
| 12 | QuickHull | 5.5 | |||
| 4a | Dec. 19-20 | 13 | Transform-and-Conquer
Presorting Horner’s Rule | 6.1, 6.5 | 23:59: Assignment 5 |
| 14 | No class, to compensate for evening exam 1 | None | |||
| 4b | Jan. 5-6 | 15 | Problem reduction
Linear Programming | 6.6 | 23:59: Assignment 6 |
| 16 | Gaussian elimination
LU Decomposition | 6.2 | |||
| 5 | Jan. 9-13 | 17 | Space and Time Trade-Offs
Sorting by Counting String Matching: Horspool | 7.1-7.2 | 23:59: Assignment 7 |
| 18 | String Matching: Boyer-Moore
Hashing | 7.2-7.3 | |||
| 19 | B-trees | 7.4 | 23:59: Assignment 8 | ||
| 20 | Introduction to Dynamic Programming | 8.1 | |||
| 6 | Jan. 16-20 | 21 | DP for the Knapsack Problem | 8.2 | 23:59: Assignment 9 |
| 22 | Dynamic programming practice | ||||
| 23 | Warshall's Algorithm
Floyd's Algorithm | 8.4 | 7-8:30pm: Exam 2 | ||
| 24 | Greedy Technique | 9.0 | |||
| 7 | Jan. 23-27 | 25 | Minimum Spanning Tree
Pell's algorithm Kruskal's algorithm | 9.1-9.2 | 23:59: Assignment 10 |
| 26 | Shortest Path Problem
Dijkstra's algorithm Huffman Trees and Codes | 9.3-9.4 | |||
| 27 | Iterative Improvement
The Simplex Method | 10.1 | 23:59: Assignment 11 | ||
| 28 | Work day | none | |||
| 8 | Jan. 30 - Feb. 3 | 29 | Simplex method continued.
The Maximum-Flow Problem | 10.2 | 23:59: Assignment 12 |
| 30 | Maximum-Flow Problem continued | none | |||
| 31 | Maximum Matching of Bipartite Graphs | 10.3 | 23:59: Assignment 13
23:59: Final project proposal | ||
| 32 | Lower bounds | 11.1-11.2 | |||
| 9 | Feb. 6-10 | 33 | P, NP, NP-complete | 11.3 | 7-8:30pm: Exam 3 |
| 34 | Coping with the Limitations of Algorithmic Power | skim chapter 12 | |||
| 35 | No class to compensate for evening exam 3 | none | 23:59: Assignment 14 | ||
| 36 | No class to compensate for evening exam 2 | none | |||
| 10 | Feb. 13-17 | 37 | Team project presentations | None | |
| 38 | Team project presentations | None | |||
| 39 | Team project presentations | None | 23:59: Assignment 15 | ||
| 40 | Team project presentations | None |