In memoriam Jirka Matoušek
This course covers various topics related to algorithms and the use of probability in algorithms and combinatorics.
The following is a list of topics that we will cover:
The class meets Monday and Wednesday from 13:00 to 14:15 in room 3435 in building E6. Lectures are given in English.
The final grade will be composed as follows (small changes reserved):
Attendance will be taken in nearly every class. If you miss at most 4 lectures, you receive 10 attendance points. For 5 missed lectures, you receive 9 attendance points, and so on. For 14 or more missed lectures you receive no attendance points.
Going to a conference, workshop, doctor, interview, is no excuse for missing the class — you can use the four free missed classes for this.
There will be a midterm and a final exam.
The midterm exam will be on October 19, 13:00 to 15:30, in room 1501 in building E3-1.
This term we will be using Piazza for class announcements, discussion, and asking questions.
Here is our Piazza class page.
You are responsible for checking the announcements on our Piazza class page regularly (if you make a Piazza account and enroll for the course, announcements will be mailed to you automatically.)
If you do not understand something, it is important that you ask questions. Piazza allows you to ask questions and get answers from the instructor, the teaching assistants, and your classmates. You can ask questions anonymously, so don't be shy and ask!
Both Korean and English are acceptable on Piazza :-). You make it easier for me if you write in English, but if the TAs can answer your question, then Korean is just fine.
To ask questions, you need to register on Piazza and enroll as a student for CS492B. To do so, go to the CS492B enrollment page. Select "Join as student". You will then need to use your KAIST email address (ending with @kaist.ac.kr) to create an account.
We will use lecture notes written by Emo Welzl, Jirka Matoušek, and Robin Moser at ETH Zürich. These will be made available to students in the class.
We will also make some use of the book Linear Programming by Gärtner and Matoušek. It is available online through the KAIST library.
The material covered in the lectures so far:
| 08-31 | Introduction, random search tress | slides, 1.1, Exercise 1.5, 1.2 |
| 09-02 | Expected total depth and height | 1.2, 1.3 |
| 09-07 | Expected depth of individual keys | 1.4, Exercises 1.15, 1.28 |
| 09-09 | Quicksort and Quickselect | 1.5, 1.6, Exercises 1.36, 1.41 |
| 09-14 | Randomized Search Trees (Treaps) | 1.7 |
| 09-16 | BasicMinCut | 2.1, 2.2, 2.3 |
| 09-21 | MinCut | 2.4 |
| 09-23 | Checking matrix multiplication, Schwartz-Zippel theorem | 3.1, 3.2 |
| 09-28 | No class (Chuseok) | |
| 09-30 | Checking perfect bipartite matching | 3.3 |
| 10-05 | Checking perfect matching in general graphs | 3.4 |
| 10-07 | Counting perfect matchings in planar graphs | 3.6 |
| 10-12 | Counting perfect matchings in planar graphs | 3.6 |
| 10-14 | Homework 1 review | |
| 10-19 | Midterm exam 13:00 to 15:00 in room 1501 (E3-1) | |
| 10-26 | Linear Algebra in combinatorics (Miniatures 26 and 4) | |
| 10-28 | Lovász Local Lemma | 4.1 |
| 11-02 | Lovász Local Lemma | 4.2 |
| 11-04 | Introduction to linear programming | 5.1, 5.2 |
| 11-09 | No class (business trip) | |
| 11-11 | No class (business trip) | |
| 11-16 | No class (business trip) | |
| 11-18 | Basic feasible solutions | 5.2, 5.3 |
| 11-23 | Farkas Lemma, Introduction to duality | 5.5.1 |
| 11-25 | No class (KAIST closed for interviews) | |
| 11-30 | Strong duality theorem, Ellipsoid method I | 5.5.2, 5.6.1 |
| 12-02 | Bit complexity of LP, Ellipsoid algorithm | 5.4, 5.6.3 |
| 12-07 | Geometry of ellipsoids, homework review | 5.6.2 |
| 12-09 | Combinatorial Linear Programs | 5.7, 5.8 |
| 12-14 | Final exam 13:00 to 15:00 in room 1501 (E3-1) | |
There will be a few homeworks in this course. You will have 1 to 2 weeks to complete the homework.