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

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.

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

Classroom: E11 #311

Schedule: Tue+Thu 10h30~11h45am KST

Language: English only

Teaching Assistants: 허경 and 민승기

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

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

Midterm: April 18, 9h00~11h45 in E11 #304

Final exam: June 13, 9h00~11h45 in E11 #304

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

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

1. Recap, Intro & Overview (PPT, PDF)
9. Parallel Algorithms (PPT, PDF)
10. Memory-Efficient Algorithms (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)

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

With over 100 students enrolled, please refrain from contacting me by personal email.
Instead use KLMS to reach out to the TAs (preferred),
or write to the dedicated email address cs500@theoryofcomputation.asia.