Introduction to the Theory of Computation
Chih-Jen Lin, Room 413, CSIE building.
- TA : Wei-Lin Chiang (r06922166 at csie), Yu-Sheng Li (kevin1kevin1k at gmail). TA hour: Thursday 13:20-14:10 in room 528
Your HW and exam scores
- Time: Monday 10:20am to 1pm.
We have a 20-minute break at around 11:30am. So the class
will end at 1pm (rather than the 1:10pm).
On Sep 10 I must leave for the airport at 11:40. On Nov 5 we won't have course as I will be out of the country. To make these classes up, we will reduce the 20-minute break to 10 minutes
We won't have a lecture on Dec 22. However, on Dec 10, 17, 24 we will do 10- or 15-minute extra.
Place: room 102
This course will be taught in English.
You are assumed to take notes.
- 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
- 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?
Why you are forced to study this theoretical and maybe
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
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
- HW1: 0.13, 1.3, 1.4f, due on October 1. (problem description as you may not have the book yet)
- HW2: 1.10c, 1.17, 1.21b, due on October 15.
- HW3: 1.30, 1.46(a), 1.53, due on October 29.
- HW4: 2.4(e), 2.9, 2.10, due on November 26.
- HW5: 3.2(c), 3.13, 3.15(e), due on December 17.
- HW6: 4.8, 4.16, 7.8, due on January 7
Weights of three exams will be decided in the end of
(Sample exam questions: 1,
- Midterm 1: October 22 (week 7)
- Midterm 2: December 3 (week 13)
- Final: Final: January 7 (week 18) Discussion: 12pm, January 14, room 102
For midterms, discussions will be in the following week.
30% homework, 70% Exam. (tentative)
Some (usually 10%) may fail if they don't work hard.