Introduction to the Theory of Computation

• Instructor: Chih-Jen Lin, Room 413, CSIE building.
• TA: r92012@csie

  Your homework score

• Time: Monday 10am to 1pm.
  We have a 20-minute break at around 11:30am.
• For this course, we will mainly use the blackboard.
• 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

Every week we will randomly select one to present his/her homework. Everyone has to turn in the homework before this presentation. Rules: We do not require you to come every week. If you are absent and are selected for presentation, you will be required to do a presentation next week. If you failed to show up then, your midterm score will be deducted by 15 points. On the other hand, every week we seek for a volunteer first who will get 10 bonus points. When no one volunteers, everyone can be picked no matter you have given a presentation before or not.

• HW1: 0.10, 0.11, due September 20.
• HW2: 1.4(i)(j), 1.5(a)(e), 1.10, due September 27
• HW3: 1.11, 1.12, 1.14(a)(c), due October 4
• HW4: 1.16, 1.23(a)(b), 1.32, due October 11
• HW5: 1.23(c)(d), 1.36, 2.4(a)(b), due October 18
• HW6: 2.4(c)(d), 2.5(c)(d), 2.14, due November 1
• HW7: 2.11, 2.12, 2.19, due November 8
• HW8: 3.1, 3.5, due November 29
• HW9: 3.12, 3.14, due December 6
• HW10: 3.7, 3.8, 4.3, due December 20
• HW11: 4.7, 4.10, 4.11, due December 27
• Hw12: 7.1, 7.2, due January 3

HW grade

Exams

• Midterm: November 8, 2004
• Final: January 10, 2005
  We will discuss the final exam on January 17, 2005.

Grading