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