# Final Exam Coverage and Practice Materials, Math 421, Fall 2017

 Examinable Material (Course Coverage) Directed Graphs and Asymptotic Tests: All material except Appendix B. Uncomputability and Self-Referencing in CPSC421: Sections 1--4. Sipser's Textbook: All Chapter 1. All 3.1 (Turing machines) and part of 3.2: multitape and non-deterministic 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 PSPACE-complete problem, B (second half of Theorem 9.20, the Baker-Gill-Solovay Theorem). Remarks and additional material: We have three tests for nonregular languages: the Pumping Lemma (Section 1.4), the Myhill-Nerode theorem, and Walk-Counting Function test. On 11_20: We introducted SNEAKY-NTM = { < M,w,1^t > | M accepts w within time t } which is NP-complete. An analogously defined SNEAKY-PSPACE = { < M,w,1^s > | M accepts w within space s } which is PSPACE-complete. (Hence we know a PSPACE-complete 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 PSPACE-complete problem, B. We also used Cook-Levin 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 poly-time reductions). On 11_29 and 12_01: Review (old exam problems). 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: Midterm 2014, Problems 1,2(c,d) (solutions). Midterm 2011, Problems 1,3 (solutions). Midterm 2010, Problems 1,4 (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 Myhill-Nerode theorem. (solutions). Some of these were used in the homework: Final 2011, Problems 1,2,3,4,5,8. Final 2014, All Problems. 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.

 UBC Math Home | Joel Friedman Home | Course Materials