Important dates

• 2023/02/27 和平紀念日 彈性放假

• 2023/03/25 補課 (4/3 調整放假)

• 2023/04/03 兒童節/民族掃墓節 調整放假

• 2023/04/10 Midterm exam

• 2023/06/05 Final exam

Info

• Course: Computation Theory

• Semester: 111-2

• Credit: 3 

• Time: Mon 9:10-12:10

• Classroom: 理圖003  理圖002  

Textbook

• Michael Sipser. Introduction to the Theory of Computation, 3/e. CENGAGE Learning.

Reference

• Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press.

  • https://theory.cs.princeton.edu/complexity/

Prerequisite

• Discrete mathematics (undergraduate level)

• Algorithm (undergraduate level)

Grading

• Midterm 40% (in class)

• Final 40% (in class)

• Participation 20%

Syllabus

• Introduction (last update: 2023/02/20) 

• Regular languages (last update: 2023/03/13) annotation in class

• The Church-Turing thesis  (last update: 2023/03/27)

• Decidability (last update: 2023/03/27)

• Reducibility  (last update: 2023/04/24)

• Time complexity (last update: 2023/05/01)

• Space complexity (last update: 2023/05/22)

• Intractability (last update: 2023/05/29)

• Selected topics