cs302: Theory of Computation   Spring 2008

cs302: Theory of Computation

David Evans

Assistant Coaches
Suzanne Collier
Qi Mi
Joe Talbott
Wuttisak Trongsiriwat

Class Meetings
Tuesdays and Thursdays
2-3:15pm in Olsson 120
Office Hours (OLS 236A)
Mondays, 2-3pm
Wednesday, 9:30-10:30am
Problem-Solving Sessions (OLS 228E)
Mondays, 5:30-6:30pm
Wednesday, 6-7pm

Exam 2

Exam 2 will be in class, Tuesday, April 8. It covers material from Lectures 1-20, Problem Sets 1-5 (including the comments), and Sipser Chapters 0-5.1. The exam may include questions from all of this material, but will focus on material that was not covered on Exam 1. The preponderance of the exam questions will focus on understanding of concepts that have been covered in all three ways (lecture, problem set, and book).

You may bring a single page, both sides, of prepared notes to use during the exam. You may not use any other resources during the exam.

If you can do these things (as well as the list from the Exam 1 guide), you should do well on the exam:

I recommend studying by doing as many of these things as you can (in roughly this order):

  1. Review Exam 1 and the provided comments. Hopefully, everyone has done this already.
  2. Review Problem Sets 4-5 and the provided comments. If there are questions you could not solve yourself originally, try them again and then use the comments for help.
  3. Review the course notes and slides. Try to solve the questions in the course notes.
  4. Review the book. For topics on which you are under-confident, try example problems and exercises in the book. (Many of these have solutions.)
  5. Try the practice exams (see below). Try to solve the questions yourself, before discussing them with others or looking at the solutions.
I also recommend getting help with any topics or questions you have by going to office hours (in Olsson 226D, Monday, 2-3pm; Wednesday, 9:30-10:30am) and the TAs review session (Monday 5:30pm, Olsson 228E).

Practice Exams

MIT 6.045J Practice Quiz 2 (Nancy Lynch and Elena Grigorescu)
The first 3 parts of Problem 1 cover enumerators, which are covered in the book, but we have not emphasized in class or the problem sets. Also, do not worry about the questions about the Post Correspondance Problem, which we have not covered (it is in Section 5.2).