CS 482 Schedule Summer 2004The 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 boss! | |||
| Meeting | Date | Topic | Suggested Reading |
|---|---|---|---|
| Lec. 1 | July 9 | Course Overview, Syllabus, Stable Matchings | 1.1, Ch 2 (optional) |
| Lec. 2 | 12 | Graphs Review and Representative Problems | 1.2, Ch 3 (optional) |
| Lec. 3 | 13 | Greedy Algorithms | 4.1 |
| Lec. 4 | 14 | Greedy Algorithms | 4.2 |
| Lec. 5 | 15 | Minimum Spanning Trees | 4.4 |
| Lec. 6 | 16 | Divide and Conquer | Ch 6 |
| Lec. 7 | 19 | Dynamic Programming | 5.1, 5.2 |
| Lec. 8 | 20 | Dynamic Programming | 5.3 |
| Lec. 9 | 21 | Dynamic Programming | 5.4 |
| Lec. 10 | 22 | Dynamic Programming | 5.5, 5.6 |
| Lec. 11 | 23 | Problem Solving Session | 4.3, 5.7 |
| Prelim I | 26 | Matchings, Greedy, Divide and Conquer, and Dynamic Programming | |
| Lec. 12 | 27 | Network Flows | 7.1, 7.2 |
| Lec. 13 | 28 | Network Flows | 7.3, parts of 7.6 |
| Lec. 14 | 29 | Network Flows | 7.5, 7.6 |
| Lec. 15 | 30 | Network Flows | 7.6, 7.8 |
| Lec. 16 | August 2 | Network Flows | 7.11 |
| Lec. 17 | 3 | NP Completeness | intro to 8, 8.1 |
| Lec. 18 | 4 | NP Completeness | 8.2, 8.3 |
| Lec. 19 | 5 | NP Completeness | 8.4, 8.5 |
| Lec. 20 | 6 | NP Completeness | 8.5, 8.6 |
| Lec. 21 | 9 | Problem Solving Session | not in text |
| Lec. 22 | 10 | Special Cases of NP Problems | 10.1, 10.2 |
| Prelim II | 11 | Greedy, D&C, Dynamic Programming, Network Flows, and NP | |
| Lec. 23 | 12 | Approximation Algorithms | not in text |
| Lec. 24 | 13 | Approximation Algorithms | 11.1 |
| Lec. 25 | 16 | Probabilistic Algorithms | 13.1, 13.2 |
| Lec. 26 | 17 | Probabilistic & Online Algorithms | 13.3, 13.4, not in text |
| Lec. 27 | 18 | k-Centre Results | 11.2 and more |
| Lec. 28 | 19 | Review Session | |
|
August 20 |
Final Exam, 9:30-12, Hollister 368 | ||