Introduction to the Theory of Computation

• Instructor: Chih-Jen Lin, Room 413, CSIE building.
• TA : Sheng-Wei Chen, Yu-Sheng Li
• TA email : automata_ta 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

• 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
• New settings this year (important!)

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

Homework

Once every two weeks. Please write your homework/reports in English. For late homework, the score will be exponentially decreased. See FAQ about how to submit your homework.
• HW1: 0.13, 1.3, 1.4f, due on September 28. (problem description as you may not have the book yet)
• HW2: 1.10a, 1.17, 1.21b, due on October 12.
• HW3: 1.29b, 1.30, 1.71, due on October 26.
• HW4: 2.14, 2.16, 2.47, due on November 16.
• HW5: 2.54(c), 3.2(b), 3.15(b), due on November 30. Note that for 2.54(c), you can directly use the result of 2.54(a) without any proof.

Exams

Weights of three exams will be decided in the end of the semester.
• Midterm 1: October 19 (week 6)
• Midterm 2: November 30 (week 12)
• Final: Final: January 11 (week 18) Discussion: 12pm, January ??, room 102
(Sample exam questions: 1, 2, 3)

For midterms, discussions will be in the following week.