Design and Analysis of Algorithms (CS500) in Spring 2025 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 (=Science) from EE (=Engineering):

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

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 use,
• 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),
• approximation ratio etc.
  

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

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

Classroom: E11 #304

Schedule: Tue+Thu 16h00~17h30pm KST

Language: English only

Teaching Assistants: 현지훈+김소민+송민우 (use only this email address!)

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

Grading: 20% attendance, 20% quizzes/participation, 20% homework, 20% midterm, 20% final exam
Using this mix gives everyone the chance of passing with sufficient grade…

Midterm: April 15, 16h~18h45, E11 #304
Final Exam: June 10, 16h~18h45, E11 #304

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

Policies: Joining class no later than 10 minutes counts as full attendance,
no later than 30 minutes still counts as half attendance,
later than 30 minutes counts as unexcused absence.
Excused absence must be confirmed by the student's academic advisor via email.

• 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)

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

• KLMS
• ELICE
• YouTube
• Average-Case Analysis of QuickSort