Homework 1 out (LaTeX source), due February 11 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.
"Fake" Homework 2.5 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.
Homework 5 out (LaTeX source); will be due on Wednesday, March 17. Here is an extra hint for problem 2; try to think about the problem on your own first.
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.
More Practice Problems 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.