Watch a video introduction to this course on YouTube.
This course continues the discussion of algorithms started in CS 341. Whereas CS 341 focuses on worst-case behaviour of deterministic algorithms, in this course students are exposed to algorithmic approaches and methods for assessment that reflect a broad spectrum of criteria.
The particular problems and algorithms studied will be chosen by the instructor from application areas such as computational geometry, algebraic algorithms, distributed and parallel algorithms, machine learning, and other areas of active research.
CS 466 is normally taken in a student's fourth year. Those interested in the more mathematical aspects of writing good programs will find this course to be of value.
Prerequisites: CS 341; Computer Science students only.
Successors: Graduate courses in algorithms and computational complexity.
Introduction to Algorithms, 3rd ed., by Thomas Cormen, C. Leiserson, R. Rivest, C. Stein, MIT Press, 2009.
3 hours of lectures per week. Normally available in Fall and Spring.
Algorithms that rely on random bits; Las Vegas and Monte Carlo algorithms.
Analyzing sequences of operations whose individual costs differ widely; the accounting and potential methods. Possible topics: Fibonacci heaps; The "union-find" data structure.
Decision trees. Information theory lower bounds. Adversary arguments.
Techniques for creating approximation algorithms. Problems for which good approximations cannot be obtained.
Algorithms in which each request must be serviced before the subsequent request is received. The k-server problem.
May include specialized models of computation, Kolmogorov complexity, derandomization, and other tools to support the application areas chosen by the instructor.