|
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
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
Homeworks
Online Resources
|