Algorithms (F2008)

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:

• Algorithmic paradigms like divide and conquer, greedy algorithms, and dynamic programming
• Flow algorithms
• Randomization
• NP Completeness, and reductions
• Approximation algorithms (and a brief intro to linear programming)
• Miscellaneous topics

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.

The textbook will be Algorithm Design, by Jon Kleinberg and Eva Tardos (it’s linked in the sidebar to the right)

This entry was posted on Friday, July 25th, 2008 at 2:23 pm and is filed under news, syllabus.