======Theory of Computing, Spring 2014======
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=====
  * 06/28: grade report available; please send inquiries, if any, to the instructor by 2PM 06/30.
  * 06/09: slides from TA sessions: {{courses:theory2014:tocta3.pptx|HW#5-7}}, {{courses:theory2014:tocta4.pptx|HW#8-10}}.
  * 05/28: {{courses:theory2014:hw10.pdf|HW#10}} due on 06/04.
  * 05/28: notes/slides for Time Complexity and NP-Completeness available.
  * 05/14: {{courses:theory2014:hw9.pdf|HW#9}} due on 05/21.
  * 05/13: notes/slides for Reducibility available.
  * 05/07: {{courses:theory2014:hw8.pdf|HW#8}} due on 05/14.
  * 05/07: {{courses:theory2014:theory2014mid_s.pdf|Suggested Solutions to Midterm Problems}} available.
  * 04/30: notes/slides for Decidability and Undecidability available.
  * 04/23: {{courses:theory2014:hw7.pdf|HW#7}} due on 04/30.
  * 04/23: notes/slides for Turing Machines available.
  * 04/09: slides from TA sessions: {{courses:theory2014:tocta1.pptx|HW#1-2}}, {{courses:theory2014:tocta2.pptx|HW#3-4}}.
  * 04/08: old exams: {{courses:theory:old_exams.zip|2000-2013}}.
  * 04/08: {{courses:theory2014:hw6.pdf|HW#6}} due on 04/23.
  * 04/08: {{courses:theory2014:hw5.pdf|HW#5}} due on 04/16.
  * 03/31: {{courses:theory2014:hw4.pdf|HW#4}} due on 04/09.
  * 03/25: notes/slides for Context-Free Languages and Pushdown Automata available.
  * 03/20: {{courses:theory2014:hw3.pdf|HW#3}} due on 03/26.
  * 03/10: due date of HW#2 postponed till 3/14.
  * 03/05: notes/slides for Finite Automata and Regular Languages available.
  * 03/03: {{courses:theory2014:hw2.pdf|HW#2}} due on 03/12.
  * 02/26: {{courses:theory2014:hw1.pdf|HW#1}} due on 03/05.
  * 02/26: notes/slides for Introduction and Mathematical Preliminaries available.
  * 02/08: this website created.

=====Instructors=====
[[http://www.iis.sinica.edu.tw/~trc/public/|Tyng-Ruey Chuang (莊庭瑞)]], Academia Sinica IIS and NTU IM Dept., ''Xtrc@iis.sinica.edu.twX'' (between the enclosing pair of X's).\\
[[http://www.iis.sinica.edu.tw/~scm/|Shin-Cheng Mu (穆信成)]],  Academia Sinica IIS and NTU IM Dept., ''Xscm@iis.sinica.edu.twX'' (between the enclosing pair of X's).\\
[[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 206, 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/19, 4/09, 5/21, and 6/4, making up one probable skipped class meeting.)
  *Introduction and Mathematical Preliminaries (2 weeks: 2/19, 2/26) [{{courses:theory2014:ch0_notes.pdf|notes}}, {{courses:theory2014:ch0_slides.pdf|slides}}]
  *Finite Automata and Regular Languages (3 weeks: 3/5, 3/12, 3/19*) [{{courses:theory2014:ch1_notes.pdf|notes}}, {{courses:theory2014:ch1_slides.pdf|slides}}]
  *Context-Free Languages and Pushdown Automata (2 weeks: 3/26, 4/9*) [{{courses:theory2014:ch2_notes.pdf|notes}},{{courses:theory2014:ch2_slides.pdf|slides}}]
  * **Midterm** (**2014/04/16**)
  *Turing Machines (1.5 weeks: 4/23, 4/30a) [{{courses:theory2014:ch3_notes.pdf|notes}}, {{courses:theory2014:ch3_slides.pdf|slides}}]
  *Decidability and Undecidability (2 weeks: 4/30b, 5/7, 5/14a) [{{courses:theory2014:ch4_notes.pdf|notes}}, {{courses:theory2014:ch4_slides.pdf|slides}}]
  *Reducibility (1.5 weeks: 5/14b, 5/21*) [{{courses:theory2014:ch5_notes.pdf|notes}}, {{courses:theory2014:ch5_slides.pdf|slides}}]
  *Time Complexity and NP-Completeness (2 weeks: 5/28, 6/4*) [{{courses:theory2014:ch7_notes.pdf|notes}}, {{courses:theory2014:ch7_slides.pdf|slides}}]
  *Reviews (if necessary, 1 week: 6/11)
  * **Final** (**2014/06/18**)

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