Theory of Computation (CS422) in Fall 2017 at KAIST's School of Computing

The Theory of Computation provides a sound logical foundation to computer science. By comparing various formal models of computation with respect to their capabilities, it identifies both fundamental features and ultimate limitations of contemporary digital computing machinery. Rigorous notions of efficiency are captured by famous complexity classes such as P and PSPACE; and concepts like oracles or polynomial-time reduction permit to compare computational problems with respect to their algorithmic cost: NP-hardness results thus serve as 'beacons' of intractability.
Lecturer: Martin Ziegler

Lectures: classroom #2112 in building E3

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

Language: English only

Teaching Assistant: Ivan Koswara

Office/claiming hour: Fridays 10:30am to 11:30am in E3 #3409

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

Grading: The final grade will be composed as follows (small changes reserved): Homework 20%, Midterm exam 30%, Final exam 40%, Attendance 10%.

Exams: There will be a midterm exam (Monday, Oct 16, 9h00-11h30, #2112) and a final exam (Monday, Dec 11, 9h00-11h30, #2112).



We make a special pedagogical effort to avoid the arduous Turing machine formalism and instead employ a variant of WHILE programs.
  1. Motivating Examples:
  2. Basic Computability Theory
  3. Advanced Computability
  4. Computational Complexity
  5. Structural Complexity / NPc
  6. PSPACE and Polynomial Hierarchy
  7. Advanced Complexity


Regularly recalling, applying, and extending the definitions, theorems, and proofs from the lecture is essential for comprehension and successful study. Therefore consider it as a courtesy that we will create homework assignments and publish them on this web page.  

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.

Students are required to submit the declaration of Academic Honour Code with their signature in the lecture on Friday, September 8 at 9am.



  You are expected to buy some of these (or similar) books — latest for the midterm exam: leaving you enough time to thoroughly browse and compare them in the library, first.