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 22 | Introduction | ||
| Wed | Aug 24 | Syllabus, algorithm design & analysis overview | Chapter 1 | ||
| Thu | Aug 25 | R1: LaTeX and pseudocode | |||
| Fri | Aug 26 | Insertion sort: pseudocode and efficiency | 2.2 | ||
| 2 | Mon | Aug 29 | Writing loop invariants | 2.1 | |
| Wed | Aug 31 | Proving loop invariants using induction | Induction (thru >= p. 158) | ||
| Thu | Sep 1 | R2: Proof practice | |||
| Fri | Sep 2 | Asymptotic notation | 3.1-3.3 | HW 1 (hw1.tex) | sols (tex) | |
| 3 | Mon | Sep 5 | Asymptotic notation, cont. | ||
| Wed | Sep 7 | Divide and Conquer, recurrences | 2.3, 4.3-4.4 | ||
| Thu | Sep 8 | R3: Asymptotic Time Complexity | |||
| Fri | Sep 9 | Recurrences, cont. | HW 2 (hw2.tex) | ||
| 4 | Mon | Sep 12 | Quicksort | 7.1-7.2 | |
| Wed | Sep 14 | Sorting lower bound | 8.1 | ||
| Thu | Sep 15 | R4: Divide and Conquer | |||
| Fri | Sep 16 | Closest Pair problem | Closest pair | reading notes | ||
| 5 | Mon | Sep 19 | Dynamic programming: Fibonacci, rod cutting | 14.1 | HW 3 (hw3.tex) |
| Wed | Sep 21 | No class | |||
| Thu | Sep 22 | R5: Dynamic Programming I | |||
| Fri | Sep 23 | Matrix chain multiplication | 14.2 | ||
| 6 | Mon | Sep 26 | Elements of dynamic programming | 14.3 | HW 4 |
| Wed | Sep 28 | Longest common subsequence | 14.4 | ||
| Thu | Sep 29 | R6: Dynamic Programming II | |||
| Fri | Sep 30 | DNA sequence alignment | |||
| 7 | Mon | Oct 3 | Greedy algorithms, activity selection | 15.1 | HW 5 |
| Wed | Oct 5 | Exam 1 | |||
| Thu | Oct 6 | R7: Greedy Algorithms | |||
| Fri | Oct 7 | Elements of greedy algorithms | 15.2 | ||
| 8 | Mon | Oct 10 | NO CLASS — FALL BREAK | ||
| Wed | Oct 12 | Huffman coding | 15.3 | ||
| Thu | Oct 13 | R8: Overview of Recursive Paradigms | |||
| Fri | Oct 14 | Abstract Data Types | |||
| 9 | Mon | Oct 17 | Binary search trees (review) | 12.1-12.3 | HW 6 |
| Wed | Oct 19 | B-trees | 18.1-18.3 | ||
| Thu | Oct 20 | R9: Red-Black Trees | 13.1-13.3 | ||
| Fri | Oct 21 | B-trees | |||
| 10 | Mon | Oct 24 | Amortized analysis – aggregate method | 16.1-16.3 | |
| Wed | Oct 26 | ||||
| Thu | Oct 27 | R10: Disjoint Sets | 19.1-19.3 | ||
| Fri | Oct 28 | Amortized analysis – accounting method | |||
| 11 | Mon | Oct 31 | Amortized analysis – potential functions | HW 7 | files | |
| Wed | Nov 2 | Graphs: definitions, representations | 20.1, B.4 | ||
| Thu | Nov 3 | R11: Disjoint Sets, Cont. | |||
| Fri | Nov 4 | Breadth-first search (BFS) | 20.2-3 | ||
| 12 | Mon | Nov 7 | HW 8 | ||
| Wed | Nov 9 | Depth-first search (DFS) and topological sort | 20.4 | ||
| Thu | Nov 10 | R12: Strongly Connected Components | |||
| Fri | Nov 11 | Minimum spanning trees (MST) | 21.1 | ||
| 13 | Mon | Nov 14 | Kruskal’s and Prim’s MST algorithms | 21.2 | |
| Wed | Nov 16 | Single source shortest paths, Bellman-Ford | 22.1 | Exam 2 (take home) | |
| Thu | Nov 17 | R13: Graph Paths | |||
| Fri | Nov 18 | Dijkstra’s algorithm | 22.3 | ||
| Nov 21-25 | NO CLASS — THANKSGIVING BREAK | ||||
| 14 | Mon | Nov 28 | Maximum Flow | 24.1 | |
| Wed | Nov 30 | Ford-Fulkerson algorithm | 24.2 | ||
| Thu | Dec 1 | R14: Flow and APSP | 23.1-23.2 | ||
| Fri | Dec 2 | Hard problems: P and NP | pp. 1042-1047 | ||
| Mon | Dec 5 | Undecidability | HW 9 | ||
| Tue | Dec 13 | Final Exam (3:30 in Dana 134) |