Introduction to the Theory of Computation

• Instructor: Chih-Jen Lin, Room 413, CSIE building.
• TA : Sheng-Wei Chen and ??
• TA email : D09944003 and ?? AT csie DOT ntu DOT edu DOT tw
• TA hour : Tuesday 15:00-16:00 at CSIE Room 530. You may also email us for online discussion if needed.
• 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: room 102 or online depending on the COVID situation

• 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 )
  • Languages in P ( part 1: slides video )
  • Languages in NP ( part 1: slides video part 2: slides video )

Homework

• HW1: ??, due on September ??. (problem description as you may not have the book yet)

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