22C:131: Limits of Computation
On the final
The midterm is on Wednesday, May 9th, 7:30-9:30 am in
213 MLH. It is open notes/textbook and you are free
to bring printouts of solutions posted on the coursepage
or from elsewhere on the internet.
There will be four problems on the exam.
Each problem involves a short proof or construction.
Here is a list of topics that each of the problem covers.
- Problem 1:
On Savitch's Theorem and its proof, SPACE(), NSPACE(), PSPACE,
and PSPACE-completeness.
- Problem 2:
On L, NL, co-NL, and NL-completeness.
- Problem 3:
Space and time heirarchy theorems.
- Problem 4:
Probabilistic TMs, the classes BPP, RP, ZPP, the amplification theorem
for BPP.