Introduction to the Theory of Computation
- Instructor:
Chih-Jen Lin, Room 413, CSIE building.
- TAs: Sheng-Wei Chen, Yu-Jen Lin, and He-Zhe Lin
- TA email: D09944003 AT ntu DOT edu DOT tw, r10922a14 AT ntu DOT edu DOT tw, and r11922027 AT ntu DOT edu DOT tw
- TA hour : It will be hosted on Webex online at these times (the free version of webex has time limit of 50 minutes):
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:
As Omicron BA.5 is arising, we will do online in this semester. Course link is provided in NTU COOL.
-
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
-
Chapter 0 (
part 1:
slides
video
)
-
Chapter 1
-
Chapter 2
-
Chapter 3
-
Chapter 4
-
Chapter 7
Homework
Once every two weeks. Please write your homework/reports in English and do NOT submit lately. See
FAQ about how to submit your homework.
- HW1: 0.11, 1.3, 1.4(g), due on September 19th. (problem description as you may not have the book yet)
- HW2: 1.7(d)(e) (Please also give formal definition of your NFAs), 1.21(b), and 1.35, due on October 3th.
- HW3: 2.4e, 2.5 for 2.4e, CNF for 2.4e, 2.26. Due on October 31th.
- HW4: 3.1d, 3.9a, 3.16d, due on November 14th.
- HW5: 3.16c, 4.2, 4.24 due on Dec 5th.
- HW6: 4.7, 7.1(e) with proof, 7.2(b) with proof, 7.30 with providing both a verifier and NTM. See the pdf file for details. Due on December 19th.
Exams
Weights of three exams will be decided at the end of
the semester.
- Midterm 1: October 3 (week 5)
- Midterm 2: November 14 (week 11)
- Final: Final: December 19 (week 16) Discussion: ??, room ??
(Sample exam questions: 1,
2,
3)
For midterms, discussions will be in the following week.
Grading
30% homework, 70% Exam. (tentative)
Some (usually 10%) may fail if they don't work hard.
Last modified: