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

  • full and unambiguous problem specification
  • formal semantics of operational primitives
  • algorithm design (as opposed to 'programming')
  • and analysis (correctness, asymptotic cost)
  • with proof of asymptotic optimality.

Synopsis

Building on undergraduate CS300 (Introduction to Algorithms), 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,
  • average-case,
  • expected, and
  • amortized runtime;
  • memory use,
  • competitive ratio,
  • approximation ratio etc.

Their practical impact is demonstrated in selected implementations.

Administration:

Lecturer: Martin Ziegler

Classroom: Online

Schedule: Tuesdays and Thursdays, 9:00am to 10:30am
Lectures start from March 17th.

Language: English only

Teaching Assistants: 임동현 (klimdhn@kaist.ac.kr), Ivan Koswara (chaoticiak@kaist.ac.kr)

Homework: Handwritten individual solutions (English only) and programming assignments in ELICE.

Grading: In view of the recent switch to online teaching and cancelled midterm, the final grade is determined to 50% from homework and 50% from final exam.

Midterm: cancelled
Final exam: TBD

Prerequisites: CS204 (Discrete Mathematics), CS300 (Introduction to Algorithms)

Literature

  • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (3rd Edition), MIT Press (2009).
  • Dasgupta, Papadimitriou, Vazirani: Algorithms, McGraw-Hill (2006).
  • Kleinberg, Tardos: Algorithm Design, Pearson (2006).
  • Vöcking, Alt, Dietzfelbinger, Reischuk, Scheideler, Vollmer, Wagner: Algorithms Unplugged, Springer (2011).
  • Introduction to the Analysis of Algorithms (Robert Sedgewick and Philippe Flajolet)
  • Online Computation and Competitive Analysis (Allan Borodin and Ran El-Yaniv)
  • Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Michael Mitzenmacher and Eli Upfal)
  • M. Sipser: Introduction to the theory of computation, Boston (1997)
  • R. Sedgewick: Algorithms

Syllabus/Slides

0. Preliminaries (pdf,ppt,video)
1. Introduction (pdf,ppt,video)
2. Examples (pdf,ppt,video)
3. Tree Data Structures (pdf,ppt,video1,video2,video3,video4)
4. Amortized Analysis (pdf,ppt,video1,video2,video3,video4,video5,bonus)
5. Randomization (pdf,ppt,video1,video2,video3)
6. Online/Competitive (pdf,ppt,video1,video2,video3)
7. Complexity Theory (pdf,ppt,video1,video2)
8. Approximation (pdf,ppt,video1,video2,video3)
(9. Memory≈parallel Time)
10. Conclusion (pdf,ppt)

E-Learning: