CSCI 435: Algorithms and Complexity (Winter 2023)

This webpage contains archived material from a past offering of this course.
Contents may differ from the current or most recent offering of the course.

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.


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

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%.



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


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.



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



Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Student hours: Tuesday, 9:15am–11:15am