This is an old revision of the document!

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=number of 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 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. 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: