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 |