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.

This entry was posted on Tuesday, August 14th, 2007 at 4:25 pm and is filed under Outline.