| Date | Assignment | Reading | Subject |
|---|---|---|---|
| Jan 24 | pre-test | Intro; define problem, efficiency, resource, problem size | |
| Jan 26 | pre-test | Discuss pre-test; conclusions from timing data | |
| Jan 28 | pre-test | Discuss pre-test;O(*), θ(*), o(*), Ω(*), ω(*),...; Euclid's Game | |
| Jan 31 | Analyze Euclid's Game; hypotheses and proofs | ||
| Feb 02 | Analyze Euclid's Game; inductive and indirect proofs | ||
| Feb 04 | HW1 | 1.1 | Algorithmic problems; proofs about algorithms |
| Feb 07 | Last day to add classes | ||
| Feb 07 | 1.2 | More algorithmic problems | |
| Feb 09 | 2.1-2.3 | Asymptotic analysis in practice | |
| Feb 11 | 2.4-2.5 | More examples of asymptotic analysis | |
| Feb 14 | 3.1-3.2 | Graphs: definitions, applications, basic algorithms | |
| Feb 16 | 3.3-3.4 | Traversals, DFS, and BFS | |
| Feb 18 | 3.5-3.6 | Directed graphs | |
| Feb 21 | Last day to drop classes | ||
| Feb 21 | HW1 due | class presentations of HW1 | |
| Feb 23 | HW2 | More on graphs | |
| Feb 25 | class presentations of HW1? Directed graphs? | ||
| Feb 28 | 4.1-4.2 | Greedy algorithms and proofs about them | |
| Mar 02 | 4.3-4.4 | Greedy algorithms; discuss homework | |
| Mar 04 | I'll be out of town at a conference; problem session | ||
| Mar 07 | HW2 due; HW3 | class presentations of HW2 | |
| Mar 09 | I'll be out of town at a conference; problem session | ||
| Mar 11 | I'll be out of town at a conference; problem session | ||
| 3/12-3/20 | Spring break | ||
| Mar 21 | Discuss homework | ||
| Mar 23 | Discuss homework | ||
| Mar 25 | 4.5-4.6 | Minimum spanning trees and data structures for them | |
| Mar 28 | Last day to withdraw from classes | ||
| Mar 28 | 4.5-4.6 | Minimum spanning trees and data structures for them | |
| Mar 30 | 4.5-4.6 | Minimum spanning trees and data structures for them | |
| Apr 01 | 5.1-5.3 | Recursion and recurrence relations | |
| Apr 04 | 5.4-5.6 | divide and conquer algorithms | |
| Apr 06 | HW3 due | class presentations of HW2 and HW3 | |
| Apr 08 | 6.1, 6.2 | memoization and dynamic programming | |
| Apr 11 | Research day: classes officially cancelled, but I'll be here to make up for missed classes in March | Apr 11 | 6.3, 6.4 | dynamic programming with multi-way choices or extra variables |
| Apr 13 | dynamic programming | ||
| Apr 15 | dynamic programming | ||
| Apr 18 | dynamic programming | ||
| Apr 20 | 6.8-6.9 | shortest paths via dynamic programming | |
| Apr 22 | 7.1-7.3, 7.5 | network flow | |
| Apr 25 | computability | ||
| Apr 27 | 8.1-8.3 | computability; computational complexity | |
| Apr 29 | 8.4-8.5 | computational complexity | |
| May 02 | HW4 | chap. 9 | space-bounded computational complexity |
| May 04 | homework 1-3 due | class presentations of homework | |
| May 06 | parallel computational complexity | ||
| May 09 | HW4 due | catch up and review for final; class presentations of homework | |
| May 16 | 344 final exam, 10:30 AM-12:30 PM | ||