======Theory of Computing, Spring 2018======
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.

=====Announcements=====
  * next edition: [[http://im.ntu.edu.tw/~tsay/dokuwiki/doku.php?id=courses:theory2020:main|Theory of Computing 2020]].
  * 07/08: grade report available; please send inquiries, if any, to the instructor by 2PM 07/09.
  * 06/20: slides from TA sessions: {{courses:theory2018:ta_3.pptx|HW#5-7}}, {{courses:theory2018:ta_4.pptx|HW#8-10}}.
  * 05/30: {{courses:theory2018:hw10.pdf|HW#10}} due on 06/06.
  * 05/30: notes/slides for Time Complexity and NP-Completeness available.
  * 05/23: {{courses:theory2018:hw9.pdf|HW#9}} due on 05/30.
  * 05/16: notes/slides for Reducibility available.
  * 05/16: {{courses:theory2018:hw8.pdf|HW#8}} due on 05/23.
  * 05/16: {{courses:theory2018:theory2018mid_s.pdf|Suggested Solutions to Midterm Problems}} available.
  * 05/09: notes/slides for Decidability available.
  * 05/09: {{courses:theory2018:hw7.pdf|HW#7}} due on 05/16.
  * 05/02: notes/slides for Turing Machines available.
  * 04/19: slides from TA sessions: {{courses:theory2018:ta_1.pptx|HW#1-2}}, {{courses:theory2018:ta_2.pptx|HW#3-4}}.
  * 04/18: notes/slides for Context-Free Languages and Pushdown Automata revised.
  * 04/18: old exams: {{courses:theory:old_exams.zip|2000-2017}}.
  * 04/18: {{courses:theory2018:hw6.pdf|HW#6}} due on 05/01.
  * 04/18: {{courses:theory2018:hw5.pdf|HW#5}} due on 05/01.
  * 04/11: {{courses:theory2018:hw4.pdf|HW#4}} due on 04/18.
  * 04/11: notes/slides for Context-Free Languages and Pushdown Automata available.
  * 03/28: {{courses:theory2018:hw3.pdf|HW#3}} due on 04/11.
  * 03/21: {{courses:theory2018:hw2.pdf|HW#2}} due on 03/28.
  * 03/14: notes/slides for Finite Automata and Regular Languages available.
  * 03/07: {{courses:theory2018:hw1.pdf|HW#1}} due on 03/21.
  * 03/07: notes/slides for Introduction and Mathematical Preliminaries available.
  * 02/25: this website announced.

=====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=====
Wednesday 2:20~5:20PM, Room 102, 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=====
林敬傑, ''Xr05725007@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 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/28, 4/18, 5/16, and 6/13.)
  *Introduction and Mathematical Preliminaries (1.5 weeks: 3/7, 3/14a) [{{courses:theory2018:ch0_notes.pdf|notes}}, {{courses:theory2018:ch0_slides.pdf|slides}}]
  *Finite Automata and Regular Languages (2.5 weeks: 3/14b, 3/21, 3/28*) [{{courses:theory2018:ch1_notes.pdf|notes}}, {{courses:theory2018:ch1_slides.pdf|slides}}, appendix:{{courses:theory2018:ch1_minimization.pdf|minimization}}]
  *Context-Free Languages and Pushdown Automata (2 weeks: 4/11, 4/18*) [{{courses:theory2018:ch2_notes.pdf|notes}},{{courses:theory2018:ch2_slides.pdf|slides}}]
  * **Midterm** (**2018/04/25**)
  *Turing Machines (2 weeks: 5/2, 5/9) [{{courses:theory2018:ch3_notes.pdf|notes}}, {{courses:theory2018:ch3_slides.pdf|slides}}]
  *Decidability (and Undecidability) (1 week: 5/16*) [{{courses:theory2018:ch4_notes.pdf|notes}}, {{courses:theory2018:ch4_slides.pdf|slides}}]
  *Reducibility (2 weeks: 5/23, 5/30) [{{courses:theory2018:ch5_notes.pdf|notes}}, {{courses:theory2018:ch5_slides.pdf|slides}}]
  *Time Complexity and NP-Completeness (3 weeks: 6/6, 6/13*, 6/20) [{{courses:theory2018:ch7_notes.pdf|notes}}, {{courses:theory2018:ch7_slides.pdf|slides}}]
  * **Final** (**2018/06/27**)

=====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.
  *[[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%.