CSG 714 
Theory of Computation 
Spring 2006 
OverviewIn this course, we study formal models of computation, notions of undecidability, and basic complexity theory. Models of computation include finite state automata, pushdown automata, and Turing machines. Topics covered include: properties of regular sets and contextfree languages, partial recursive functions, primitive recursive functions, recursively enumerable sets, Turing decidability and unsolvable problems, reductions, time and space complexity classes, and the polynomialtime hierarchy

AnnouncementsApr 24: The final has been handed out. Due monday, May 1st, at 17h00. Apr 5: Homework 7 is out. Due wednesday April 12, at the beginning of class. Mar 22: Homework 6 is out. Due wednesday March 29, at the beginning of class. Mar 13: The midterm is out. Due monday March 20th, at the beginning of class. Feb 27: Homework 5 is out. Due monday March 13th, at the beginning of class. Feb 15: Homework 4 is out. Due next wednesday, at the beginning of class. By the way, the version I distributed in class used a grammar format that I did not describe, so if you confused, just used the amended version I give below. Feb 8: Homework 3 is out. Due next wednesday, at the beginning of class. Feb 1: Second homework is out. Due next wednesday, at the beginning of class. Jan 24: Some notes on homework 1 can be found here. Jan 18: First homework is out. Due next wednesday, at the beginning of class. Jan 18: I have updated the schedule to reflect the sections in Sipser (2nd edition) corresponding roughly to the lectures Jan 9: Note that the course location has been changed to 433 Ryder Hall 

Administration 
Resources

Schedule and Lecture NotesHere is a list of the lectures planned for the course. Note that this schedule is subject to change.

Homework AssignmentsAll homeworks are provided in PDF.
