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

More content and corrections may be added to this page.

Examinable Material (Course Coverage)
  1. Directed Graphs and Asymptotic Tests: All material except Appendix B.
  2. Uncomputability and Self-Referencing in CPSC421: Sections 1--4.
  3. 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).
  4. 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).
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 Myhill-Nerode theorem. (solutions).
Some of these were used in the homework: Here are some problems for which I will not provide solutions: 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