Design and Analysis of Algorithms (CS500) in Spring 2017 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:

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: Tuesdays and Thursdays 4:00pm to 5:15pm

Language: English only

Teaching Assistants: 박세원, 조준희

Office hours: Mondays 4pm to 5:30pm and 6:30pm to 8:00pm in E3-1 #1434

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 Tuesday, April 18, from 16h00 to 18h30 in E11 #309 and #406
and a written final exam on Tuesday, June 13, from 16h00 to 18h30 in 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:

  For your convenience some of these books have been collected in KAIST's library 'on reserve' for this course.

Bloom's Taxonomy  

Synopsis/Slides

  1. Introduction
  2. Stable Matching
  3. Binomial Heaps
  4. Fibonacci Heaps with animation
  5. Union-Find
  6. Algorithmic Foundations of Swarm Robotics and Online Resource Leasing
    (guest lecture by Prof. Dr. Friedhelm Meyer auf der Heide, Heinz Nixdorf Institute & Department of Computer Science, University of Paderborn, Germany)
  7. Complexity Theory
  8. Randomization
  9. Approximation
  10. Conclusion
 

E-Learning: