The goal of this course is to acquaint the students with the basic concepts in computation theory and to cultivate the students' ability in analyzing the complexity of computational problems.

• 06/30: grade report available; please send inquiries, if any, to the instructor by 2PM July 02.
• 06/14: slides from TA sessions: HW#5, HW#6, HW#7, HW#8, HW#9, HW#10.
• 06/06: the TA session rescheduled on 06/10 will be held in the same classroom. (There might be other students in the room waiting for the class starting from 2:20PM, but we have officially booked the room for 1:20-2:10PM.)
• 06/06: check out revised Slide 56 of Time Complexity and NP-Completeness.
• 05/29: reminder: there will be a TA session on 06/05.
• 05/22: HW#10 due on 05/29.
• 05/22: notes/slides for Time Complexity and NP-Completeness available.
• 05/16: reminder: there will be a TA session on 05/22.
• 05/15: HW#9 due on 05/22.
• 05/15: notes/slides for Reducibility available.
• 05/13: Suggested Solutions to Midterm Problems available.
• 05/07: HW#8 due on 05/15.
• 05/01: notes/slides for Decidability and Undecidability available.
• 04/24: HW#7 due on 05/01.
• 04/24: notes/slides for Turing Machines available.
• 04/11: old exams: 2000-2006.
• 04/10: slides from TA sessions: HW#1, HW#2, HW#3, HW#4.
• 04/10: HW#6 due on 04/17.
• 04/01: HW#5 due on 04/10.
• 03/27: reminder: there will be a TA session on 04/10.
• 03/26: notes/slides for Context-Free Languages available.
• 03/20: HW#4 due on 03/27.
• 03/19: reminder: there will be a TA session on 03/20, starting at 1:20PM.
• 03/18: HW#3 revised; please read the additional note for this revision.
• 03/13: HW#3 due on 03/20.
• 03/06: HW#2 due on 03/13.
• 03/05: notes/slides for Regular Languages available.
• 02/27: HW#1 due on 03/06.
• 02/20: notes/slides for Introduction and Mathematical Preliminaries available.

Yih-Kuen Tsay (蔡益坤), NTU IM Dept., 3366-1189, Xtsay@im.ntu.edu.twX (between the enclosing pair of X's).

Wednesday 2:20~5:20PM, Room B01, Management I.
TA sessions will be scheduled prior to some of the class meetings between 1:20 and 2:10PM.

Tuesday 1:30~2:00PM, Wednesday 1:30~2:00PM, or by appointment, Room 1108, Management II.

Jui-Shun Lai (賴瑞舜), 3366-1205, Xnarration.lai@gmail.comX (between the enclosing pair of X's).
Wei-Hsien Chang (張暐獻), 3366-1205, Xb96705043@ntu.edu.twX (between the enclosing pair of X's).

• Introduction to the Theory of Computation, 2nd, International Edition, Michael Sipser, Thomson Course Technology, 2006. (新月圖書代理)
• Introduction to the Theory of Computation, 3rd Edition, Michael Sipser, Cengage Learning, 2012. (歐亞圖書代理)

Note: according to the local distributor, the 3rd edition has not arrived in Taiwan. Its main difference from the 2nd edition is a new section on deterministic pushdown automata in Chapter 2. We will follow mainly the 2nd edition, but it should be safe for you to use the 3rd edition (if you manage to get one).

This is an introductory course to the theory of computation. It covers various mathematical models, including automata and Turing machines, for physical computing machineries along with their computational capabilities/limitations. In terms of specific topics and the order of their exposition, the course will follow closely the book by Sipser. (Note: a TA session will precede a class meeting whose date is marked with an *. There are four TA sessions on 3/20, 4/10, 5/22, and 6/5, making up one skipped class meeting.)

• Introduction and Mathematical Preliminaries (2 weeks: 2/20, 2/27) [notes, slides]
• Finite Automata and Regular Languages (3 weeks: 3/6, 3/13, 3/20*) [notes, slides]
• Context-Free Languages and Pushdown Automata (2 weeks: 3/27, 4/10*) [notes,slides]
• Midterm (2013/04/17)
• Turing Machines (1.5 weeks: 4/24, 5/1a) [notes, slides]
• Decidability and Undecidability (2 weeks: 5/1b, 5/8, 5/15a) [notes, slides]
• Reducibility (1.5 weeks: 5/15b, 5/22*) [notes, slides]
• Time Complexity and NP-Completeness (2 weeks: 5/29, 6/5*) [notes, slides]
• Final (2013/06/19)

• MIT OpenCourseWare: Automata, Computability, and Complexity
• Stanford Coursera: Automata
• What is an Algorithm? (M.Y. Vardi, Communications of the ACM, Volume 55 Issue 3, March 2012)
• Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft and Jeffrey D. Ullman, Addison-Wesley, 1979.
• Introduction to Automata Theory, Languages, and Computation, 3rd Edition, John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Addison-Wesley, 2006.
• Elements of the Theory of Computation, 2nd Edition, Harry R. Lewis and Christos H. Papadimitriou, Prentice-Hall, 1998.
• Maillardet's Automaton at the Franklin Institute.
• Free Tool: JFLAP
• Free Tool: GOAL

Homework 20%, Participation 10%, Midterm 30%, Final 40%.