Theory of Computing, Spring 2021
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.
Announcements
07/01: grade report available; please send inquiries, if any, to the instructor by 5PM 07/02.
06/21: slides from TA sessions:
HW#6-10.
06/21: notes/slides for More NP-Complete Problems available.
06/08: slides from TA sessions:
HW#6-9.
06/02:
HW#10 due on 06/15.
05/24: notes/slides for Time Complexity and NP-Completeness available.
05/24:
HW#9 due on 06/01.
05/18: notes/slides for Reducibility available.
05/11:
HW#8 due on 05/18.
-
05/04: notes/slides for Decidability available.
05/04:
HW#7 due on 05/11.
04/27: notes/slides for Turing Machines available.
04/13: old exams:
2000-2020. (Note: I didn't offer the course some of the years.)
04/13: slides from TA sessions:
HW#1-5.
04/12:
HW#6 due on 04/27.
03/30:
HW#5 due on 04/13.
03/22: notes/slides for Context-Free Languages and Pushdown Automata available.
03/22:
HW#4 due on 03/30.
03/15: TA session of 3/16 postponed to 3/23.
03/15:
HW#3 due on 03/23.
03/15: slides for Minimization of DFAs available.
03/09: class meeting room changed to Room 204 from this day.
03/09:
HW#2 due on 03/16.
03/02: notes/slides for Finite Automata and Regular Languages available.
03/02:
HW#1 due on 03/09.
02/23: notes/slides for Introduction and Mathematical Preliminaries available.
02/22: website created on 02/18. This website is the primary source of all up to date course information and syllabus of Theory of Computing 2021; there is no separate PDF version for the syllabus.
Instructor
Yih-Kuen Tsay (蔡益坤), NTU IM Dept.,
3366-1189, Xtsay@ntu.edu.twX (between the enclosing pair of X's).
Lectures
Tuesday 2:20~5:20PM, Room 303, 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.
Office Hours
Tuesday 1:30~2:00PM, Wednesday 1:30~2:00PM, or by appointment, Room 1108,
Management Building 2.
TA
Wei-Cheng Liu (劉韋成), Xr09725026@ntu.edu.twX (between the enclosing pair of X's).
Jack Su (蘇俊杰), Xr09725002@ntu.edu.twX (between the enclosing pair of X's).
Textbook
Syllabus/Schedule (with links to notes/slides)
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/23, 04/13, 05/18, and 06/08.)
References
Grading
Homework 20%, Participation 10%, Midterm 35%, Final 35%.