Algorithm Analysis
As offered at AAU
About the Course
Course Outline
| Lecture | Topic | Reading |
|---|---|---|
| 1 | Introduction and Course Logistics (Slides, Lecture Note) | |
| 2 | Stable Matching (Slides) | Chapter 1 |
| 3 | Algorithm Analysis: Runtime and Proof of Correctness (Slides, Lecture Note) | Chapter 2 |
| 4 | Algorithm Analysis: Rate of Growth (Same slides as Lecture 3) | |
| 5 | Graphs (Slides) | Chapter 3 |
| 6 | Greedy Algorithms for Scheduling Problems (Slides) | Chapter 4 |
| 7–9 | Continued: Greedy Algorithms (Same slides as Lecture 6) | |
| 10–12 | Divide and Conquer (Slides) | Chapter 5 |
| 13–15 | Dynamic Programming (Slides) | Chapter 6 |
| 16 | Network Flow (Slides) | Chapter 7 (Sections 7.1 & 7.2) |
| 17–18 | NP and Computational Intractability (Slides) | Chapter 8 |
Textbook
- Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley, 2006. ISBN: 0321295358.
Additional Reference
- Introduction to Algorithms (Fourth Edition) by Cormen, Leiserson, Rivest, and Stein. MIT Press, 2022. ISBN: 9780262046305.
Reading
Reading assignments will be announced on the class webpage. Students are strongly encouraged to complete the readings before class sessions.
Grading
Homework will be assigned every two to three weeks. There will be a midterm and a comprehensive final exam. All assignments and exams are due by midnight on the specified deadline.
Grading Breakdown
- 20% Midterm Exam (Take-home)
- 30% Final Exam (Take-home)
- 50% Homework