Special Topics in Theory

Topics classes in systems vary from year to year. The following are some classes that have been offered in the past or are expected to be offered in the future:

Computational Geometry — Design of efficient algorithms for problems defined on geometric objects, such as points, lines, polygons, surfaces, etc; fundamental problems such as point location, intersection, proximity, convex hulls; applications to other fields such as computer graphics, computer-aided design, geographic information systems, and robotics.

Advanced Algorithms — This course covers a broad spectrum of advance algorithm. Topics include amortized complexity, randomized algorithms, multidimensional searching, string processing, graph algorithms, intractability, NP-completeness, approximation algorithms.

Randomized Algorithms I — Begins with a brief introduction on probability theory and present basic tools from probabilistic analysis recurring in algorithmic applications. Topics include game-theoretic techniques, moments and deviations, tail inequalities, and Markov chains and random walks.

Randomized Algorithms II — Focuses on applications of randomized algorithms involving data structures, graph algorithms, geometric algorithms, number theoretic algorithms, counting algorithms, parallel and distributed algorithms and online algorithms.

Performance Modeling II — Cores the application of performance modeling techniques to real systems. Application topics include networks, computer architecture, distributed systems and databases.

Distributed Algorithms — Gives an introduction to various distributed algorithms and a detailed discussion on their analysis. Algorithms to be discussed include communication protocols, routing algorithms, packet switching, traversal algorithms, election algorithms, termination detection, anonymous networks, snapshots.