suresh at cs utah edu
Ph: 801 581 8233
Room 3404, School of Computing
50 S. Central Campus Drive,
Salt Lake City, UT 84112.

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.


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.