Design and Analysis of Algorithms (CS500) in Spring 2016 at KAIST's School of Computing

All Computer Science is based on the concept of an efficient algorithm: a finite sequence of primitive instructions that, when executed according to their well-specified semantics, provably provide a mechanical solution to the infinitely many instances of a complex mathematical problem within a guaranteed number of steps of least asymptotic growth. We thus call these the 'virtues' of Theoretical Computer Science:

Building on undergraduate CS300 (Introduction to Algorithm), the graduate-level course CS500 discusses the design of advanced algorithms and analyzes their behaviour with respect to various notions of performance such as worst-case, amortized, expected, and competitive. Their practical impact is demonstrated in selected implementations.

Instructor: Martin Ziegler

Lectures: classroom #309 in building E11 (Creative Learning)

Schedule: Tuesdays and Thursdays 2:30pm to 3:45pm

Language: English

Teaching Assistants: 박세원, 이원영, 임준성, 최규현

Office hours: Tuesdays 4pm to 5:30pm and from 6:30pm, E3-1 #1434

Attendance: 10 points for missing less than 5 lectures, 9 when missing 5 lectures, 8 when missing 6, and so on: 14 or more missed lectures earn you no attendance points.

Grading: The final grade will (essentially) be composed as follows: Homework 20%, Midterm exam 30%, Final exam 40%, Attendance 10%.
≥95% for A+, ≥90% for A0, ≥85% for A-, ≥80% for B+, ≥75% for B0, ≥70% for B-, ≥65% for C+, ≥60% for C0: GPA=3.11

Exams: There will be a midterm exam on April 21 and a final exam on June 16,
both from 13h00 to 15h00 in E11 #309 (student ID ≥ 20163025) and #311 (student ID < 20163025)

Guest tutorial by Professor Neil Immerman on Descriptive Complexity on May 10 and 12 (section 5)!

PhD qualifying exam problems from Jul 1, 2016 and from Jan 13, 2017



CS204 (Discrete Mathematics), CS206 (Data Structures), CS300 (Introduction to Algorithms)  


Receptive learning and reproductive knowledge do not suffice for thorough understanding. Hence, for students' convenience, we will regularly offer homework assignments; and encourage their solution by having them enter into the final grade. Submit your solutions by the due time into the box #16 next to the elevator on 3F of building E3-1.
Late submission policy: none.



  For your convenience some of these books have been collected in KAIST's library 'on reserve' for this course.



  1. Introduction
  2. Stable Matching
  3. Binomial Heaps
  4. Fibonacci Heaps
  5. Union-Find
  6. Complexity Theory
  7. Randomization
  8. Approximation
  9. Online (?)
  10. Conclusion