======Theory of Computing, Spring 2016======
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=====
  * 07/03: grade report available; please send inquiries, if any, to the instructor by 2PM 07/04.
  * 06/08: slides from TA sessions: {{courses:theory2016:toc_ta1.pptx|HW#1-2}}, {{courses:theory2016:toc_ta2.pptx|HW#3-5}}, {{courses:theory2016:toc_ta3.pptx|HW#6-7}}, {{courses:theory2016:toc_ta4.pptx|HW#8-10}}.
  * 06/08: {{courses:theory2016:hw10.pdf|HW#10}} due on 06/15.
  * 05/25: {{courses:theory2016:hw9.pdf|HW#9}} due on 06/01.
  * 05/25: notes/slides for Time Complexity and NP-Completeness available.
  * 05/17: {{courses:theory2016:hw8.pdf|HW#8}} due on 05/25.
  * 05/17: notes/slides for Reducibility available.
  * 05/11: {{courses:theory2016:theory2016mid_s.pdf|Suggested Solutions to Midterm Problems}} available.
  * 05/04: notes/slides for Decidability available.
  * 04/28: {{courses:theory2016:hw7.pdf|HW#7}} due on 05/11.
  * 04/27: notes/slides for Turing Machines available.
  * 04/11: old exams: {{courses:theory:old_exams.zip|2000-2015}}.
  * 04/06: {{courses:theory2016:hw6.pdf|HW#6}} due on 04/20.
  * 03/23: {{courses:theory2016:hw5.pdf|HW#5}} due on 04/06.
  * 03/16: {{courses:theory2016:hw4.pdf|HW#4}} due on 03/30.
  * 03/16: notes/slides for Context-Free Languages and Pushdown Automata available.
  * 03/09: {{courses:theory2016:hw3.pdf|HW#3}} due on 03/23.
  * 03/02: {{courses:theory2016:hw2.pdf|HW#2}} due on 03/16.
  * 03/02: notes/slides for Finite Automata and Regular Languages available.
  * 02/24: {{courses:theory2016:hw1.pdf|HW#1}} due on 03/09.
  * 02/24: notes/slides for Introduction and Mathematical Preliminaries available.
  * 02/17: 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 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.

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

=====TA=====
Hung-Wei Hsu (許宏瑋), 3366-1205, ''Xr02725048@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/23, 4/6, 5/11, and 6/8, making up the missed class meeting on 4/13.)
  *Introduction and Mathematical Preliminaries (2 weeks: 2/24, 3/2) [{{courses:theory2016:ch0_notes.pdf|notes}}, {{courses:theory2016:ch0_slides.pdf|slides}}]
  *Finite Automata and Regular Languages (3 weeks: 3/9, 3/16, 3/23*) [{{courses:theory2016:ch1_notes.pdf|notes}}, {{courses:theory2016:ch1_slides.pdf|slides}}]
  *Context-Free Languages and Pushdown Automata (2 weeks: 3/30, 4/6*) [{{courses:theory2016:ch2_notes.pdf|notes}},{{courses:theory2016:ch2_slides.pdf|slides}}]
  * **Midterm** (**2016/04/20**)
  *Turing Machines (2 weeks: 4/27, 5/4) [{{courses:theory2016:ch3_notes.pdf|notes}}, {{courses:theory2016:ch3_slides.pdf|slides}}]
  *Decidability (and Undecidability) (1 week: 5/11*) [{{courses:theory2016:ch4_notes.pdf|notes}}, {{courses:theory2016:ch4_slides.pdf|slides}}]
  *Reducibility (2 weeks: 5/18, 5/25) [{{courses:theory2016:ch5_notes.pdf|notes}}, {{courses:theory2016:ch5_slides.pdf|slides}}]
  *Time Complexity and NP-Completeness (3 weeks: 6/1, 6/8*, 6/15) [{{courses:theory2016:ch7_notes.pdf|notes}}, {{courses:theory2016:ch7_slides.pdf|slides}}]
  * **Final** (**2016/06/22**)

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