Algorithms Design and Analysis (CS500)

Spring Semester 2015

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:

Course information

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

박지원, 송현지, 도현우, 안성근.

Lectures

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.

Grading policy

The final grade will be composed as follows (small changes reserved):

  • Homework (20%), Midterm exam (30%), Final exam (40%), Participation (10%).
Exams

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

Syllabus

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

Piazza

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.

Text book, lecture notes, slides

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:

  • Algorithms by Dasgupta, Papadimitriou, Vazirani. The international edition is quite inexpensive, and there is also a Korean translation.
  • Algorithm Design, by Jon Kleinberg and Éva Tardos.

Course progress

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.

Homework

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.