CSCI 435: Algorithms and Complexity (Winter 2023)

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

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

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

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