Course: The Theory of Computation

Fall semester, 2014

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

3 credits

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

Instructor: Kun-Mao Chao (趙坤茂)

Teaching Assistant: Yen-Wei Wu (吳彥緯)

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

Classmates: I  II  III

Coursework:

    Homework assignments and Class participation (10%)

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

        1. Midterm #1: Oct. 28, 2014 (tentative)

        2. Midterm #2: Dec. 9, 2014 (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. 16, 2014)

    Sets, Relations, and Functions  [Read 1.1-1.3] (Sept. 23, 2014)

    Some Proof Techniques  [Read 1.4-1.5] (Sept. 30, 2014; Oct. 7, 2014)

        -- Yet Another Proof: I  II More (Sept. 30, 2014)

        -- Magic Square (Sept. 30, 2014)

        -- Two Wrong Proofs (Oct. 7, 2014)

    Closures  [Read 1.6] (Oct. 7, 2014)

    Alphabets & Languages  [Read 1.7] (Oct. 14, 2014)

    Regular Expressions  [Read 1.8] (Oct. 14, 2014; Oct. 21, 2014)

    Deterministic Finite Automata [Read 2.1] (Oct. 21, 2014)

    Nondeterministic Finite Automata  [Read 2.2] (Oct. 21, 2014; Nov. 4, 2014)

    Finite Automata & Regular Expressions  [Read 2.3] (Nov. 4, 2014)

    Pumping Lemma  [ Read 2.4] (Nov. 4, 2014; Nov. 11, 2014)

    State Minimization  [Read 2.5-2.6] (Nov. 11, 2014; Nov. 18, 2014)

    Context-Free Grammars  [Read 3.1-3.2] (Nov. 18, 2014; Nov. 25, 2014)

    Pushdown Automata  [Read 3.3] (Nov. 25, 2014)

    CFG vs. PA  [Read 3.4-3.6] (Nov. 25, 2014; Dec. 2, 2014)

    Turing Machines  [Read 4.1-4.2 & 5.3] (Dec. 2, 2014)

* No class on Dec. 16, 2014

* Popular X problems  (Dec. 23, 2014 and Dec. 30, 2014)

* Class presentations (Jan. 6, 2015):

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.  (Jan. 6, 2015)

2. Section 6.1 The Class P

3. Section 7.1 Polynomial-time Reductions

4. Section 7.4 Coping with NP-completeness

5. Machine Translation

6. The Stable Marriage Problem