CS467: Theory of Computation (Autumn 2019)

Announcement

(Introduction to CS467)
(Preliminary knowledge on Set Theory)

PART I: Automata and Language

  1. Finite automata and regular language (pdf)
  2. Pushdown automata and context free language (pdf)
  3. (*) Deterministic Context-Free Languages (pdf)

PART II: Computability

  1. The Church-Turing Thesis (pdf)
  2. Decidability (pdf)
  3. Reducibility (pdf)
  4. (*) Goedel Number (pdf)

PART III: Computational Complexity

  1. Time Complexity (pdf)
  2. NP-completeness (pdf)
  3. Space Complexity (pdf)
  4. The log Space (pdf)
  5. Intractability (pdf)

    Assignments

    1. Week 02: Textbook (pdf), Chapter 1, Exercises and Problems: 1.5-b,g; 1.6-b,j; 1.11; 1.14; 1.29; Chapter 2, Exercises and Problems: 2.4-d,e,f.
    2. Week 03: Textbook (pdf), Chapter 2, Exercises and Problems: 2.4-c,d,e; 2.14; 2.20; 2.32; 2.36.
    3. Week 06: Textbook (pdf), Chapter 3, Exercises and Problems: 3.7; 3.8; 3.9; 3.13; 3.15.
    4. Week 07: Textbook (pdf), Chapter 4, Exercises and Problems: 4.3; 4.5; 4.7; 4.14; 4.24; 4.29.
    5. Week 08: Textbook (pdf), Chapter 5, Exercises and Problems: 5.1; 5.4; 5.13; 5.14; 5.28; 5.30. (进博会调休的原因,推迟到和第九周作业一起交。)
    6. Week 09: Textbook (pdf), Chapter 5, Exercises and Problems: 5.2; 5.6; 5.7; 5.23.
    7. Week 10: Textbook (pdf), Chapter 7, Exercises and Problems: 7.2; 7.6; 7.7; 7.10; 7.12.
    8. Week 11: Textbook (pdf), Chapter 7, Exercises and Problems: 7.16; 7.18; 7.24(a); 7.29.
    9. Week 12: Textbook (pdf), Chapter 8, Exercises and Problems: 8.1; 8.2; 8.4; 8.6; 8.8.
    10. Week 12: Textbook (pdf), Chapter 8, Exercises and Problems: 8.10; 8.11; 8.14; 8.25.
    11. Week 12: Textbook (pdf), Chapter 8, Exercises and Problems: 8.29; 8.30; 8.34.

    References

    Last updated: Sep. 9, 2019