Course Description
This course provides an introduction to some fundamental areas of research in algorithms and computational complexity theory. Flow networks and randomized, approximation, parameterized, and online algorithms and complementary techniques in hardness of approximation and lower bounds are presented. This course is a broad exploration of these topics to provide a well-rounded introduction to modern theories in algorithms and theoretical computer science.
See the course outline for more information.
Course Details
Lecture Time/Place
Tuesday, 8:15am–9:05am; Wednesday, 10:15am–11:05am; Friday, 9:15am–10:05am
All lectures are held in Mulroney Hall, room 3024.
Textbooks
General material: J. Kleinberg and É. Tardos, Algorithm Design. Pearson Addison-Wesley, 2005.
Online algorithms: A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press, 1995.
Randomized algorithms: R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, 1995.
Approximation algorithms: D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms. Cambridge University Press, 2011.
Fixed-parameter algorithms: R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Springer, 2013.
Some textbooks are available at the campus bookstore, in the campus library, or online.
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
- Jan. 27: Lecture notes for the fourth week have been posted to Moodle.
- Jan. 25: Readings and discussion questions for the fourth week have been posted.
- Jan. 20: Lecture notes for the third week have been posted to Moodle.
- Jan. 13: Lecture notes for the second week have been posted to Moodle.
- Jan. 11: Readings and discussion questions for the second week have been posted.
- Jan. 9: The first assignment has been posted. It is due by Jan. 24 at 8:15am.
- Jan. 6: Lecture notes for the first week have been posted to Moodle.
- Jan. 4: Welcome to the course! Please see our Moodle page for details about the course this term.
Lectures
| Week | Topic | Readings |
| 1 | Introduction and review | – |
| 2 | Online algorithms: Secretary problem, offline paging problem | [Gar60], [ST85] |
| 3 | Online algorithms (cont’d): Online paging problem | – |
| 4 | Randomized algorithms: Generating random bits, minimum cuts | [Kar93], [Met87] |
| 5 | Randomized algorithms (cont’d): Maximum cuts, probabilistic method, derandomization | – |
Discussion Questions
Assignments
- Assignment 1, due Jan. 24
- Assignment 2, due Feb. 28
- Assignment 3, due Mar. 28
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. 15, 2022
Time: 10:15am–11:05am
Place: Mulroney Hall, room 3024
Content: All material from Weeks 1 to 6
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Student hours: Tuesday, 9:15am–11:15am