CSG 714   Spring 2007
Theory of Computation



In 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.



Apr 19: Ouch, typo on the final exam. The last line of question 3b should read: "Show that this would imply that P is *not* equal to NP". I have updated the PDF. Thanks for spotting this, Daniel.

Apr 17: The final is out. Due next Tuesday, Apr 24. Have fun!

Apr 6: Homework 8 is out. Due next Friday, Apr 13. Some of the questions are a bit harder than usual, so you may want to start early on this one.

Mar 24: Homework 7 is out. Sorry for the slight delay. To make up for it, the questions are actually quite easy. Due next Friday, March 30th. See you all on Tuesday.

Mar 20: There will be no class on Friday, as I am out of town for a workshop. Please read Section 10.1 and 10.2 in Hopcroft, Ullman, and Motwani. (10.1 is P and NP, and 10.2 is polynomial-time reductions and NP completeness.) The next homework will be posted by Friday.

Mar 16: I am sick, so no class today.

Mar 13: The midterm has been handed out. Due in a week.

Feb 27: Homework 6 is out. Due Tuesday after Spring Break. Also, the midterm exam (take home) will be handed out that Tuesday as well.

Feb 16: Homework 5 is out. Due next Friday.

Feb 10: Homework 4 is out. Due next Friday.

Feb 2: Homework 3 is out. Due next Friday.

Feb 1: Thanks to Ryan for presented the first two lectures about context-free languages.

Jan 22: Tuesday's lecture (Jan 23) cancelled. See you all Friday.

Jan 20: Updated homework 2 because of a missing assumption in Question 3: the alphabet needs at least two symbols for the result to be true. Thanks to Vlad for spotting this.

Jan 19: Homework 2 is out. Due next Friday.

Jan 12: Homework 1 is out. Due next Friday in class. I have also fleshed out the schedule for the upcoming classes.

Jan 11: There is a mailing list set up for the course. Please point your browser here and subscribe.

Jan 11: It appears that we will not be moving the class after all. Sorry if this caused worries and confusion over the last week, and thanks for your patience.


Course Information

Time and Location: Tuesday/Friday 9h50-11h30, in 5 Snell Library (#59)

Instructor: Riccardo Pucella, 328 West Village H (#23H)

Office hours: Monday 14h00-16h00

Course Web Site: http://www.ccs.neu.edu/home/riccardo/csg714

Prerequisites: CSG 713 (Advanced Algorithms)

Grading: Grading will be based on weekly homeworks (50%), a take-home midterm (25%), and a take-home final exam (25%).

Textbooks: The main textbook for the course is:

Other useful textbooks include:

  • Introduction to the Theory of Computation, by Sipser
  • Computational Complexity, by Papadimitriou
  • Computers and Intractability: A Guide to the Theory of NP-Completeness, by Garey and Johnson


Schedule Outline and Lecture Notes

This schedule is subject to change.

Automata Theory

  • Jan 9: Finite automata and regular languages
  • Jan 12: Properties of regular languages
  • Jan 16: Regular expressions
  • Jan 19: Pumping Lemma for regular languages
  • Jan 23: Cancelled
  • Jan 26: Pushdown automata and context-free languages
  • Jan 30: Context-free grammars
  • Feb 2: Equivalence of CFG and pushdown automata
  • Feb 6: Pumping Lemma for CFLs
  • Feb 9: Logical characterization of languages

Computability Theory

  • Feb 13: Turing machines
  • Feb 16: Decidability and recognizability
  • Feb 20: Existence of non-recognizable languages
  • Feb 23: The halting problem
  • Feb 27: Reductions
  • Mar 1: Rice's theorem
  • Mar 13: Post correspondence problem

Complexity Theory

  • Time complexity
  • Classes P, NP, co-NP
  • Polytime reductions
  • NP-completeness
  • Space complexity
  • Hardness of approximations




Online Resources