Introduction to the Theory of Computation

• Instructor: Chih-Jen Lin, Room 413, CSIE building.
• TAs: Sheng-Wei Chen, Yu-Jen Lin
• TA email: D09944003 AT ntu DOT edu DOT tw, r10922a14 AT ntu DOT edu DOT tw
• TA hour : Wednesday 14:20-15:20 via Webex online. The link for TA hour is
  https://meet93.webex.com/meet93/j.php?MTID=m16d704b542281cfc199eec2c4680c2be



Your HW and exam scores, with solutions to exams

• Time: Monday 10:20am to 1pm.
  We will do two 10-minute breaks at around 11:10am and 12:10pm. The class ends at 1pm.
• Place: Online via Webex, due to COVID situation.

  The Webex link is provided at NTU cool, and you can join as a guest without registration.

• This course will be taught in English.
• Textbook: Michael Sipser, Introduction to the Theory of Computation, third edition, Cengage Learning, 2012
  
  We will mainly teach Chapters 1-4 and 7.
• FAQ of this course is here
• We have pre-recorded all lectures and will broadcast them in the class. In the class I will give additional comments while the video is being played.

Course Outline

• Automata and Languages
  Mathematical models of computation
• Computability Theory
  Problems CAN and CANNOT be solved by computers
• Complexity Theory
  Why some problems are hard but some are easy?

Why taking this course?

From authors of the textbook

• Theoretical CS has some fancy/big ideas
• Relevant to practice (e.g., modern cryptography)
• Abstract way of thinking the computers. Help you to design more beautiful ones

Slides (Latex sources) and recordings

• Chapter 0 ( part 1: slides video )
• Chapter 1
  • Deterministic finite automata ( part 1: slides video part 2: slides video part 3: slides video )
  • Nondeterministic finite automata ( part 1: slides video part 2: slides video part 3: slides video part 4: slides video )
  • Regular expressions ( part 1: slides video part 2: slides video part 3: slides video part 4: slides video )
  • Pumping lemma ( part 1: slides video part 2: slides video part 3: slides video )
• Chapter 2
  • Context-free grammars ( part 1: slides video part 2: slides video )
  • Chomsky normal form ( part 1: slides video part 2: slides video )
  • Pushdown automata ( part 1: slides video part 2: slides video part 3: slides video part 4: slides video part 5: slides video )
  • Deterministic pushdown automata ( part 1: slides video part 2: slides video )
• Chapter 3
  • Turing machines ( part 1: slides video part 2: slides video part 3: slides video )
  • Multitape Turing machines ( part 1: slides video part 2: slides video )
  • Nondeterministic Turing machines ( part 1: slides video part 2: slides video )
  • Hilbert's problems ( part 1: slides video )
• Chapter 4
  • Decidability ( part 1: slides video part 2: slides video )
  • Halting problem ( part 1: slides video part 2: slides video )
• Chapter 7
  • Big-O notation ( part 1: slides video part 2: slides video )
  • Time complexity ( part 1: slides video part 2: slides video )
  • Languages in P ( part 1: slides video )
  • Languages in NP ( part 1: slides video part 2: slides video )

Homework

• HW1: 0.13, 1.3, 1.4(g), due on October 11th. (problem description as you may not have the book yet)
• HW2: 1.9a, 1.14, due on October 25th.
• HW3: 1.17, 1.22, due on Nov 8th.
• HW4: 1.29b 1.47, due on Nov 29th.
• HW5: 2.4(e), 2.5 for 2.4(e), 2.14, 2.26 due on Dec 13th.
• HW6: 3.2(d), 3.16(b), 4.2, 7.1(e) with proof, 7.2(b) with proof, due on Jan 10th.

Exams

• Midterm 1: November 1 (week 6)
• Midterm 2: December 6 (week 11)
• Final: Final: January 10 (week 16) Discussion: 12pm, January ??, room 102

For midterms, discussions will be in the following week.

Grading

Some (usually 10%) may fail if they don't work hard.

FAQ