- Instructor: 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

- 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 ?

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

- 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

- 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.

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