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

=====Instructors=====
[[http://www.iis.sinica.edu.tw/pages/yfc/contact_en.html|Yu-Fang Chen (陳郁方)]], Academia Sinica IIS and NTU IM Dept., ''Xyfc@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).\\
[[http://soslab.nccu.edu.tw/Welcome.html|Fang Yu (郁方)]], NCCU MIS Dept., ''Xyuf@nccu.edu.twX'' (between the enclosing pair of X's).

=====Lectures=====
Wednesday 2:20~5:20PM, Room 103, 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/25, 4/15, 5/20, and 6/10.)
  *Introduction and Mathematical Preliminaries (2 weeks: 2/25, 3/4) [{{courses:theory2015:ch0_notes.pdf|notes}}, {{courses:theory2015:ch0_slides.pdf|slides}}]
  *Finite Automata and Regular Languages (3 weeks: 3/11, 3/18, 3/25*) [{{courses:theory2015:ch1_notes.pdf|notes}}, {{courses:theory2015:ch1_slides.pdf|slides}}]
  *Context-Free Languages and Pushdown Automata (2 weeks: 4/8, 4/15*) [{{courses:theory2015:ch2_notes.pdf|notes}},{{courses:theory2015:ch2_slides.pdf|slides}}]
  * **Midterm** (**2015/04/22**)
  *Turing Machines (2 weeks: 4/29, 5/6) [{{courses:theory2015:ch3_notes.pdf|notes}}, {{courses:theory2015:ch3_slides.pdf|slides}}]
  *Decidability and Undecidability (1 week: 5/13) [{{courses:theory2015:ch4_notes.pdf|notes}}, {{courses:theory2015:ch4_slides.pdf|slides}}]
  *Reducibility (2 weeks: 5/20*, 5/27) [{{courses:theory2015:ch5_notes.pdf|notes}}, {{courses:theory2015:ch5_slides.pdf|slides}}]
  *Time Complexity and NP-Completeness (3 weeks: 6/3, 6/10*, 6/17) [{{courses:theory2015:ch7_notes.pdf|notes}}, {{courses:theory2015:ch7_slides.pdf|slides}}]
  * **Final** (**2015/06/24**)

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