Introduction to the Theory of Computation
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.
For late homework, the score will be exponentially decreased. See
FAQ about how to submit your
homework.
 HW1: 0.13, 1.3, 1.4f, due on September 28. (problem description as you may not have the book yet)
 HW2: 1.10a, 1.17, 1.21b, due on October 12.
 HW3: 1.29b, 1.30, 1.71, due on October 26.
 HW4: 2.14, 2.16, 2.47, due on November 16.
 HW5: 2.54(c), 3.2(b), 3.15(b), due on November 30.
Note that for 2.54(c), you can directly use the result of 2.54(a) without any proof.
Exams
Weights of three exams will be decided in the end of
the semester.
 Midterm 1: October 19 (week 6)
 Midterm 2: November 30 (week 12)
 Final: Final: January 11 (week 18) Discussion: 12pm, January ??, room 102
(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: