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: as opposed to a program or a heuristic. We thus call these 'virtues' and features distinguishing CS from EE (Electrical Engineering):

  • unambiguous problem specification
  • semantics of operational primitives
  • algorithm design (as prerequisite to 'coding'/implementing)
  • and analysis (correctness, cost)
  • with proof of optimality.

Synopsis

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

  • memory,
  • parallel time/depth,
  • size=#CPUs/gates,
  • communication volume,
  • #coin flips etc.

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

  • average-case,
  • expected,
  • amortized,
  • competitive (ratio),
  • approx. ratio 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
  • MIT OCW: Design and Analysis of Algorithms (2015)

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. Randomized/Expected Analysis (PPT, PDF)
6. Online/Competitive Analysis (PPT, PDF)
7. P/NP Intermission (PPT, PDF)
8. Approximation (PPT, PDF)
9. parallel Time (PPT, PDF)
10. Memory (PPT, PDF)

E-Learning: