
Final Exam Coverage and Practice Materials, Math 421, Fall 2017
More content and corrections may be added to this page.
Examinable Material (Course Coverage) 
 Directed Graphs and Asymptotic Tests: All material except Appendix B.

Uncomputability and SelfReferencing in CPSC421:
Sections 14.

Sipser's Textbook:

All Chapter 1.

All 3.1 (Turing machines) and part of 3.2:
multitape and nondeterministic machines.

All 4.2.

All Chapter 7.

All 8.1 and 8.2.

9.2: Oracle machines, (P^A = P with oracle A, NP^A).
Theorem: P^B = NP^B for any PSPACEcomplete problem, B
(second half of Theorem 9.20, the BakerGillSolovay Theorem).

Remarks and additional material:
 We have three tests for nonregular languages: the Pumping Lemma
(Section 1.4), the MyhillNerode theorem, and
WalkCounting Function test.
 On 11_20: We introducted SNEAKYNTM = { < M,w,1^t >  M accepts w within
time t } which is NPcomplete.
An analogously defined SNEAKYPSPACE = { < M,w,1^s >  M accepts w within
space s } which is PSPACEcomplete.
(Hence we know a PSPACEcomplete language even though we did not
cover Section 8.3.)
 On 11_22: Sections 8.1 and 8.2: Savitch's Theorem and PSPACE = NPSPACE.
 On 11_24: We proved P^B = NP^B for any PSPACEcomplete problem, B.
We also used CookLevin idea to show that a language in P has polynomial
size circuits to compute if an input is in the language or not
(see Theorem 9.30).
 On 11_27: The halting problem, HALT_TM (see page 216),
like the acceptance problem A_TM, is recognizable
(using a universal Turing machine) but is undecidable.
The complement of HALT_TM, and the complement of A_TM are
unrecognizable.
HALT_TM < A_TM and A_TM < HALT_TM (both by polytime reductions).
 On 11_29 and 12_01: Review (old exam problems).

Practice Problems for the Final Exam 
All homework problems and the problems on the midterm are good practice
problems.
Below I list the problems that directly correspond to the material
learned this year in the language that we used.
Here are some problems for which I will provide partial or full solutions:
Here are some problems with some brief solutions:
 Final 2004, Problems 1,2,5,6,7,8,9.
For 9(b) the hint for this years' course is to use the MyhillNerode
theorem.
(solutions).
Some of these were used in the homework:
Here are some problems for which I will not provide solutions:
 Midterm 2007, Problems 1,2.
 Midterm 2009, Problems 1,2.
 Final 2009, Problems 1,3.
 Final 2010, Problems 1,2,4,5.
Some problems from the Final 2014 and Final 2009 (Problem 3) may be
solved in class on the last two days of class.

