CS 482 Schedule Summer 2005 | |||
| Meeting | Date | Topic | Suggested Reading |
|---|---|---|---|
| Lec. 1 | July 8 | Course Overview, Syllabus, Stable Matchings | 1.1, Ch 2 (optional) |
| Lec. 2 | 11 | Graphs Review and Representative Problems | 1.2, Ch 3 (optional) |
| Lec. 3 | 12 | Greedy Algorithms | 4.1 |
| Lec. 4 | 13 | Greedy Algorithms | 4.2 |
| Lec. 5 | 14 | Minimum Spanning Trees | 4.5 |
| Lec. 6 | 15 | Divide and Conquer | Ch 5 |
| Lec. 7 | 18 | Dynamic Programming | 6.1, 6.2 |
| Lec. 8 | 19 | Dynamic Programming | 6.3 |
| Lec. 9 | 20 | Dynamic Programming | 6.4 |
| Lec. 10 | 21 | Dynamic Programming | 6.5, 6.6 |
| Lec. 11 | 22 | Problem Solving Session | 4.4, 6.8 |
| Prelim I | 25 | Matchings, Greedy, Divide and Conquer, and Dynamic Programming | |
| Lec. 12 | 26 | Network Flows | 7.1 |
| Lec. 13 | 27 | Network Flows | 7.2, 7.6 |
| Lec. 14 | 28 | Network Flows | 7.3, 7.5, 7.6, 7.7 |
| Lec. 15 | 29 | Network Flows | 7.7, 7.10 |
| Lec. 16 | August 1 | Network Flows | 7.9, 7.11 |
| Lec. 17 | 2 | NP Completeness | intro to 8, 8.1, 8.2 |
| Lec. 18 | 3 | NP Completeness | 8.3, 8.4 |
| Lec. 19 | 4 | NP Completeness | 8.5, 8.6, 8.10 |
| Lec. 20 | 5 | NP Completeness | 8.8 |
| Lec. 21 | 8 | Problem Solving Session | not in text |
| Prelim II | 9 | Greedy, D&C, Dynamic Programming, Network Flows, and NP | |
| Lec. 22 | 10 | Special Cases of NP Problems | 10.1, 10.2 |
| Lec. 23 | 11 | Approximation Algorithms | not in text |
| Lec. 24 | 12 | Approximation Algorithms | 11.1 |
| Lec. 25 | 15 | Randomized Algorithms | 13.1, 13.2, 13.4 |
| Lec. 26 | 16 | Online Algorithms | not in text |
| Lec. 27 | 17 | Local Search | 12.1, 12.2 |
| Lec. 28 | 18 | Review Session | |
|
August 19 |
Final Exam, 9:30-12, Hollister 368 | ||