Refer to this page daily for updates. This is a dynamic schedule (except for the labs); only the past is certain.
| Week | Day | Date | Topic | Reading Due | Assignment Due |
|---|---|---|---|---|---|
| 1 | Mon | Aug 21 | Introduction | ||
| Wed | Aug 23 | Syllabus, algorithm design & analysis overview | Chapter 1 | ||
| Thu | Aug 24 | R1: LaTeX and pseudocode | |||
| Fri | Aug 25 | Proof review | |||
| 2 | Mon | Aug 28 | Proof by induction | ||
| Wed | Aug 30 | Insertion sort: pseudocode and efficiency | 2.2 | ||
| Thu | Aug 31 | R2: Proof practice | |||
| Fri | Sep 1 | Insertion sort: loop invariants and correctness | 2.1 | ||
| 3 | Mon | Sep 4 | Insertion sort: proving loop invariants | ||
| Wed | Sep 6 | Asymptotic notation | 3.1-3.3 | Homework 1 (latex) | |
| Thu | Sep 7 | R3: Asymptotic time complexity | |||
| Fri | Sep 8 | Asymptotic notation, cont. | |||
| 4 | Mon | Sep 11 | Divide and Conquer, recurrences | 2.3, 4.3-4.4 | Homework 2 (latex) |
| Wed | Sep 13 | Away – attend other section | |||
| Thu | Sep 14 | R4: Cancelled | |||
| Fri | Sep 15 | Away – attend other section | |||
| 5 | Mon | Sep 18 | One last recurrence… | ||
| Wed | Sep 20 | Quicksort | 7.1-7.2 | Homework 3 (latex) | |
| Thu | Sep 21 | R5: Divide and Conquer algorithms | |||
| Fri | Sep 22 | Sorting lower bound | 8.1 | ||
| 6 | Mon | Sep 25 | The closest pair problem | Closest pair | reading notes | |
| Wed | Sep 27 | Dynamic programming: Fibonacci, rod cutting | 14.1 | ||
| Thu | Sep 28 | R6: Rod cutting, cont. | |||
| Fri | Sep 29 | Matrix chain multiplication | 14.2 | Homework 4 | |
| 7 | Mon | Oct 2 | Elements of dynamic programming | 14.3 | |
| Wed | Oct 4 | ||||
| Thu | Oct 5 | R7: DP problems | Homework 5 | ||
| Fri | Oct 6 | Exam 1 | |||
| 8 | Mon | Oct 9 | NO CLASS — FALL BREAK | ||
| Wed | Oct 11 | Longest common subsequence | 14.4 | ||
| Thu | Oct 12 | R8: Knapsack problem | |||
| Fri | Oct 13 | Knapsack problem | |||
| 9 | Mon | Oct 16 | Sequence alignment | Sequence alignment | reading notes | |
| Wed | Oct 18 | Global and local alignment | |||
| Thu | Oct 19 | R9: Homework help | |||
| Fri | Oct 20 | Greedy algorithms, activity selection | 15.1 | Homework 6 | |
| 10 | Mon | Oct 23 | Elements of greedy algorithms | 15.2 | |
| Wed | Oct 25 | Huffman coding | 15.3 | Homework 7 | |
| Thu | Oct 26 | R10: Greedy algorithms | |||
| Fri | Oct 27 | Graphs | 20.1, B.4 | ||
| 11 | Mon | Oct 30 | Breadth-first search (BFS) | 20.2-3 | Homework 8 |
| Wed | Nov 1 | Depth-first search (DFS) and topological sort | 20.4 | ||
| Thu | Nov 2 | R11: | |||
| Fri | Nov 3 | Minimum spanning trees (MST) | 21.1 | ||
| 12 | Mon | Nov 6 | Prim MST algorithm | 21.2 | |
| Wed | Nov 8 | Exam 2 | |||
| Thu | Nov 9 | R12: Strongly connected components | |||
| Fri | Nov 10 | Tangent: heaps and priority queues | 6.1-2, 6.5 | ||
| 13 | Mon | Nov 13 | Kruskal’s MST algorithm | ||
| Wed | Nov 15 | Single source shortest paths, Bellman-Ford | 22.1 | ||
| Thu | Nov 16 | R13: | |||
| Fri | Nov 17 | Dijkstra’s algorithm | 22.3 | ||
| Nov 20-24 | NO CLASS — THANKSGIVING BREAK | ||||
| 14 | Mon | Nov 27 | Maximum flow and the Ford-Fulkerson method | 24.1-2 | |
| Wed | Nov 29 | Max-flow min-cut theorem | Article 1 | Article 2 (skim first 2 pages) | Homework 9 | |
| Thu | Nov 30 | R14: Applications of maximum flow | 24.3 | ||
| Fri | Dec 1 | Hard problems: P and NP | pp. 1042-1047 | ||
| Mon | Dec 4 | Undecidability | Homework 10 | ||
| Thu | Dec 14 | Final Exam (8:00-11:00) |