Steam-powered Turing Machine University of Washington Department of Computer Science & Engineering
 Midterm Study Guide
  CSE Home  About Us    Search    Contact Info 

Exam Policies

The midterm is on Thursday, November 9th. It will last one hour. Please bring a 8 1/2 x 11 inch bluebook (or greenbook). You may handwrite all the notes you want inside the notebook ahead of time for use during the exam. Otherwise the exam is closed book.

Topics

Turing machines
Equivalent models to Turing machines: SMM, RAM, General Grammars
Variants of Turing machines: mulitple tapes, nondeterministic Turing machines
Universial Turing machine
Undecidability of acceptance problem
Reducibility: many-one and Turing
Using reducibility method to show other undecidable problems
Reductions using simulation and histories
Post correspondence problem
Decidability and undecidability of context-free grammar problems
Showing problems are not Turing-recognizable using many-one reductions
Time complexity: deterministic and nondeterministic
P and NP
Polynomial time reducibility
Cook-Levin Theorem
Other NP-complete problems
Optimization problems vs. decision problems

Sections in the Book

Chapter 3, all sections
Chapter 4, all sections
Chapter 5, all sections
Chapter 6, sections 6.2 and 6.3
Chapter 7, all sections

Study Suggestions

Review all homework solutions
Review all of Zasha's advice
Do exercises from the book
Do the old midterms from 531
Meet in groups where students solve problems
Ask questions of Zasha and Richard

Old Midterms

Midterm 1993: .ps .pdf
Midterm 1995: .ps .pdf

CSE logo Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to ladner]