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
- Apr. 17: The final exam will be written on Apr. 19. See the review document and the Exams section below for details.
- Mar. 31: Lecture notes for the twelfth week have been posted to Moodle.
- Mar. 24: Lecture notes for the eleventh week have been posted to Moodle.
- Mar. 20: The third assignment has been posted. It is due by Apr. 4 at 8:15am.
- Mar. 17: Lecture notes for the tenth week have been posted to Moodle.
- Mar. 15: Reading and discussion questions for the tenth week have been posted.
- Mar. 10: Lecture notes for the ninth week have been posted to Moodle.
- Mar. 3: Lecture notes for the eighth week have been posted to Moodle.
- Mar. 2: Due to the delayed opening of the university, the lecture tomorrow is cancelled.
- Mar. 1: Reading and discussion questions for the eighth week have been posted.
- Feb. 27: The second assignment has been posted. It is due by Mar. 14 at 8:15am.
- Feb. 14: Due to the delayed opening of the university, the lecture and office hour today are cancelled.
- Feb. 10: The midterm will be written next week during the Feb. 15 lecture. See the review document and the Exams section below for details.
- Feb. 10: Lecture notes for the sixth week have been posted to Moodle.
- Feb. 3: Lecture notes for the fifth week have been posted to Moodle.
- 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 | — |
| 6 | Randomized algorithms (cont’d): Las Vegas/Monte Carlo algorithms, complexity theory | — |
| 7 | Mid-course review, midterm examination | — |
| — | Winter study break | — |
| 8 | Amortized analysis: Aggregate method, accounting method, potential method | [Imp95], [BS84] |
| 9 | Amortized analysis (cont’d): Specific examples | — |
| 10 | Approximation algorithms: greediness, integer/linear programming | [Joh74], [Chv79] |
| 11 | Approximation algorithms (cont’d): rounding, dual rounding, primal-dual method | — |
| 12 | Fixed-parameter algorithms: bounded search trees, branch and bound, kernelization | — |
Discussion Questions
- Week 2 Discussion Questions
- Week 4 Discussion Questions
- Week 8 Discussion Questions
- Week 10 Discussion Questions
Assignments
- Assignment 1, due Jan. 24
- Assignment 2, due
Feb. 28Mar. 14 - Assignment 3, due
Mar. 28Apr. 4
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, 2023
Time: 10:15am–11:05am
Place: Mulroney Hall, room 3024
Content: All material from Weeks 1 to 6
Final Exam
Date: Apr. 19, 2023
Time: 9:00am–11:30am
Place: Mulroney Hall, room 3024
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
Student hours: Tuesday, 9:15am–11:15am