The prerequisites for the class are cs54 and cs62. Talk to one of the professors if you have questions about these requirements.
The textbook is Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, and Stein. Copies are available at Huntley bookstore.
Any topic/readings/assignments that are listed for a date in the future should be taken as (potentially very) tentative. Readings/assignments will be updated by the preceding class; lecture topics will be updated by the following class.
| Week | Date | In class topic(s) | Readings (CLRS) | Assignment due |
|---|---|---|---|---|
| 1 | (Tue) 1/21 | intro review (asymptotics, proofs - direct, contradiction, style) | ||
| (Thu) 1/23 | review (proofs - induction) insertion sort | 2, 3 | ps1 | |
| 2 | (Tue) 1/28 | mergesort recurrences quicksort average case analysis | 4.3-4.5 | ps2 |
| (Thu) 1/30 | master method quicksort average case analysis | 4.2, 7 | ps3 - part 1 | |
| 3 | (Tue) 2/4 | order statistics | 9 | ps3 - part 2 - coding |
| (Thu) 2/6 | bounding problems lower bounds on sorting linear time sorts | 8 | ||
| 4 | (Tue) 2/11 | review (basic data structures) heaps | 6, 10 | ps4 |
| (Thu) 2/13 | amortized analysis | 17 | ps5 | |
| 5 | (Tue) 2/18 | (balanced) binary search trees | 12, 13 | ps6 |
| (Thu) 2/20 |
other data structures review | ps7 | ||
| 6 | (Tue) 2/25 | checkpoint 1 | ||
| (Thu) 2/27 | optimal substructure, greedy choice property greedy algorithms: change, activity scheduling | 16 | ps8 | |
| 7 | (Tue) 3/3 | dynamic programming: fibonacci, longest common subsequence, matrix multiplication | 15 | ps9 |
| (Thu) 3/5 | dynamic programming: rod splitting, 0-1 knapsack implementation | 15 | ps10 | |
| 8 | (Tue) 3/10 | dynamic programming continued | 15 | ps11 - part 1 |
| (Thu) 3/12 | linear programming | 29 | ps11 - part 2 (coding) | |
| (Tue) 3/17 | spring break | |||
| (Thu) 3/19 | ||||
| (Tue) 3/24 | spring break #2 | |||
| (Thu) 3/26 | ||||
| 10 | (Tue) 3/31 | review: graphs, trees, traversals topological sort strongly connected components | B.4-B.5, 22 | |
| (Thu) 4/2 | single source shortest paths: Bellman-Ford, Dijkstra's | 24 | ||
| 11 | (Tue) 4/7 | all pairs shortest paths: Johnson's, Floyd-Warshall | 25 | ps12 |
| (Thu) 4/9 | minimum spanning trees: Kruskal's, Prims | 23 | ||
| 12 | (Tue) 4/14 | network flow | 26 | ps13 |
| (Thu) 4/16 | checkpoint 2 | |||
| 13 | (Tue) 4/21 | maximum bipartite matching P, NP, NPC | 26, 34 | ps14 |
| (Thu) 4/23 | NP-completeness reductions | 34 | ||
| 14 | (Tue) 4/28 | more NP-completeness reductions | 34 | ps15 |
| (Thu) 4/30 | more NP-completeness reductions | 35 | ||
| 15 | (Tue) 5/5 | approximation algorithms | ps16 | |
The final exam time is Thursday, May 14th from 2-5pm7