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 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.

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: Sewon Park, Junhee Cho, Ivan Koswara

Office hours: Every Tuesday and Thursday from 1600h to 1730h at E3-1, #2448

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 on Monday, April 16, from 9:00am to 11:45am, and a written final exam on Monday, June 11, same time.

Midterm Exam: The midterm exam will be held on Monday, April 16, from 9:00am to 11:45am. We use two lecture rooms. If your student id is less than 20175000, you are expected to take the midterm exam at E11, #309. If your student id is greater than 20175000, you are expected to take the exam at E11, #310.

Final Exam: The final exam will be held on Monday, June 11, from 9:00am to 11:45am. We use two lecture rooms. If your student id is less than 20173636, you are expected to take the final exam at E11, #310. If your student id is greater than 20173636, you are expected to take the final exam at E11, #309.

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

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
• Randomization
• Online/Competitive
• Complexity Theory
• Intermission: Global Identifiability of Parametric Differential Models by Prof. Chee K. Yap (New York University)
• Approximation
• Memory≈parallel Time
• Conclusion

E-Learning:

• KLMS
• First homework assignment in |ELICE, due Mar.16 9am.
• Homework #2 consists of four problems to be solved in groups of three and submitted in English handwriting before March 30 (Friday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1.
• Homework #3 consists of two problems to be solved in groups of three and submitted in English handwriting before April 13 (Friday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1.
• Guest Talk #1 and #2 by Prof. Mayer-Lindenberg (TU Hamburg-Harburg)
• Homework #4 consists of two problems to be solved in groups of three and submitted in English handwriting before May 11 (Friday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1; and one problem to be solved individually in |ELICE before May 11 (Friday)9am.
• Homework #5 consists of three problems to be solved in groups of three and submitted in English handwriting before May 23 (Wednesday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1.
• Homework #6 consists of Problems 14 and 15a to be solved in groups of three and submitted in English handwriting before June 6 (Wednesday) June 8 (Friday) 9am into the CS500 mail box next to the elevator on 3F of building E3-1; and of programming Problems 15b) to 15e) to be solved individually in |ELICE.