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

Building on undergraduate CS300 (Introduction to Algorithm), 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, amortized, expected, and competitive. Their practical impact is demonstrated in selected implementations.

Lecturer: Martin Ziegler

Lectures: classroom #309 in building E11 (Creative Learning)

Schedule: Wednesdays and Fridays 9:00am to 10:30am

Language: English only

Teaching Assistants: TBC

Office hours: TBC

Attendance: 10 points for missing less than 15% of the lectures, 9 when missing <19%, 8 when missing <23%, and so on: 50% or more misses earn you no attendance points. (No need to get excused for conference or doctor's visits etc.: This is what the free misses are for…)

Grading: The final grade will (essentially) be composed as follows: Attendance 10%, Homework 10%, Quiz 10%, Midterm exam 30%, Final exam 40%.

Exams: There will be a written midterm exam and a written final exam.

Prerequisites CS204 (Discrete Mathematics), CS206 (Data Structures), CS300 (Introduction to Algorithms) Homework/Assignments Receptive learning and reproductive knowledge do not suffice for thorough understanding. Hence, for students' convenience, we will regularly offer homework assignments; and encourage their solution by having them enter into the final grade. Submit your solutions by the due time into the box #18 next to the elevator on 3F of building E3-1. Academic Honesty Late homework submissions will be ignored (for grading: you could still win an award). Copied homework solutions receive 0 points. Cheating during the exam results in expulsion and 0 points.

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)
For your convenience some of these books have been collected in KAIST's library 'on reserve' for this course.

Synopsis/Slides

• Introduction
• Stable Matching
• Binomial Heaps
• Fibonacci Heaps with animation
• Union-Find
• Complexity Theory
• Randomization
• Approximation
• Conclusion

E-Learning: