CS 482 Schedule Summer 2003The notes for some classes are posted below. If there is a class for which notes are missing, it is probably because we didn't make any. We reserve the right to make changes to the schedule, because we're the boss! | |||
| Meeting | Date | Topic | Suggested Reading |
|---|---|---|---|
| Lec. 1 | July 7 | Course Overview, Syllabus, Stable Matchings | 1.1, 1.2 |
| Lec. 2 | 8 | Graphs Review and Representative Problems | 1.3, 1.4, Ch 2 (optional) |
| Lec. 3 | 9 | Greedy Algorithms | 3.1 |
| Lec. 4 | 10 | Greedy Algorithms | 3.2 |
| Lec. 5 | 11 | Minimum Spanning Trees | 3.4 |
| Lec. 6 | 14 | Divide and Conquer | Ch 4 |
| Lec. 7 | 15 | Dynamic Programming | 5.1 |
| Lec. 8 | 16 | Dynamic Programming | 5.2 |
| Lec. 9 | 17 | Dynamic Programming | 5.3 |
| Lec. 10 | 18 | Dynamic Programming | 5.4, 5.5, 5.6 |
| Lec. 11 | 21 | Alexa's Essential Mix no.1 | 3.3, 5.7 |
| Prelim I | 22 | Matchings, Greedy, Divide and Conquer, and Dynamic Programming | |
| Lec. 12 | 23 | Network Flows | 6.1, 6.3 |
| Lec. 13 | 24 | Network Flows | 6.2, 6.4, parts of 6.5 and 6.8 |
| Lec. 14 | 25 | Network Flows | 6.7, 6.8 |
| Lec. 15 | 28 | Network Flows | 6.8, 6.9 |
| Lec. 16 | 29 | Network Flows | 6.9 |
| Lec. 17 | 30 | NP Completeness | intro to 7, 7.1.5, 7.2 |
| Lec. 18 | 31 | NP Completeness | 7.3, 7.4 |
| Lec. 19 | August 1 | NP Completeness | 7.5, 7.1 |
| Lec. 20 | 4 | NP Completeness | 7.6 |
| Lec. 21 | 5 | Alexa's Essential Mix no.2 | |
| Prelim II | 6 | Greedy, D&C, Dynamic Programming, Flows, and NP | |
| Lec. 22 | 7 | Special Cases of NP Problems | 9.1, 9.2 |
| Lec. 23 | 8 | Approximation Algorithms | not in text |
| Lec. 24 | 11 | Approximation Algorithms | not in text |
| Lec. 25 | 12 | Probabilistic Algorithms | 12.1, 12.2, 12.4 |
| Lec. 26 | 13 | Online Algorithms | not in text |
| Lec. 27 | 14 | Local Search | 11.1, 11.2 |
| Lec. 28 | 15 | Alexa's Essential Mix no.3 | |
|
August 18 |
Final Exam, Hollister 206, 9:30-12 | ||