CMP 741 - Advanced Analysis of Algorithms, in person at D6. (virtual on February 10 and 17)
Lale Özkahya
Office Hours:
Email to arrange an appointment.
All communication will be on https://piazza.com/hacettepe.edu.tr/spring2022/cmp741
| Week | Topic and Slides | Notes | Reading on Applications and Notes by Jeff Erickson (JE) |
| 1 | Graphs [Slides: 1 ] Exercise Set 1 | Chapter 3 in KT | |
| 2 | Greedy Algorithms [Slides: 1] |
Chapter 4 in
KT Further Examples on Greedy Algorithms |
|
| 3 | Divide and Conquer [Slides: 1, 2] | Chapter 5 in KT | |
| 4 | Dynamic Programming Deadline to Pick a Paper [Slides: 1, 2] | Chapter 6 in KT | |
| 5 | Network Flow [Slides: 1, 2] |
Chapter 7 in
KT Ford-Fulkerson Demo |
|
| 6 | Intractability I: Polynomial Time Reductions [Slides] | Chapter 8 in KT | |
| 7 | Midterm Exam | -- | |
| 8 | Intractability II: P, NP, and NP-complete [Slides] | Chapter 8 in KT | |
| 9 | PSPACE: A Class of Problems beyond NP [Slides] | Notes | Chapter 9 in KT |
| 10 | Limits of Tractability [Slides] | Chapter 10 in KT | |
| 11 | Approximation Algorithms [Slides] |
Chapter 11 in
KT Approximation Algorithms (JE) |
|
| 12 | Local Search Deadline for Paper Reading Submission [Slides] | Chapter 12 in KT | |
| 13 | Randomized Algorithms [Slides] |
Chapter 13 in
KT Randomized Algorithms (JE) |
|
| 14 | Paper Presentations | -- |