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

Synopsis

Building on undergraduate CS300 (Introduction to Algorithms), the graduate-level course CS500 revolves around the design and analysis of advanced algorithms.
More specifically we discuss, design, and analyze algorithms with respect to various cost measures beyond (sequential) runtime, such as

  • memory,
  • parallel time,
  • number of CPUs/gates,
  • communication volume etc.

And we discuss, design, and analyze algorithms in various modes beyond the worst-case, such as

  • average-case,
  • expected,
  • amortized,
  • competitive etc.

The practical impact of these algorithms is demonstrated in selected implementations.

Administration:

Lecturer: Martin Ziegler (use only this email address!)

Classroom: Online

Schedule: Tue+Thu 10h30~11h45am KST

Language: English only

Teaching Assistants: 현지훈 and 박정호

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

Grading: 40% attendance/quizzes, 20% homework, 20% midterm, 20% final exam

Midterm: April 20, 9h00~11h45 in E3-1 #1501

Final exam: June 15, 9h00~11h45 in E3-1 #1501

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)
  • E. Vigoda: Graduate Algorithms
  • R. Sedgewick: Algorithms
  • Coursera: Data Structures and Algorithms

Syllabus/Slides

0. Summary (PPT, PDF)
1. Introduction (PPT, PDF)
2. Tree Data Structures (PPT, PDF)
3. Average-Case Analysis (PPT, PDF)
4. Amortized Analysis (PPT, PDF)
5. Randomization (PPT, PDF)
6. Online/Competitive (PPT, PDF)
7. P/NP Intermission (PPT, PDF)
8. Approximation (PPT, PDF)
9. parallel Time (PPT, PDF)
10. Memory

E-Learning: