Course: The Theory of Computation

Fall semester, 2013

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

3 credits

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

Instructor: Kun-Mao Chao (趙坤茂)

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

(限在職專班生選修; This evening class is for part-time students of 在職專班 only. 本課程不列入資工系資格考核心課程。)

Classmates: I

Coursework:

    Homework assignments and Class participation (10%)

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

        1. Midterm #1: Oct. 29, 2013 (tentative)

        2. Midterm #2: Dec. 10, 2013 (tentative)

    Oral presentation of selected papers/topics (20%)

Topics:

• Sets, Relations, Languages

• Finite Automata

• Context-free Languages

• Turing Machines

• Undecidability

• Computational Complexity

• NP-completeness

• Related Topics

Supporting Materials:

    First class (Sept. 10, 2013)

    Sets, Relations, and Functions (Sept. 17, 2013) [Read 1.1-1.3]

    Some Proof Techniques (Sept. 17, 2013; Sept. 24, 2013) [Read 1.4-1.5]

        -- Yet Another Proof: I  II (Oct. 1, 2013) More

    Closures (Sept. 24, 2013; Oct. 1, 2013) [Read 1.6]

    Alphabets & Languages (Oct. 8, 2013) [Read 1.7]

    Regular Expressions (Oct. 8, 2013) [Read 1.8]

    Deterministic Finite Automata (Oct. 8, 2013; Oct. 15, 2013) [Read 2.1]

    Nondeterministic Finite Automata (Oct. 15, 2013; Oct. 22, 2013) [Read 2.2]

    Finite Automata & Regular Expressions (Oct. 22, 2013) [Read 2.3]

    Pumping Lemma (Oct., 22, 2013; Nov. 5, 2013) [ Read 2.4]

    State Minimization (Nov. 5, 2013; Nov. 12, 2013) [Read 2.5-2.6]

    Context-Free Grammars (Nov. 12, 2013; Nov. 19, 2013) [Read 3.1-3.2]

    Pushdown Automata (Nov. 19, 2013) [Read 3.3]

    CFG vs. PA (Nov. 26, 2013; Dec. 3, 2013) [Read 3.4-3.6]

    Turing Machines (Dec. 3, 2013) [Read 4.1-4.2 & 5.3]

* No class on Dec. 17, 2013

* Fixed-Parameter Algorithms & Boolean Networks (Dec. 24, 2013)

* Class presentations (Dec. 31, 2013): TBA

1. J. Michael Steele, Variations on the Monotone Subsequence Theme of Erdös and Szekeres, Discrete Probability and Algorithms, Volume 72, 1995, pp 111-131.

2. Section 6.1 The Class P

3. Section 7.1 Polynomial-time Reductions

4. Section 7.4 Coping with NP-completeness