Introduction to the Theory of Computation

• Instructor: Chih-Jen Lin, Room 413, CSIE building.
• TA: Chia-Hua Ho (b95082@csie), Ming-Yuan Hsu (r99922015@csie), and Yao-Nan Chen (r99922008@csie)
  TA hours: Monday and Friday 12:20-14:10, room 528.

  Your HW and exam scores

• Time: Tuesday 10:20am to 1:10pm.
  We have a 20-minute break at around 11:30am. So the class will end at 1pm.
  No course on Nov 15 because of university anniversary

  Place: room 104

• This course will be taught in English. We will use blackboard. You are assumed to take notes.
• Textbook: Michael Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
  We will mainly teach Chapters 1-4 and 7.
• FAQ of this course is here

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

Homework

• HW1: 0.11, 1.5(g), 1.5(h), 1.6(i), due on September 27. See problem statements here in case you haven't got your textbook.
• HW2: 1.16(b), 1.17(a), 1.36, due on October 11.
• HW3: 1.21(b), 1.35, 1.47, due on October 25.
• HW4: 2.6(b), 2.10, due on November 8. Note that we move 2.22 to HW5 because we haven't taught PDA in detail.
• HW5: 2.22, 2.44, 3.2(e), due on November 29 (note that we have no course on Nov 15 because of university anniversary).
• HW6: 3.7, 3.12, 3.15(c), due on December 13
• HW7: 4.10, 7.1 (f), 7.2(e), due on January 10

Exams

• Midterm 1: October 18
• Midterm 2: December 13 (moved from December 6)

  We had two choices: Nov 29 and Dec 13. A voting by students (14 versus 24) decides Dec 13.

• Final: January 10. Discussion: January 12 12:45pm at room ??. If you cannot come for discussion, you can get your answer sheet from TA.