Graduate Algorithms

Fundamental topics in algorithm design and analysis: Asymptotic notations, divide-and-conquer, dynamic programming, greedy algorithms, and graph algorithms. Advanced topics to be drawn from: Concentration bounds, probabilistic methods, random walks and expander graphs, randomized algorithms, linear programming and semidefinite programming, duality and its applications in approximation algorithms, multiplicative weight update methods, online algorithms and competitive analysis, advanced data structures, parallel and distributed algorithms, quantum algorithms. Prerequisites: basic data structures at the level of CS2; undergraduate discrete mathematics at the level of CSCI 2243 Logic & Computation; undergraduate probability at the level of CSCI 2244 (Randomness & Computation).