Course: The Theory of Computation (限在職專班生選修; This evening class is for part-time students of 在職專班 only.)

Fall semester, 2012

18:30 - 21:15 Tuesday, R439 CSIE Building.

3 credits

Web site: http://www.csie.ntu.edu.tw/~kmchao/theory12fall

Instructor: Kun-Mao Chao (趙坤茂)

Teaching assistant: Chia-Jung Chang (張家榮)

Classmates: I

Coursework:

    Homework assignments and Class participation (15%)

    Two midterm exams (70%; 35% each):

        1. Midterm #1: Oct. 30, 2012 (tentative)

        2. Midterm #2: Dec. 11, 2012 (tentative)

    Oral presentation of selected papers/topics (15%)

Topics:

• Sets, Relations, Languages

• Finite Automata

• Context-free Languages

• Turing Machines

• Undecidability

• Computational Complexity

• NP-completeness

• Related Topics

Supporting materials:

    First class (Sept. 11, 2012)

    Bell number (Sept. 12, 2012)

    Lecture notes I (Sept. 18, 2012) Read 1.1-1.5

    Lecture notes II (Sept. 25, 2012) Read 1.1-1.8

    Lecture notes III (Oct. 2, 2012) Read 1.1-1.8

    Lecture notes IV (Oct. 9, 2012) Read 1.8-2.1

    Lecture notes V (Oct. 16, 2012) Read 2.1-2.2

    Lecture notes VI (Oct. 23, 2012) Read 2.3-2.4

    Lecture notes VII (Nov. 6, 2012) Read 2.5-2.6

    Lecture notes VIII (Nov. 13, 2012 & Nov. 20, 2012) Read 3.1-3.2

    Lecture notes IX (Nov. 20, 2012 & Nov. 27, 2012) Read 3.3

    Lecture notes X (Nov. 27, 2012) Read 3.3-3.5

    Lecture notes XI (Dec. 4, 2012) Read 3.5, part of 4.1, 4.2, and 5.3

Please participate in the Reception of  The 23^rd International Symposium on Algorithms and Computation (ISAAC 2012) on Dec. 18, 2012.

Class presentations (Dec. 25, 2012):

7.4 Coping with NP-completeness (The last section of the book)

We even found a typo "They they ..." on the last page of this section.

Problem 7.4.6 (The last problem of the book)

Yes, we did solve the last problem together in class. Well done.