Please let us know if you have any trouble downloading, displaying, or printing anything on the course web site!
Solutions to the fifth homework are here.
Best web page to check if a problems is NP-Hard is: A compendium of NP optimization problems
For the final exam, the problems will correspond to homeworks 4-6. So it is mainly about Turing Machines, Decidabilty, Reducibility, P and NP. That being said, the problem itself may say something about automata or grammars, as for example the last problem of Homework 4.
The sixth homework was assigned November 18 and is due December 2 (and no later than before the start of the final exam).
The fifth homework was assigned November 9 and is due November 18.
The two sets of notes on time complexity are here and here (this second version has one extra theorem).
The project is due November 23. Sample input and output are input_grammar and output_tree. A second valid output is here. A big sample input is here.
A reminder: there is no class Thursday, Sept. 2.
The third (and final) version of the syllabus is available in PDF here.
There will be a make-up class on Monday Sept. 20, the exact time is not finalized yet.
The first homework was assigned today, August 31. It is due on September 14. You can download it in PDF here. Here are page 84 and page 86 from the book.
The second version of the first chapter notes is available in PDF here. The third version of the second set of notes is here. The third set of notes is here.
Updated solutions to the first homework are here.
The second homework was assigned September 14 and is due September 28. You can download it in PDF here.
For those looking to learn latex, check out the latex file giving the notes and the latex file giving Homework 1.
The midterm, on Oct. 21 (Oct. 22 for Section 04), will be based on Regular and Context Free languages, and Turing machines only up to the problem in Homework 3. Here is a Previously given midterm.
The third homework (version 2) was assigned September 30 and is due October 12. You can download it in PDF here. Example 3.9 has been scanned here.
Partial solutions to the second homework are here. Twice updated partial solutions to the third homework are here.
The fourth set of notes (on decidabilty; revised for Sipser second edition) is here.
The fourth homework was assigned October 21 and is due November 9. The version here is the same as the previous except the deadline.
The fifth set of notes (on reducibility) is here.
Partial solutions to the fourth homework are here.
