This is an introductory course to the theory of computing, a study of formal/mathematical foundations of computer science and technology. Its goal 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/13: grade report available; please send inquiries, if any, to the instructor by 5PM 06/15.
• 05/31: slides from TA sessions: HW#6-10.
• 05/23: HW#10 due 1:20PM 05/30.
• 05/16: notes/slides for Time Complexity and NP-Completeness available.
• 05/16: HW#9 due 05/23.
• 05/09: notes/slides for Reducibility available.
• 05/08: HW#8 due 05/16.
• 05/02: notes/slides for Decidability available.
• 05/02: Suggested Solutions to Midterm Problems available.
• 05/02: HW#7 due 05/09.
• 04/25: notes/slides for Turing Machines available.
• 04/12: HW#6 due 04/25.
• 04/12: slides from TA sessions: HW#1-5.
• 04/12: old exams: 2000-2022. (Note: I didn't offer the course some of the years.)
• 03/28: HW#5 due 1:20PM 04/11.
• 03/28: HW#4 due 1:20PM 04/11.
• 03/28: notes/slides for Context-Free Languages and Pushdown Automata available.
• 03/21: HW#3 due 2:20PM 03/28.
• 03/14: HW#2 due 1:20PM 03/21.
• 03/06: notes/slides for Finite Automata and Regular Languages available.
• 03/06: HW#1 due on 03/14.
• 02/21: notes/slides for Introduction and Mathematical Preliminaries available.
• 02/18: this website created to complement the NTU COOL site for this course.

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

Tuesday 2:20~5:20PM, Room 203, Management Building 2.
TA sessions will be scheduled prior to some of the class meetings between 1:20 and 2:10PM; see the course schedule.

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

Yi-Fan Lin (林奕帆), Xb08705009@ntu.edu.twX (between the enclosing pair of X's).

• Introduction to the Theory of Computation, 3rd Edition, Michael Sipser, Cengage Learning, 2012. (歐亞圖書代理)

This introductory course to the theory of computing 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 03/21, 04/11, 05/09, and 05/30.)

• Introduction and Mathematical Preliminaries (1.5 weeks: 02/21, 03/07a) [notes, slides]
• Finite Automata and Regular Languages (2.5 weeks: 03/07b, 03/014, 03/21*) [notes, slides, appendix:minimization]
• Context-Free Languages and Pushdown Automata (2 weeks: 03/28, 04/11*) [notes,slides]
• Midterm (2023/04/18)
• Turing Machines (1.5 weeks: 04/25, 05/2a) [notes, slides]
• Decidability (and Undecidability) (1.5 weeks: 05/02b, 05/09*) [notes, slides]
• Reducibility (1.5 weeks: 05/16, 05/23a) [notes, slides]
• Time Complexity and NP-Completeness (1.5 weeks: 05/23b, 05/30*) [notes, slides]
• Final (2023/06/06)

Homework 20%, Participation 10%, Midterm 35%, Final 35%.

• MIT OpenCourseWare: Automata, Computability, and Complexity
• Coursera: Introduction to Theoretical Computer Science
• 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.
• Mathematics and Computation: A Theory Revolutionizing Technology and Science, Avi Wigderson, 2019. (The book has formally been published by Princeton University Press.)
• Maillardet's Automaton at the Franklin Institute.
• What Is an Algorithm? (M.Y. Vardi, Communications of the ACM, Volume 55 Issue 3, March 2012)
• What Is Computation? (a lecture by Leslie Lamport, who received the 2013 Turing Award)
• Free Tool: GOAL
• Free Tool: JFLAP