Spring 2006: Design and Analysis of Algorithms

Spring 2005: Design and Analysis of Algorithms

22C:231, Sec 001

Time and Place: 2.30--3.45, TTh, 214 MLH

This is the graduate algorithms course. This time, our discussion will, after some introduction, revolve around five broad themes -- (1) Randomized algorithms (2) greedy algorithms and dynamic programming (3) network optimization - flows, matching, arborescences (4) NP-completeness (5) Approximation or approximate optimization.

Our text will be Kleinberg and Tardos' Algorithm Design.

We will assume an exposure to an algorithms course at the undergraduate level. In particular, we will assume familiarity with basic data structures such as priority heaps and binary search trees, and basic graph algorithms such as breadth-first-search and depth-first-search.