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

Exam Policies

The final exam is on Friday, December 8th, 10:30 - 12:20, in our usual room. It will last 1 hour and 50 minutes. 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
BPP
Space complexity: deterministic and nondeterministic
Savitch's Theorem
PSPACE and PSPACE-completeness
PSPACE-completeness of not everything problem for NFAs
EXPSPACE-completeness of not everything problem for regular expression with exponentiation
Alternating Turing machines
Alternating space and time theorems
PSPACE-completeness of QBF
EXPTIME-completeness of propositional temporal logic
LOGSPACE and NLOGSPACE, log space reducibility, completeness

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
Chapter 8, sections 8.1 to 8.5
Chapter 9, section 9.1
Chapter 10, sections 10.2 and 10.3

Study Suggestions

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

Old Finals

Final 1993: .ps .pdf
Final 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]