| Date | Assignment | Reading | Subject |
|---|---|---|---|
| Jan 25 | Introduction; problems and algorithms | ||
| Jan 27 | Preface, 1.1 | Sample problems; pseudocode, analysis, and proofs | |
| Jan 30 | 1.2, exercises | More sample problems | |
| Feb 01 | HW1 | 2.1-2.2 | Efficiency, scaling, worst-case, best-case, average-case, asymptotic notation |
| Feb 03 | 2.3-2.4 | Implementation, data structures, common running times | |
| Feb 06 | 2.5, exercises | Priority queues and heaps | |
| Feb 07 | Last day to add classes | ||
| Feb 08 | 3.1-3.2 | Graphs | |
| Feb 10 | 3.1-3.2 | Graphs | |
| Feb 13 | 3.1-3.2 | Graphs | |
| Feb 15 | HW1 due | 3.1-3.3 | Graphs, BFS |
| Feb 17 | HW2 | 3.3-3.4 | BFS, DFS, and bipartiteness |
| Feb 20 | 3.5-3.6, exercises | Connectedness, DAGs, topological sorting | |
| Feb 21 | Last day to drop classes | ||
| Feb 22 | 4.1-4.2 | Return & discuss homework; Greedy algorithms; interval scheduling; proving optimality | |
| Feb 24 | 4.2-4.4 | Proving optimality; shortest paths | |
| Feb 27 | 4.5 | Minimum spanning trees | |
| Mar 01 | 4.5 | Prim's algorithm for minimum spanning trees | |
| Mar 03 | HW2 due | 4.5 | Analyzing Prim's & Kruskal's algorithms |
| Mar 06 | 4.6, exercises | Union/Find data structure | |
| Mar 08 | HW3 | 5.1-5.2 | Mergesort and recurrences |
| Mar 10 | The Master Method for solving recurrences | ||
| Mar 13 | Discuss homework | ||
| Mar 15 | 5.5-5.6, exercises | Integer multiplication; student presentations | |
| Mar 17 | HW3 due | Student presentations | |
| Mar 20 | 6.1-6.2 | Student presentations; Dynamic programming & memoization | |
| Mar 22 | 6.3-6.4 | Multiway choices, extra parameter | |
| Mar 24 | Discuss homework, primes, factoring, ... | Mar 27 | 7.1-7.3 | Max flow, min cut |
| Mar 29 | HW4 | 7.5 (skim 7.7-7.12) | An application: Bipartite matching |
| Mar 31 | 12.1-12.2 | Local search and simulated annealing | |
| Mar 31 | Last day to withdraw from classes | ||
| Apr 03 | 13.1 | Randomization | |
| Apr 05 | 13.5 | Randomized median and quicksort | |
| Apr 07 | 13.6 | Hashing | |
| Apr 10 | Spring break | ||
| Apr 12 | |||
| Apr 14 | |||
| Apr 17 | Problems and programs again; an impossible problem | ||
| Apr 19 | HW4 due | Recursive, r.e., co-r.e., completeness | |
| Apr 21 | Several homework problem presentations | ||
| Apr 24 | HW5 | 8.1-8.3 | Polynomial reducibility, SAT, and NP |
| Apr 26 | 8.4-8.5 | Example NP-complete problems | |
| Apr 28 | 8.6-8.8 | More example NP-complete problems | |
| May 1 | 8.9-8.10, exercises | Complexity theory | |
| May 3 | 9.1-9.2 | PSPACE | |
| May 5 | Parallel complexity | ||
| May 08 | HW5 due | Catch up & review | |
| May 10 | Emergency/Study Day | ||
| May 17 | 344 final exam, 10:30-12:30 | ||