CS 466 | SCS

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

References

Introduction to Algorithms, 2nd ed., by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGraw-Hill, 2001.

Schedule

Outline

Randomized Algorithms (6 hours)

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)

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.