Design and Analysis of Algorithms (CS500) in Spring 2017 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.

Lecturer: Martin Ziegler

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

Schedule: Tuesdays and Thursdays 4:00pm to 5:15pm

Language: English only

Teaching Assistants: 박세원, 조준희

Office hours: Mondays 4pm to 5:30pm and 6:30pm to 8:00pm in E3-1 #1434

Attendance: 10 points for missing less than 15% of the lectures, 9 when missing <19%, 8 when missing <23%, and so on: 50% or more misses earn you no attendance points.
(No need to get excused for conference or doctor's visits etc.: This is what the free misses are for...)

Grading: The final grade will (essentially) be composed as follows: Attendance 10%, Homework 10%, Quiz 10%, Midterm exam 30%, Final exam 40%.

Exams: There will be a written midterm exam on Tuesday, April 18, from 16h00 to 18h30 in E11 #309 and #406
and a written final exam on Tuesday, June 13, from 16h00 to 18h30 in E11 #309.



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 #18 next to the elevator on 3F of building E3-1.  

Academic Honesty

Late homework submissions will be ignored (for grading: you could still win an award). Copied homework solutions receive 0 points. Cheating during the exam results in expulsion and 0 points.



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

Bloom's Taxonomy  


  1. Introduction
  2. Stable Matching
  3. Binomial Heaps
  4. Fibonacci Heaps with animation
  5. Union-Find
  6. Algorithmic Foundations of Swarm Robotics and Online Resource Leasing
    (guest lecture by Prof. Dr. Friedhelm Meyer auf der Heide, Heinz Nixdorf Institute & Department of Computer Science, University of Paderborn, Germany)
  7. Complexity Theory
  8. Randomization
  9. Approximation
  10. Conclusion