|
|
|
|
|
| 9/4/17 |
Sorting and asymptotic analysis Weds: Syllabus Thurs: Insertion Sort handout Insertion Sort handout w/ invariants Invariant proofs |
Asymptotic analysis practice (semi-optional, due Mon 9/11 in class) Homework 1: Sorting (due Fri 9/22 in class) |
CLRS 2.1, 3.1 KT 2.1-2.2, 2.4 |
| 9/11/17 |
More sorting and solving recurrences Fri: Induction practice |
CLRS 6, 2.3, 4.3-4.4 KT 2.5, 5.1-5.2 |
|
| 9/18/17 | More sorting and lower bounds | Homework 2: Recurrences and Proofs (due Weds 10/11 in class) | CLRS 7, 8.1-8.2 |
| 9/25/17 |
Divide-and-conquer Thurs: Proving the Master Theorem (corrected from version handed out in class) |
CLRS 4.1, 4.5-4.6 | |
| 10/2/17 |
Greedy algorithms Fri: Problems solved by greedy algorithms (corrected from version handed out in class) |
Homework 3: Greedy and DP Algorithms (due Mon 10/23 in class) |
CLRS 16.1-16.2 KT 4.1-4.2 |
| 10/9/17 | Greedy algorithms on graphs |
CLRS 24.3, 23 KT 4.4-4.5 |
|
| 10/16/17 | Dynamic programming |
CLRS 15.1, 15.3, 24.1 KT 6.1-6.2, 6.8 |
|
| 10/23/17 |
More dynamic programming, MIDTERM (Fri 10/27) Weds: DFS and topological sort review Thurs: Midterm review problems |
||
| 10/30 |
Network flow Weds: Network flow definitions Thurs/Fri: Ford-Fulkerson and Max-flow/Min-cut |
Homework 4: Network Flow (due Fri 11/17 in class) |
CLRS 26.1-26.2 KT 7.1-7.2 |
| 11/6/17 | Applications of network flow | KT 7.5, 7.7-7.9 | |
| 11/13/17 |
Problem reductions Fri: Graph Coloring and 3-SAT (solutions) |
KT 8.1-8.2, 8.7 | |
| 11/20/17 |
|
||
| 11/27/17 | NP-hardness and NP-completeness | Homework 5: NP-Completeness (due Fri 12/8 in class) |
CLRS 34.1-31.4 KT 8.3-8.5 |
| 12/4/17 | Approximation algorithms | ||
| 12/11/17 |
Review and FINAL EXAM (Weds 12/13) Mon: Sample final exam |
||