Special Topics in Computer Science (CS492)

Advanced Algorithms

Fall Semester 2007

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!


Otfried Cheong. Office: E3-1 3434, Phone: 3542.

Teaching assistant:

Mira Lee


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.

Grading policy

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


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

The first two books go very deeply into the topic, and we will only cover the easier and introductory part of them. I do not expect students to buy the books (but you will have to make good notes during the class).

There are also very good resources on the web:

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

Course progress

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.

Bulletin board

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