Overview
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.
Announcements
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
polynomialtime 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 contextfree 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 9h5011h30, in 5
Snell Library (#59)
Instructor: Riccardo Pucella,
328 West Village H (#23H)
Office hours: Monday 14h0016h00
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 takehome midterm (25%), and a takehome 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
NPCompleteness, 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 contextfree languages
 Jan 30: Contextfree 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 nonrecognizable 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, coNP
 Polytime reductions
 NPcompleteness
 Space complexity
 Hardness of approximations
Homeworks
Online Resources
