CS 7880: Topics in Theories of Computer Science

Algorithmic Power Tools

This course will cover some of the major techniques developed for
solving hard algorithmic problems in Computer Science and related
domains.  We will present these techniques along with case studies
drawn from real-world motivations and diverse applications.  The
prerequisite for the course is that the students already have an
intermediate background in algorithms, i.e. big-Oh notation,
divide-and-conquer, greedy algorithms, dynamic programming,
NP-hardness, and basic probability theory.  The course is primarily
targeted for PhD students; interested MS students who have the
required background are also welcome and should consult the
instructor.

Since this is an advanced course, we will generally avoid
stress-inducing activities such as tests.  The main deliverables of
the course will be

(a) 2-3 problem sets

(b) A term project that involves research to be conducted in teams of
up to two and requires a final paper and presentation, and

(c) Class participation, including scribing one week's worth of
lectures.

Below we give a brief outline of the topics we will be covering.  More
details will be provided on a course webpage very soon.

1. Probabilistic Techniques (2 weeks)
   -- Basic probability theory
   -- Chernoff bounds
   -- The probabilistic method
   -- Lovasz Local Lemma and its applications

2. Linear Programming and its applications (4 weeks)
   -- Introduction
   -- Randomized rounding
   -- Deterministic rounding
   -- Primal-dual techniques
   -- Iterative rounding

   Case studies: 
   -- Graph bisection 
   -- Facility location, with applications to databases and network design
   -- Multicommodity flows with applications to network routing 

3. Metric embedding techniques (2 weeks)
   -- Reducing arbitrary metrics to tree metrics
   -- Hierarchical decompositions of metrics

   Case studies:
   -- Oblivious routing
   -- Various network design problems

4. Semi-definite Programming and its applications (3 weeks).
   -- Introduction
   -- Shannon capacity of a graph
   -- Rounding semi-definite programs

   Case studies: 
   -- Maximum cut of a graph 
   -- Graph bisection 

5. Term Project Presentations (2-3 weeks)