Contents may differ from the current or most recent offering of the course.
Course Description
A survey of advanced topics in algorithms and complexity theory. Topics include online, randomized, approximation, and parameterized algorithms as well as other advanced algorithm design techniques, average-case analysis, and amortized analysis.
See the course outline for more information.
Course Details
Lecture Time/Place
Monday, 4:00pm–5:15pm; Wednesday, 2:30pm–3:45pm
All lectures are held in Mulroney Hall, room 4032.
Textbooks
J. Kleinberg and É. Tardos, Algorithm Design. Pearson Addison-Wesley, 2005.
Course notes will be provided for each lecture. The course textbook will be used as an optional supplement.
Marking Scheme
- Three assignments (15% each, total 45%)
- Research article discussions (10%)
- Midterm examination (25%)
- Final examination (20%)
You must write the final examination in order to pass the course, even if the weighted sum of your other submissions is at least 50%.
News
- Apr. 2: The final exam will be written on Apr. 15. See the review document and the Exams section below for details. A practice final exam is also available.
- Mar. 31: Lecture notes for the twelfth week have been posted.
- Mar. 24: Lecture notes for the eleventh week have been posted.
- Mar. 19: The third assignment has been posted. It is due by Apr. 2 at 2:30pm.
- Mar. 17: Lecture notes for the tenth week have been posted. The eighth set of discussion questions has also been posted.
- Mar. 10: Lecture notes for the ninth week have been posted. The seventh set of discussion questions has also been posted.
- Mar. 3: The sixth set of discussion questions has been posted.
- Feb. 26: Lecture notes for the seventh week have been posted. The second assignment has also been posted. It is due by Mar. 12 at 2:30pm.
- Feb. 24: The fifth set of discussion questions has been posted.
- Feb. 5: The midterm will be written next week during the Feb. 12 lecture. See the review document and the Exams section below for details. A practice midterm is also available, although the practice midterm was written in a past offering of the course where topics were covered in a different order. (The course textbook has many more practice problems on material we covered.)
- Feb. 5: The fourth set of discussion questions has been posted.
- Feb. 3: Lecture notes for the fifth week have been posted.
- Jan. 29: Lecture notes for the fourth week have been posted.
- Jan. 27: The third set of discussion questions has been posted.
- Jan. 22: The first assignment has been posted. It is due by Feb. 5 at 2:30pm.
- Jan. 20: Lecture notes for the third week have been posted. The second set of discussion questions has also been posted.
- Jan. 13: Lecture notes for the second week have been posted. The first set of discussion questions has also been posted.
- Jan. 6: Lecture notes for the first week have been posted.
- Jan. 6: Welcome to the course! Please see our Moodle page for details about the course this term.
Lectures
| Week | Topic | Readings |
| 1 | Introduction; Space complexity | Kleinberg & Tardos, 9.1–9.3 |
| 2 | Space complexity (cont’d); Extending tractability | Kleinberg & Tardos, 9.4–9.5, 10.1–10.3 |
| 3 | Approximation algorithms | Kleinberg & Tardos, 11.1–11.2, 11.4 |
| 4 | Approximation algorithms (cont’d); Local search | Kleinberg & Tardos, 11.6, 11.8; 12.1–12.2 |
| 5 | Local search (cont’d); Randomized algorithms | Kleinberg & Tardos, 12.3–12.4; 13.1–13.3 |
| 6 | Midterm examination | — |
| — | Winter study break | — |
| 7 | Randomized algorithms (cont’d); Online algorithms | Kleinberg & Tardos, Ch. 13.4, 13.6 |
| 8 | Online algorithms (cont’d) | — |
| 9 | Amortized analysis | — |
| 10 | Linear programming | — |
| 11 | Linear programming (cont’d) | — |
| 12 | Quantum computing | — |
Discussion Questions
- Space complexity: [Mic92], [ADGV15]
- Extending tractability: [DT11]
- Approximation algorithms: [Joh74], [Chv79]
- Local search: [HT85]
- Randomized algorithms: [Kar93], [Met87]
- Online algorithms: [Gar60], [ST85]
- Amortized analysis: [Imp95], [BS84]
- Linear programming: [Dan91]
Assignments
- Assignment 1, due Feb. 5
- Assignment 2, due Mar. 12
- Assignment 3, due Apr. 2
Assignments are due at the beginning of class on the due date. Late assignments will be accepted up to the beginning of the first class following the due date. Late assignments are subject to a penalty of 10% deducted from the earned mark.
Exams
Midterm
Date: Feb. 12, 2025
Time: 2:30pm–3:45pm
Place: Mulroney Hall, room 4032
Content: All material from Weeks 1 to 6
Final Exam
Date: Apr. 15, 2025
Time: 2:00pm–4:30pm
Place: Mulroney Hall, room 4032
Content: Primarily material from Weeks 7 to 12, some earlier material
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Office hours: Monday/Wednesday/Thursday, 10:30am–11:20am, or by appointment