Week # | Monday | Wednesday | Friday |
1 | Jan 7: Introduction. Ch. 1. lecture pdf, lecture pdf | Jan 9: Complexity. Ch. 2. lecture pdf | Jan 11: Graph Algorithms. Ch. 3. lecture pdf lecture ppt |
2 | Jan 14: Graph Algs. (cont.) | Jan 16: Graph Algs. (cont.) | Jan 18: Greedy Algorithms. Ch. 4 (4.4-4.6 are review; omit 4.7, 4.9). lecture pdf lecture ppt [Assignment 1 due] |
3 | Jan 21: Martin Luther King Day (no class) | Jan 23: Greedy Algs. (cont.) | Jan 25: Greedy Algs. (cont.) lecture pdf lecture ppt |
4 | Jan 28: Greedy Algs. (cont.) lecture pdf lecture ppt [Assignment 2 due] | Jan 30: Dynamic Programming. Ch. 6 (omit 6.8-6.10). lecture pdf lecture ppt | Feb 1: Dynamic Prog. (cont.) lecture pdf lecture ppt |
5 | Feb 4: Dynamic Prog. (cont.) [Assignment 3 due] | Feb 6: Dynamic Prog. (cont.) | Feb 8: Divide & Conquer. Ch. 5 lecture pdf lecture ppt |
6 | Feb 11: Divide & Conquer (Inversion counting, Closest pair problem, etc.) | Feb 13 review [Assignment 4 due] | Feb 15: [Midterm] |
7 | Feb 18: Presidents Day (no class) | Feb 20: Divide & Conquer (Karatsuba multiplication, Strassen's matrix multiplication) | Feb 22: Divide & Conquer (Fast Fourier Transform etc) lecture pdf lecture ppt |
8 | Feb 25: Divide & Conquer (cont.) lecture pdf lecture ppt | Feb 27: NP-Completeness & Intractability. Ch. 8 (omit 8.9, 8.10). lecture pdf lecture ppt | Mar 1: Network Flow lecture pdf lecture ppt |
9 | Mar 4: NP-Completeness (cont.) | Mar 6: NP-Completeness (cont.) lecture pdf lecture ppt | Mar 8: Topics Retrospective lecture pdf lecture ppt; NP-Completeness (cont.) [Project due] |
10 | Mar 11: NP-Completeness (cont.) lecture pdf lecture ppt | Mar 13: PSPACE. Ch. 9. | Mar 15: Final Review. [Assignment 5 due] |
Mar 19 (Tuesday): FINAL EXAMINATION 2:30 AM - 4:20 |