CS 466 Algorithm Design and Analysis
Watch a video introduction to this course on YouTube.
Objectives
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.
Intended Audience
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.
Related Courses
Prerequisites: CS 341; Computer Science students only.
Successors: Graduate courses in algorithms and computational complexity.
References
Introduction to Algorithms, 3rd ed., by Thomas Cormen, C. Leiserson, R. Rivest, C. Stein, MIT Press, 2009.
Schedule
3 hours of lectures per week. Normally available in Fall and Spring.
Outline
Randomized Algorithms (6 hours)
Algorithms that rely on random bits; Las Vegas and Monte Carlo algorithms.
Amortized Analysis (6 hours)
Analyzing sequences of operations whose individual costs differ widely; the accounting and potential methods. Possible topics: Fibonacci heaps; The "union-find" data structure.
Lower Bounds (6 hours)
Decision trees. Information theory lower bounds. Adversary arguments.
Approximation Algorithms (6 hours)
Techniques for creating approximation algorithms. Problems for which good approximations cannot be obtained.
Online Algorithms (6 hours)
Algorithms in which each request must be serviced before the subsequent request is received. The k-server problem.
Other Topics (6 hours)
May include specialized models of computation, Kolmogorov complexity, derandomization, and other tools to support the application areas chosen by the instructor.