# 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: 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 optimality.

### Synopsis

Building on undergraduate CS300 (Introduction to Algorithms), the graduate-level course CS500 revolves around
the design and analysis of advanced algorithms.

More specifically we discuss, design, and analyze algorithms with respect to various *cost* measures *beyond* (sequential) runtime,
such as

- memory,
- parallel time,
- number of CPUs/gates,
- communication volume etc.

And we discuss, design, and analyze algorithms in various *modes* *beyond* the 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. Randomization (PPT, PDF)

6. Online/Competitive (PPT, PDF)

7. P/NP Intermission (PPT, PDF)

8. Approximation (PPT, PDF)

9. parallel Time (PPT, PDF)

10. Memory