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
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
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
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
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.
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
- 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.
- 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
- 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
- Time complexity
- Classes P, NP, co-NP
- Polytime reductions
- Space complexity
- Hardness of approximations