


The course is divided into three units, on finitestate machines, on computability theory, and on complexity theory.
We assume that you have taken 6.042, Mathematics for Computer Science. 6.045 is, essentially, a mathematics course, and we assume that you are reasonably facile with mathematical concepts. In particular, we assume that you are comfortable with formal mathematical proofs, and can write them up properly.
The course web site can be found at: http://theory.lcs.mit.edu/classes/6.045/spring07
Electronic copies of handouts will be available on the site.
There are two course mailing lists. The first, sp076.045staff@mit.edu, reaches only the course staff. The second, sp076.045@mit.edu, reaches all staff and students. Please feel free to contact the staff via the first list, and your fellow students via the second. We especially encourage you to use the list to find other students to collaborate with.
Extra copies of handouts and supplemental readings will be kept in the course drawer, which is located outside of the course secretary's office, 32G672A.
Of course, you can instead turn them in during class on Monday. We think it is very important that you turn in the homework assignments on time and we are unable to accept late homeworks; if you cannot complete an assignment on time, please just hand in what you are able to do.
When we grade homeworks, we will give full credit for correct answers and proofs. We will give partial credit for partial solutions and solutions with minor flaws. We will also give a small amount of partial credit for answers which read in full, ``I don't know''. Likewise, proofs with gaps will receive partial credit, and the partial credit granted will increase if the gaps are explicitly noted. We will give no credit for wildly incorrect answers which are obviously there only in the hope of getting partial credit. Please only write down answers in which you are confident. Wild guesses make life difficult for the graders. Making yourself believe a false proof is bad for your brain.
We require that all homework solutions be typed up. We will provide LaTeX shells for you to flesh out with your solutions, but you do not need to use them. Handdrawn diagrams are permitted (though that may preclude submitting by email).
If you are unfamiliar with LaTeX, we recommend taking one of the Athena minicourses on LaTeX offered in February. (There are links on the course website to minicourse information as well as a useful LaTeX HowTo document).
Four of the homework assignments will be halfsized. These are the ones that cover single lectures, in weeks where the other lecture slot is taken up by a quiz or a national holiday.
The final exam will be cumulative. There will be no homework due on Wednesdays in which a quiz is given.
The final exam will be during finals week, and has yet to be scheduled.