Design and Analysis of Algorithms (CS500) in Spring 2016 at KAIST's School of Computing

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

Instructor: Martin Ziegler

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

Schedule: Tuesdays and Thursdays 2:30pm to 3:45pm

Language: English

Teaching Assistants: 박세원, 이원영, 임준성, 최규현

Office hours: Tuesdays 4pm to 5:30pm and from 6:30pm, E3-1 #1434

Attendance: 10 points for missing less than 5 lectures, 9 when missing 5 lectures, 8 when missing 6, and so on: 14 or more missed lectures earn you no attendance points.

Grading: The final grade will (essentially) be composed as follows: Homework 20%, Midterm exam 30%, Final exam 40%, Attendance 10%.
≥95% for A+, ≥90% for A0, ≥85% for A-, ≥80% for B+, ≥75% for B0, ≥70% for B-, ≥65% for C+, ≥60% for C0: GPA=3.11

Exams: There will be a midterm exam on April 21 and a final exam on June 16,
both from 13h00 to 15h00 in E11 #309 (student ID ≥ 20163025) and #311 (student ID < 20163025)

Guest tutorial by Professor Neil Immerman on Descriptive Complexity on May 10 and 12 (section 5)!

PhD qualifying exam problems from Jul 1, 2016 and from Jan 13, 2017

Prerequisites

Homework/Assignments

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

Synopsis

0. Introduction
1. Stable Matching
2. Binomial Heaps
3. Fibonacci Heaps
4. Union-Find
5. Complexity Theory
6. Randomization
7. Approximation
8. Online (?)
9. Conclusion

E-Learning:

• KAIST Learning Management System
• Slides of §0, §1, §2, §3, §4, §5, §6, §7, and §9.
• Initial self-assessment, due by Monday (March 7) 9am.
  (Box #16 next to the elevator on 3F of building E3-1)
• Homework #1 is a programming assignment in /* elice */
• Homework assignment #2 for download.
  The solution is due by April 7 2pm in groups of 2 or 3 (Box #16 next to the elevator on 3F of building E3-1). Please indicate your and your (1 or 2) fellow students' IDs as comments in KLMS until Wednesday (March 30) night.
  We will have a paper quiz on April 7: Everyone is randomly assigned one of the problems 7 to 9 and there receives the minimum of i) the number of points scored there and ii) those scored on the problem in aforementioned joint submission.
• Assignment for midterm (April 21st): Research some contemporary female computer scientist's biographical data and contributions to summarize in two sentences.
• Homework assignment #3 for download,
  solutions in groups of 3 due by May 10, 2pm, in aforementioned box #16.
• Professor Immerman's slides of May 10 and 12
• Homework assignment #4 for download,
  solutions in groups of 3 due by May 31, 2pm, in aforementioned box #16.
• The final homework #5 again includes a programming assignment in /* elice */ and is to be solved individually.
• Slides with animations (password protected from modification)
• Congratulations for your performance on the final exam!