Introduction to the Theory of Computation
- 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
Weights of three exams: ??, ??, ?? (to be decided in the end of
(Sample exam questions: 1,
- 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.
30% homework, 70% Exam. (tentative)
Some (usually 10%) may fail if they don't work hard.