Graduate Algorithms

The study of algorithms is, at one level, the study of techniques driven by rigorous formal analysis: divide and conquer, greedy algorithms, recursion, O() notation and the like. At another level, algorithms are about abstraction: what is the core computational structure underlying a problem, and how might we unlock it ?

In this course, we will study algorithms at the level of techniques, and at the level of structure. Formalization, a key step in the practice of using algorithms, will play an important role in this class. Specific topics to be covered include:

• NP-Completeness and reductions.
• Greedy algorithms (and matroids) and dynamic programming
• Linear programming
• Approximation algorithms.
• Randomization

Some of these topics (the last three most notably) can command an entire course of their own; our coverage will emphasize the basics, covering a few of the most common ideas in play.

Location/Time

Tue-Thu 2:00pm-3:20pm
WEB 1230

Course Material/Forums/Polls/Grading

For discussions, grading, general updates and other activities, please visit the class webpage for fall 2011.