In this course we will discover some topics in algorithms that go beyond the standard material of the CS300 algorithms course.

In particular, we will cover two main topics: approximation algorithms, and randomized algorithms.

Many natural optimization problems are NP-hard, which means that very likely an efficient algorithm solving them exactly will never be found. In practice, people use heuristics to attack such problems -- but this always leaves the question on how good a solution one can really find. Approximation algorithms are algorithms that find a solution for which we can prove bounds on how good it is compared to the optimal solution.

Randomized algorithms make use of random numbers or random decisions to guide the progress of the computation. It is perhaps surprising how introducing random decisions can help to solve algorithmic problems, in particular if we insist on an exact solution -- but this is really the case. For some problems the simplest and most efficient algorithms are randomized.

If you liked CS300 Algorithms, then this course is for you!

The class meets Monday, Wednesday, and Friday from 10:00 to 10:50 in room 2443 in the Computer Science Building (E3-1). Lectures are given in English.

Students will be graded based on homeworks and one or two quizzes.

The course will make use of material from the following books:

- Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag 2001.
- Michael Mitzenmacher and Eli Upfal. Probability and Computing. Cambridge University Press 2005.
- Jon Kleinberg and Eva Tardos. Algorithm Design. Addison-Wesley 2005.

There are also very good resources on the web:

- Jeff Erickson's lecture notes,
- Samir Khuller's course on Combinatorial Optimization,
- Samir Khuller's algorithms course,
- A compendium of NP optimization problems
- Mark de Berg's advanced algorithms course

We will make use of lecture notes available on the web, and I will make printouts of material available as well.

Here is a rough list of what we will cover in each week of the semester.

Week 1 | Introduction |

Week 2 | Nuts and bolts |

Week 3 | Treaps |

Week 4 | Minimum enclosing disks |

Week 5 | Maximum flow and minimum cuts |

Week 6 | Randomized minimum cuts |

Week 7 | Binary space partitions |

Week 8 | Midterm exam week |

Week 9 | Set cover |

Week 10 | Steiner tree and TSP |

Week 11 | The Knapsack problem |

Week 12 | LP-Duality |

Week 13 | Dual fitting |

Week 14 | The Primal-Dual method |

Week 15 | Optimal sorting |

Week 16 | Final Exam week |

The material covered in the lectures so far:

09-03 | Introduction | |

09-05 | Paranoid Maximum algorithm, random variables | |

09-07 | Minidisk algorithm | Notes |

09-10 | Minidisk algorithm | |

09-12 | Nuts and bolts I | Notes |

09-14 | Nuts and bolts II | |

09-17 | Treaps I | Notes |

09-19 | Treaps II | |

09-21 | Skip lists | |

No class (Chuseok week) | ||

10-01 | Markov's inequality, independent random variables | |

10-05 | Chernoff's bound, depth of a treap | |

10-08 | Hashing | Notes |

10-10 | Universal hashing | |

10-12 | Balls and bins | |

10-15 ~ 10-19 | No class (I'm in France) | |

10-22 ~ 10-26 | No class (midterm week) | |

10-29 | Diameter approximation | Notes |

10-31 | Diameter approximation | |

11-02 | No class (Computing conference) | |

11-05 | Vertex cover | Vazirani 1.1 |

11-07 | Set cover | Vazirani 2.1 |

11-09 | Shortest superstring | Vazirani 2.3 |

11-12 | Weighted vertex cover | Vazirani 2.2 |

11-14 | Metric TSP | Vazirani 3.2, Notes |

11-16 | No class (Fall workshop) | |

11-19 | Christofides' algorithm | |

11-21 | Knapsack with rounding | Notes |

11-23 | k-Center | David Mount's notes, page 81-85 |

11-26 | Linear programming relaxation, weighted vertex cover by rounding | Vazirani 14.1, Notes |

11-28 | Half-integrality of vertex cover, Randomized set cover | Vazirani 14.3, 14.2 |

11-30 | Linear programs and their dual | Vazirani 12.1 |

12-03 | Max-flow as a linear program | Vazirani 12.2 |

12-05 | Set-cover via dual fitting | Vazirani 13.1 |

12-07 | Constrained set multicover | Vazirani 13.2.1 |

12-10 | The primal-dual schema | Vazirani 15.1, 15.2 |

12-12 | Exercise 15.6 in Vazirani (page 129) | |

12-14 | Homework discussion |

There will be several homework assignments in this course. You will
have about *one to two weeks* to complete an assignment.
Homeworks can be turned in in either *Korean* or *English*.
Homeworks must be submitted *on paper* and should be deposited in
the homework box.

- Homework 1, deadline Sept 20.
- Homework 2, deadline October 8.
- Homework 3, deadline October 26.
- Homework 4, deadline November 19.
- Homework 5, deadline November 27.
- Homework 6, deadline December 4.
- Homework 7, deadline December 13.

We have a bulletin board for announcements and discussions. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)

Otfried Cheong