CSG399: 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.

The course will be co-taught by Profs. Rajmohan Rajaraman and Ravi
Sundaram.  There will be no exams.  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.

The course is part of a two-course series that will be continued in
the Spring.  Prof Rajaraman is the person in charge of the Fall 07
course and you can approach him regarding any administration related
issues.  Prof. Sundaram will be in charge of the Spring 08 course.
(The Fall 07 course will not be a prerequisite for the Spring 08
course.)

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

1. Linear Programming and its applications (4 weeks). 
   -- Introduction
   -- Randomized rounding
   -- Deterministic rounding
   -- Primal-dual techniques
   
   Case studies: 
   -- Graph bisection 
   -- Facility location, with applications to databases and network design
   -- Multicommodity flows with applications to network routing

2. 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 

3. Geometric Techniques (2 weeks)
   -- Introduction
   -- Geometric structure of polytopes

   Case studies: 
   -- Weak perfect graph theorem 
   -- Sorting partially ordered sets 

4. Probabilistic Techniques (3 weeks).
   -- Random sampling
   -- Random walks
   -- Markov chains

   Case studies: 
   -- Fingerprinting
   -- Estimating the volume of a convex body 
   -- HITS algorithm and Google's PageRank

5. Term Project Presentations (2-3 weeks)

In Spring 08 we plan to cover:

1. Fourier techniques
2. Linear algebraic techniques
3. Distributed computing
4. Techniques based on expander graphs
5. Learning algorithms and information retrieval