User Tools

Site Tools


courses:theory2015:main

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: HW#6-7, HW#8-10.
  • 06/03: HW#10 due on 06/10.
  • 05/27: HW#9 due on 06/03.
  • 05/27: notes/slides for Time Complexity and NP-Completeness available.
  • 05/13: TA session of 05/27 moved one week earlier to 05/20.
  • 05/13: notes/slides for Reducibility available.
  • 05/13: HW#8 due on 05/20.
  • 05/06: 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: 2000-2014.
  • 04/20: slides from TA sessions: HW#1-2, HW#3-5.
  • 04/08: HW#6 due on 04/22.
  • 04/06: HW#5 due on 04/15.
  • 04/06: notes/slides for Context-Free Languages and Pushdown Automata available.
  • 03/24: HW#4 due on 04/08.
  • 03/16: HW#3 due on 03/25.
  • 03/10: HW#2 due on 03/18.
  • 03/10: notes/slides for Finite Automata and Regular Languages available.
  • 03/04: HW#1 due on 03/11.
  • 02/25: notes/slides for Introduction and Mathematical Preliminaries available.
  • 02/24: this website announced.

Instructors

Yu-Fang Chen (陳郁方), Academia Sinica IIS and NTU IM Dept., Xyfc@iis.sinica.edu.twX (between the enclosing pair of X's).
Yih-Kuen Tsay (蔡益坤), NTU IM Dept., 3366-1189, Xtsay@ntu.edu.twX (between the enclosing pair of X's).
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

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) [notes, slides]
  • Finite Automata and Regular Languages (3 weeks: 3/11, 3/18, 3/25*) [notes, slides]
  • Context-Free Languages and Pushdown Automata (2 weeks: 4/8, 4/15*) [notes,slides]
  • Midterm (2015/04/22)
  • Turing Machines (2 weeks: 4/29, 5/6) [notes, slides]
  • Decidability and Undecidability (1 week: 5/13) [notes, slides]
  • Reducibility (2 weeks: 5/20*, 5/27) [notes, slides]
  • Time Complexity and NP-Completeness (3 weeks: 6/3, 6/10*, 6/17) [notes, slides]
  • Final (2015/06/24)

References

Grading

Homework 20%, Participation 10%, Midterm 35%, Final 35%.

courses/theory2015/main.txt · Last modified: 2016/05/04 11:15 by tsay