Members‎ > ‎Jan Michael C. Yap‎ > ‎

CS 204 - Theory of Computation

Announcements

  • **NEW** November 15, 2015 - Exam 3 questionnaire and Final Paper guidelines now up. Exam 3 deadline is on November 23, 11:59pm, while Final Paper is due on December 13, 11:59pm. Please be guided accordingly.
  • November 8, 2015 - Exam 2 answer key up. Sorry for the delay in posting it. :)
  • October 19, 2015 - I have now posted the questionnaire for Exam 2. It is a "take home" exam, and the ABSOLUTE deadline for submission is on October 26, 2015, 11:59pm. Read the instructions carefully. Exam 2 covers decidability and reducibility. We will still discuss the topic on Recursion Theorem during the first part of the next meeting, but it will no longer be included in the coverage of the third exam. Have fun answering the exam (HAHAHAHAHAHA), stay safe, and see you next week! :)
  • October 18, 2015 - In accordance with Quezon City Mayor Herbert Bautista's announcement, tomorrow's class is cancelled in anticipation of potential adverse effects of Typhoon Lando. However, check here tomorrow around after lunch time for an important announcement. Stay safe everyone.
  • September 29, 2015 - There was a mistake in the Answer Key, particularly in Item 4 where a CFG is placed. I have uploaded an updated version of it just now. Credits to Mr. Ren Tristan de la Cruz for pointing this out. :)
  • September 28, 2015 - Answer Key for Exam 1 up. See you next week for the next wave of lessons. :)
  • September 18, 2015 - Reviewer for Exam 1 up. Check the right hand side for the link. Again, we have no classes this Monday, September 21, and we will have the first exam on September 28. Please be guided accordingly.
  • August 4, 2015 - This is the website for the CS 204 (Theory of Computation) class of Jan Michael Yap. Announcements and files pertinent to the class will be posted here.

DatesLesson Slides/Materials
08/03/2015Introduction
08/10/2015
08/17/2015
Finite Automata, Regular Expressions, and Regular Languages
Slides:
Part 1
Part 2
Part 3
Part 4
Part 5
 08/24/2015 
09/07/2015
Context-Free Grammars, Context-Free Languages, and Pushdown Automata
Slides:
Part 1
Part 2
Part 3
Part 4
Part 5
Part 6
09/07/2015
09/14/2015
 Turing Machines, Church-Turing Thesis, and Recursive and Recursively Enumerable Languages
Slides:
Part 1
Part 2
Part 3
Part 4
Part 5
Part 6
09/28/2015EXAM 1Answer Key
Reviewer
10/12/2015
DecidabilitySlides
10/12/2015
Reducibility
Slides
10/26/2015
Recursion Theorem
Reading

Slides^
10/19/2015
10/26/2015
EXAM 2Answer Key
Questionnaire
10/26/2015
11/02/2015
Time Complexity
Reading (for Complexity Theory in general)

Slides:
Part 1
Part 2
11/02/2015
11/09/2015
Space Complexity
Reading

Slides*:
Part 1
Part 2
Part 3
Part 4
11/09/2015Intractability
Slides
11/16/2015
11/23/2015
EXAM 3
 Questionnaire
11/23/2015
 12/13/2015
 FINAL PAPERGuidelines
^ - Slides are from Nancy Lynch and made available via the MIT Open
    Courseware initiative on  Automata, Computability, and Complexity.
* - Slides are from Nabil Mustafa's site. All rights duly reserved
    and fair use invoked. Owner may (request to) remove links and/or
    slides at his own convenience.
  • Syllabus can be downloaded here.
  • Copy of the 2012 Code of Student Conduct can be downloaded here.