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 2017======
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=====
  * 04/20: slides from TA sessions: {{courses:theory2017:toc_ta3.pptx|HW#6-7}}, {{courses:theory2017:toc_ta4.pptx|HW#8-10}}.
  * 05/31: {{courses:theory2017:hw10.pdf|HW#10}} due on 06/07.
  * 05/24: {{courses:theory2017:hw9.pdf|HW#9}} due on 05/31.
  * 05/24: notes/slides for Time Complexity and NP-Completeness available.
  * 05/18: {{courses:theory2017:theory2017mid_s.pdf|Suggested Solutions to Midterm Problems}} available (revised on 5/24 and again on 6/25).
  * 05/17: notes/slides for Reducibility available.
  * 05/10: {{courses:theory2017:hw8.pdf|HW#8}} due on 05/24.
  * 05/10: notes/slides for Decidability available.
  * 05/03: {{courses:theory2017:hw7.pdf|HW#7}} due on 05/10.
  * 04/20: slides from TA sessions: {{courses:theory2017:toc_ta1.pptx|HW#1-2}}, {{courses:theory2017:toc_ta2.pptx|HW#3-5}}.
  * 04/19: old exams: {{courses:theory:old_exams.zip|2000-2016}}.
  * 04/19: notes/slides for Turing Machines available.
  * 04/12: {{courses:theory2017:hw6.pdf|HW#6}} due on 04/26.
  * 03/29: {{courses:theory2017:hw5.pdf|HW#5}} due on 04/12.
  * 03/22: notes/slides for Context-Free Languages and Pushdown Automata available.
  * 03/22: {{courses:theory2017:hw4.pdf|HW#4}} due on 03/29.
  * 03/15: {{courses:theory2017:hw3.pdf|HW#3}} due on 03/22.
  * 03/08: {{courses:theory2017:hw2.pdf|HW#2}} due on 03/15.
  * 03/01: notes/slides for Finite Automata and Regular Languages available.
  * 03/01: {{courses:theory2017:hw1.pdf|HW#1}} due on 03/08.
  * 02/22: notes/slides for Introduction and Mathematical Preliminaries available.
  * 02/20: 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 (Room 304 from 5/17), 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=====
Willy Chang (張子建), 3366-1205, ''Xr03725007@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/22, 4/12, 5/10, and 6/7.)
  *Introduction and Mathematical Preliminaries (2 weeks: 2/22, 3/1) [{{courses:theory2017:ch0_notes.pdf|notes}}, {{courses:theory2017:ch0_slides.pdf|slides}}]
  *Finite Automata and Regular Languages (3 weeks: 3/8, 3/15, 3/22*) [{{courses:theory2017:ch1_notes.pdf|notes}}, {{courses:theory2017:ch1_slides.pdf|slides}}, appendix:{{courses:theory2017:ch1_minimization.pdf|minimization}}]
  *Context-Free Languages and Pushdown Automata (2 weeks: 3/29, 4/12*) [{{courses:theory2017:ch2_notes.pdf|notes}},{{courses:theory2017:ch2_slides.pdf|slides}}]
  *Turing Machines (2 weeks: 4/19, 5/3) [{{courses:theory2017:ch3_notes.pdf|notes}}, {{courses:theory2017:ch3_slides.pdf|slides}}]
  * **Midterm** (**2017/04/26**)
  *Decidability (and Undecidability) (1 week: 5/10*) [{{courses:theory2017:ch4_notes.pdf|notes}}, {{courses:theory2017:ch4_slides.pdf|slides}}]
  *Reducibility (2 weeks: 5/17, 5/24) [{{courses:theory2017:ch5_notes.pdf|notes}}, {{courses:theory2017:ch5_slides.pdf|slides}}]
  *Time Complexity and NP-Completeness (3 weeks: 5/31, 6/7*, 6/14) [{{courses:theory2017:ch7_notes.pdf|notes}}, {{courses:theory2017:ch7_slides.pdf|slides}}]
  * **Final** (**2017/06/21**)

=====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%.
Yih-Kuen Tsay's Wiki @ IM.NTU

User Tools

Site Tools

Page Tools
