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: