Introduction to the Theory of Computation

• Instructor: Chih-Jen Lin, Room 413, CSIE building.
• TA: Chuan-heng Hsiao, chshou@csie
• Time: Thursday 10am to 1pm.

  Your final score of this course

• For this course, we will mainly use the blackboard.

  Lectures are given in English. However, you are welcome to ask questions in any language which I can understand.

  If you come to finish small exercises during my lectures, you will get 5 bonus points of the mid-term.

• Textbook: Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997
  We will mainly teach Chapters 1-4 and 7.

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 ?

Homework

• HW1: 0.10, 1.1, 1.2, due October 2.
• HW2: 1.9, 1.11, 1.12, 1.13, due October 16.
• HW3: 1.16, 1.17, 1.18, 1.24, 1.29, due October 30.
• HW4: 2.1, 2.4, 2.8, 2.9, 2.15, due November 13.
• HW5: 2.10, 2.11, 2.13, 2.14, and an addition one given in the class, due November 27.
• HW6: 3.2, 3.4, 3.5, 3.10, due December 18.
• HW7: 3.7, 3.9, 4.1, 4.3, 4.4, due December 25
• HW8: 4.6, 4.8, 4.9, 4.17, 4.20, and additional one, due January 8

HW grade

list of people who got 5 bonus points

Exams

• Midterm: November 6, 2003
• Final: January 8 11:40-13:10, 2004
  We will discuss the final exam at January 15, 2004

Grading