We will study the design and analysis of algorithms for problems that appear in many areas of computer science.
The following is a list of topics that I'll try to cover in this course:
박지원, 송현지, 도현우, 안성근.
The class meets Wednesday and Friday from 9:00 to 10:15 in classroom #301 of the Creative Learning Building (E11).
Since this is rather early, attendance will be taken at the beginning of the class. There will be no attendance credit if you are late.
Attendance will be taken in nearly every class. If you miss at most 3 lectures, you receive 10 attendance points. For 4 missed lectures, you receive 9 attendance points, and so on. For 13 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 three free missed classes for this.
Lectures are given in English.
The final grade will be composed as follows (small changes reserved):
There will a midterm exam and a final exam.
The midterm exam will be on Monday, April 20, from 9:00 to 11:45 in the joint lecture hall (room 1501) of the CS building (E3-1).
The final exam will be on Monday, June 15, from 9:00 to 11:45 in the joint lecture hall (room 1501) of the CS building (E3-1).
Here is a rough list of what we will cover in each week of the semester.
| Week 1 | Introduction, Problem reductions |
| Week 2 | Some basic problems, The classes P and NP, NP-hardness |
| Week 3 | Proving problems NP-hard |
| Week 4 | Dynamic programming |
| Week 5 | Network flow |
| Week 6 | Network flow |
| Week 7 | Mincost flow |
| Week 8 | Midterm exam |
| Week 9 | Linear Programming |
| Week 10 | Linear Programming |
| Week 11 | Approximation algorithms |
| Week 12 | Approximation algorithms |
| Week 13 | Local search |
| Week 14 | Local search |
| Week 15 | Reserve |
| Week 16 | Final Exam |
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 :-), but you make it easier for me if you write in English.
To ask questions, you need to register on Piazza and enroll as a student for CS500. To do so, go to the CS500 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 are not following a specific text book. I will make pointers to lecture notes and other on-line materials available during the course.
In particular, I'm using the following resources to prepare the lecture materials:
If you want to buy a book to review undergraduate algorithms and to help you with studying the material of this course, I recommend one of these two:
The material covered in the lectures:
| 03-04 | Introduction | slides | |
| 03-06 | Lecture by Eric Vigoda: Introduction to Markov Chain Monte Carlo Methods | slides | |
| 03-11 | Lecture by Eric Vigoda: Approximating the Permanent | slides | |
| 03-13 | No class | ||
| 03-18 | Reductions: IndependentSet, Clique, VertexCover, SetCover | slides, scribbles | |
| 03-20 | Reductions: Coloring, Hamiltonian Path | slides, scribbles | |
| 03-25 | Reductions: SubsetSum, SAT, 3SAT | slides, scribbles | notes (*) |
| 03-27 | NP-completeness | slides, scribbles | |
| 04-01 | NP-completeness, weakly NP-hard problems | scribbles | |
| 04-03 | Traveling Salesman | slides scribbles | |
| 04-08 | Approximation algorithms for Makespan and SetCover | slides scribbles | Jeff Erickson's lecture notes |
| 04-10 | Classroom change: 301 in CLB! PTAS for Subset Sum, FPT for Vertex Cover | slides 1, slides 2 | |
| 04-15 | Introduction to network flow | slides | Jeff Erickson's lecture notes |
| 04-17 | Ford-Fulkerson algorithm, Max-flow min-cut theorem, capacity scaling | ||
| 04-20 | Midterm exam, Monday, April 20, 9:00–11:45 in 1501, E3-1 | ||
| 04-29 | Analysis of capacity scaling, bipartite Matchings, Hall's theorem | slides | Jeff Erickson's lecture notes |
| 05-01 | Menger's theorem, edge disjoint paths, non-integer capacities | bad example slides | |
| 05-06 | Edmonds-Karp algorithm, Circulations | slides, slides | |
| 05-08 | Flow applications | slides, slides | |
| 05-13 | I/O-efficient algorithms, merge sort | slides | book |
| 05-15 | I/O-efficient techniques | slides | |
| 05-20 | No class | ||
| 05-22 | Linear programming: Canonical and Slack forms | lecture notes | |
| 05-27 | Linear programming applications, duality | slides | |
| 05-29 | Duality Theorem, LP Algorithms | slides | |
| 06-03 | IP, Approximation algorithm for weighted vertex cover by relaxing and rounding | slides | |
| 06-05 | |||
| 06-10 | No class | ||
| 06-12 | No class | ||
| 06-15 | Final exam, Monday, June 15, 9:00–11:45 in 1501, E3-1 | ||
(*) from Jeff Erickson's lecture notes.
There will be several homework assignments. You will have about one week to complete the assignment. Homeworks can be turned in in either Korean or English, and must be submitted before midnight (23:59 pm) on the day of the deadline.
Please submit your homework in the homework box next to classroom 1 (room 1101) on the ground floor in the computer science building (E3-1).
You can work in groups of up to three students, and each group only needs to submit one solution. Groups are allowed to change between homeworks.
Researching on the internet is highly discouraged. In any case, you or your group must write up your solution by yourself, and you must acknowledge all sources used for your solution (webpages, books, discussions with students not in your group).
Note: If the problem asks you to give an algorithm, this implies that you must prove that your algorithm is correct. If the problem asks for an algorithm with a specific running time—for example, a linear-time algorithm—then you must prove that your algorithm has indeed this running time.