This is an old revision of the document!


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

Synopsis

Building on undergraduate CS300 (Introduction to Algorithms), the graduate-level course CS500 discusses the design of advanced algorithms and analyzes their behaviour with respect to various notions of performance such as

  • worst-case,
  • average-case,
  • expected, and
  • amortized runtime;
  • memory use,
  • competitive ratio,
  • approximation ratio etc.

Their practical impact is demonstrated in selected implementations.

Administration:

Lecturer: Martin Ziegler

Classroom: Online

Schedule: Tuesdays and Thursdays, 9:00am to 10:30am
Lectures start from March 17th.

Language: English only

Teaching Assistants: 임동현 (klimdhn@kaist.ac.kr), Ivan Koswara (chaoticiak@kaist.ac.kr)

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

Grading: In view of the recent switch to online teaching and cancelled midterm, the final grade is determined to 50% from homework and 50% from final exam.

Midterm: cancelled
Final exam: TBD

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)
  • R. Sedgewick: Algorithms

Syllabus/Slides

0. Preliminaries (pdf,ppt,video)
1. Introduction (pdf,ppt,video)
2. Examples (pdf,ppt,video)
3. Tree Data Structures (pdf,ppt,video1,video2,video3,video4)
4. Amortized Analysis (pdf,ppt,video1,video2,video3,video4,video5,bonus)
5. Randomization (pdf,ppt,video1,video2,video3)
6. Online/Competitive (pdf,ppt,video1)
7. Complexity Theory
8. Approximation
9. Memory≈parallel Time
10. Conclusion

E-Learning: