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.
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.
For specific information regarding this year’s incarnation of the class, please visit the corresponding class page:
- Fall 2014: CS 6150 Graduate Algorithms (TTh 10:45-12:05, WEB L105). NOTE: The class is completely full at this point, and I cannot give out permission codes because the room we’re in is full to capacity. I’d recommend sitting in on a lecture or two BEFORE the drop deadline on Sep 3, and then attempting to register if there are any withdrawals at that time. I’m sorry I can’t accomodate all your requests.