Introduction to the Theory of Computation

• Instructor: Chih-Jen Lin, Room 413, CSIE building.
• TA: (You may find them in lab 528)

  Your HW scores.

• Time: Tuesday 9:10am to 12:00pm.
  We have a 20-minute break at around 10:30am, so we finish at 12:00pm.

  Place: room 104

• This course will be taught in English. We will use the 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(c), 1.5(h), 1.6(j), due on September 29, 2009. See HW problems here as you may not get the textbook yet.
• HW2: 1.16(b), 1.21(b), 1.34, due on Oct. 13, 2009
• HW3: 1.47, 1.53, due on November 3, 2009
• HW4: 2.15, 2.24, due on November 17, 2009
• HW5: 2.19, 3.13, due on December 1, 2009
• HW6: 3.15(b), 3.17, 3.21, due on December 22, 2009
• HW7: 4.12, 4.19, due on January 5, 2010

Exams

• Midterm 1: October 13
• Midterm 2: December 1 (Questions last year: can be found here)
• Final: January 12, 2010 (Questions last year: can be found here)
  For midterms, discussions will be in the following week. The discussion of the final exam will be on January 19, 2010 (room 104). See the faq page for more details.

Grading

We calculate raw scores first. We then adjust them to final scores so that some fail and some pass. Around 10 to 15% may not pass (tentative).

FAQ