Yih-Kuen Tsay's Wiki @ IM.NTU

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======Theory of Computing, Spring 2020======
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=====
  * 06/02 notes/slides for Time Complexity and NP-Completeness available.
  * 06/02: {{courses:theory2020:hw10.pdf|HW#10}} due on 06/09.
  * 06/01: we will meet in the classroom from 06/02.
  * 05/25: {{courses:theory2020:theory2020mid_s.pdf|Suggested Solutions to Midterm Problems}} available.
  * 05/21: due date of HW#9 extended to 06/02.
  * 05/19: {{courses:theory2020:hw9.pdf|HW#9}} due on 05/26.
  * 05/19: notes/slides for Reducibility available.
  * 05/11: {{courses:theory2020:hw8.pdf|HW#8}} due on 05/19.
  * 05/05: notes/slides for Decidability available.
  * 04/27: {{courses:theory2020:hw7.pdf|HW#7}} due on 05/12.
  * 04/27: notes/slides for Turing Machines available.
  * 04/20: the midterm exam tomorrow will be held in Room 303, Management Building 2, the room originally assigned for this class.  Before the exam, there will be a discussion session from 1:20PM in the same room for last-minute questions.
  * 04/18: old exams: {{courses:theory:old_exams.zip|2000-2018}}. (Note: I didn't offer this course in 2019.)
  * 04/18: slides from TA sessions: {{courses:theory2020:hw1_5.pdf|HW#1-5}}.
  * 04/14: {{courses:theory2020:hw6.pdf|HW#6}} due on 04/28.
  * 04/06: notes/slides for Context-Free Languages and Pushdown Automata revised.
  * 04/06: {{courses:theory2020:hw5.pdf|HW#5}} due on 04/14.
  * 03/30: notes/slides for Context-Free Languages and Pushdown Automata available.
  * 03/30: {{courses:theory2020:hw4.pdf|HW#4}} due on 04/07.
  * 03/30: notes/slides for Finite Automata and Regular Languages revised.
  * 03/24: {{courses:theory2020:hw3.pdf|HW#3}} due on 03/31.
  * 03/23: we will meet online over Skype for 3/24.
  * 03/17: {{courses:theory2020:hw2.pdf|HW#2}} due on 03/24.
  * 03/10: Ceiba course ID: 1082theory2020
  * 03/09: notes/slides for Finite Automata and Regular Languages available.
  * 03/09: {{courses:theory2020:hw1.pdf|HW#1}} due on 03/17.
  * 03/03: notes/slides for Introduction and Mathematical Preliminaries available.
  * 03/02: this website announced. This website is the primary source of all up to date course information and syllabus of Theory of Computing 2020; there is no separate PDF version for the syllabus.

=====Instructor=====
[[http://im.ntu.edu.tw/~tsay/|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=====
Wayne Zeng (曾守瑜), ''Xr08725038@ntu.edu.twX'' (between the enclosing pair of X's).

=====Textbook=====
  *//[[http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X|Introduction to the Theory of Computation, 3rd Edition]]//, Michael Sipser, Cengage Learning, 2012. (歐亞圖書代理)

=====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 3/31, 4/14, 5/19, and 6/9.)
  *Introduction and Mathematical Preliminaries (2 weeks: 3/3, 3/10) [{{courses:theory2020:ch0_notes.pdf|notes}}, {{courses:theory2020:ch0_slides.pdf|slides}}]
  *Finite Automata and Regular Languages (2.5 weeks: 3/17, 3/24, 3/31a*) [{{courses:theory2020:ch1_notes.pdf|notes}}, {{courses:theory2020:ch1_slides.pdf|slides}}, appendix:{{courses:theory2020:ch1_minimization.pdf|minimization}}]
  *Context-Free Languages and Pushdown Automata (2.5 weeks: 3/31b, 4/7, 4/14*) [{{courses:theory2020:ch2_notes.pdf|notes}},{{courses:theory2020:ch2_slides.pdf|slides}}]
  * **Midterm** (**2020/04/21**)
  *Turing Machines (2 weeks: 4/28, 5/5) [{{courses:theory2020:ch3_notes.pdf|notes}}, {{courses:theory2020:ch3_slides.pdf|slides}}]
  *Decidability (and Undecidability) (1.5 weeks: 5/12, 5/19a*) [{{courses:theory2020:ch4_notes.pdf|notes}}, {{courses:theory2020:ch4_slides.pdf|slides}}]
  *Reducibility (1.5 weeks: 5/19b, 5/26) [{{courses:theory2020:ch5_notes.pdf|notes}}, {{courses:theory2020:ch5_slides.pdf|slides}}]
  *Time Complexity and NP-Completeness (2 weeks: 6/2, 6/9*) [{{courses:theory2020:ch7a_notes.pdf|notes}}, {{courses:theory2020:ch7a_slides.pdf|slides}}]
  * **Final** (**2020/06/16**)
  *More about NP-Completeness (1 week: 6/23) [{{courses:theory2020:ch7b_notes.pdf|notes}}, {{courses:theory2020:ch7b_slides.pdf|slides}}]
  *Wrap-Up Discussions (1 week: 6/30)
=====References=====
  *MIT OpenCourseWare: [[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/index.htm|Automata, Computability, and Complexity]]
  *Stanford Coursera: [[https://www.coursera.org/course/automata|Automata]]
  *//[[http://www.amazon.com/Introduction-Automata-Languages-Computation-Addison-Wesley/dp/020102988X/ref=sr_1_11?s=books&ie=UTF8&qid=1361114620&sr=1-11&keywords=Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation|Introduction to Automata Theory, Languages, and Computation]]//, John E. Hopcroft and Jeffrey D. Ullman, Addison-Wesley, 1979.
  *//[[http://www.amazon.com/Introduction-Automata-Theory-Languages-Computation/dp/0321455371/ref=sr_1_2?s=books&ie=UTF8&qid=1361114620&sr=1-2&keywords=Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation|Introduction to Automata Theory, Languages, and Computation, 3rd Edition]]//, John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Addison-Wesley, 2006.
  *//[[http://www.amazon.com/Elements-Theory-Computation-2nd-Edition/dp/0132624788|Elements of the Theory of Computation, 2nd Edition]]//, Harry R. Lewis and Christos H. Papadimitriou, Prentice-Hall, 1998.
  *//[[https://www.math.ias.edu/avi/book|Mathematics and Computation: A Theory Revolutionizing Technology and Science]]//, Avi Wigderson, 2019. (The book has formally been published by Princeton University Press.)
  *[[http://www.fi.edu/learn/sci-tech/automaton/automaton.php?cts=instrumentation|Maillardet's Automaton]] at the Franklin Institute.
  *[[http://dl.acm.org/citation.cfm?id=2093549&CFID=70582427&CFTOKEN=84470362|What Is an Algorithm?]] (M.Y. Vardi, Communications of the ACM, Volume 55 Issue 3, March 2012)
  *[[http://www.youtube.com/watch?v=BDPHfRuAFnU|What Is Computation?]] (a lecture by Leslie Lamport, who received the 2013 Turing Award)
  *Free Tool: [[http://goal.im.ntu.edu.tw/|GOAL]]
  *Free Tool: [[http://www.jflap.org/|JFLAP]]

=====Grading=====
Homework 20%, Participation 10%, Midterm 35%, Final 35%.
Yih-Kuen Tsay's Wiki @ IM.NTU

User Tools

Site Tools

Page Tools
