Homework 1 [ ps | pdf | LaTeX source] out, due February 9 at the beginning of class.
To get started typing up your solutions, use this LaTeX shell for Homework 1. The LaTex shell requires the use
of 6045preamble.tex.
Homework solutions for this class MUST be typed.
We highly recommend that you use LaTeX.
Here is a useful document on how to use LaTeX.
There is also an Athena Minicourse which you may find helpful. One more useful LaTeX website is this one.
Homework 2 out ( [ ps | pdf | LaTeX source ]); will be due on Wednesday Feb 16. You might want to use the Xfig program to generate some of the figures (of the FAs etc.). Here is a comprehensive Xfig manual.
"Fake" Homework 2.5 [ ps | pdf ] out; these problems should be used to practice the material covered in lectures 4 and 5; they will not be due. Try them on your own first and then check your answers with the homework 2.5 solutions [ ps | pdf ].
Handout 2: Quiz 1 Information and Review Material [ ps | pdf ].
Reading: Computation histories (see page 176) and Sections 5.2
Handout 6 : A photocopy of Section 8.5 from "Introduction to Automata Theory, Languages and Computation" by Hopcroft, Motwani and Ullman will be distributed in the class.
Fake Homework 5.5 [ ps | pdf ] out. Solutions [ ps | pdf ]; these problems should be used to practice the material covered in lectures 12, 13 and 14; they will not be due.
Handout 7: Quiz 2 Information and Review Material [ ps | pdf ]
HAMPATH, SUBSET-SUM, 3-DIM-MATCHING and many more languages are NP-Complete
WARNING: the polynomial time reduction of 3SAT to HAMPATH is incorrect in OLD versions of Sipser (i.e., the first printing). The problem is that the diamond gadgets are missing separator nodes.
Fake Homework 8.5 out [ ps | pdf ]. The solutions to the fake homework [ ps | pdf ]. These problems should be used to practice the material covered in lectures 19, 20 and 21; they will not be due.
Handout 12: Quiz 3 Information and Review Materials [ ps | pdf ].
More Practice Problems [ ps | pdf ] for Quiz 3. These are extra problems to help you study SOME (but not all) of the material covered on Quiz 3. No solutions will be provided.
Homework 9 due. Solutions to Homework 9 out. [ ps | pdf ].
"Fake" Homework 10 out [ ps | pdf ]. These problems should be used to practice the material covered in lectures 23, 24, and 25; they will not be due. Solutions to the fake homework out. [ ps | pdf ]
Fake Homework 10.5 out. [ ps | pdf ]. These problems should be used to practice the material covered in lectures 25 and 26; they will not be due. Solutions to fake homework 10.5 out. [ ps | pdf ]