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.
What’s with the course title? This term, I’m revamping this course to cover a broader base of material. While we’ll still be covering approximation algorithms in this course, we’ll also be discussing all kinds of other aspects of advanced algorithm design and analysis.
Course Details
Lecture Time/Place
Monday, 10:30am–11:20am; Wednesday, 9:30am–10:20am; Friday, 8:30am–9:30am
All lectures are held in Mulroney Hall, room 3024.
Textbook
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
- Two assignments (10% each, total 20%)
- Two quizzes (15% each, total 30%)
- Student presentation (total 30%): a lesson plan (10%) and the presentation itself (20%)
- Report on the presentation (10%)
- Participation (total 10%): class participation (5%) and reviewing student presentations (5%)
News
- Sep. 21: Lecture slides for the third week have been posted.
- Sep. 14: Lecture slides for the second week have been posted.
- Sep. 8: Lecture slides for the first week have been posted.
- Sep. 2: Welcome to the course! Please see our Moodle page for details about the course this term.
Lectures
| Week | Notes | Readings |
| 1 | Introduction; Space complexity | Kleinberg & Tardos, 9.1–9.4 |
| 2 | Space complexity (cont’d); Extending tractability | Kleinberg & Tardos, 9.5, 10.1–10.3 |
| 3 | Approximation algorithms | Kleinberg & Tardos, 11.1–11.2, 11.4 |
Assignments
- Assignment 1, due Oct. 2
- Assignment 2, due Nov. 6
- Student Presentation, due date varies
- Report, due Dec. 7
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.
The presentation and report must be submitted on the due date. Late submissions will not be accepted.
Quizzes
Quiz 1
Date: Oct. 9, 2026
Time: 8:30am–9:20am
Place: Mulroney Hall, Room 3024
Content: All material from Weeks 1 to 5
Quiz 2
Date: Nov. 13, 2026
Time: 8:30am–9:20am
Place: Mulroney Hall, Room 3024
Content: All material from Weeks 6 to 9
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Office hours: Monday 11:30am–1:20pm/Wednesday 10:30am–12:20am/Friday 9:30am–11:20am, or by appointment