- Instructor: Chih-Jen Lin, Room 413, CSIE building.
- TA (official ones): Chuan-Yao Su (r05922081 at ntu.edu.tw), Hung-Yi Chou (s1243221 at gmail.com), and Chieh-Teng Chang (scott820914 at gmail.com). TA hour:
Monday 14:00-16:00 and Thursday 14:00-16:00 in room 528

TA (undergraduate helper): Hsin-Yuan Huang (momohuang at gmail.com), TA hour Wed. 10:00-12:00 in**B1 of CSIE**or by email appointments - Time: Thursday 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).**No course on Nov 16 and maybe Nov 9 (out of the country). To make it up, we will reduce the 20-minute break to 10 minutes**

Place: room 104

- 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 September 28. (problem description as you may not have the book yet)

- Midterm 1: Oct 19 (week 6)
- Midterm 2: Dec 7 (week 13)
- Final: Final: Jan 11 (week 18) Discussion: ??, room ?? -->

For midterms, discussions will be in the following week.

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