Final Exam Study Guide, Math 421, Fall 2025

More content and corrections may be added to this page.

You will be allowed 2 two-sided sheet of notes on 8.5 x 11 inch (Letter) sized paper.

The Exam is at 8:30am on Friday, Dec 19, in CHEB, Floor 1, Room 101. It consists of Part 1 (60 minutes), break (15 minutes), Part 2 (65 minutes). Please remain outside the room until you are invited in.

Examinable Material for the Final, 2025
  1. All material covered in class. This is mostly included in the sources below.
  2. The handouts to supplement the textbook:
    1. Uncomputability in CPSC 421, Sections 1-7.
    2. Non-Regular Languages, and the Myhill-Nerode Theorem, and Linear Algebra Tests, Sections 1-5.
    3. Section 1 of Sneaky Complete Languages and Notes on Chaper 7 explains some differences in the way we covered Chapter 7 of [Sip]. (Section 2 of this article will not be covered.)
    4. Sections 2-5 and Subsection A.2 (in Appendix A) of Introduction to Solving P Versus NP, and Subbotovskaya's Restriction Method
  3. Sipser's Textbook:
    • Chapter 1, excluding the Pumping Lemma in 1.4.
    • All of 3.1, the part of 3.2 on multi-tape and non-deterministic Turing machines.
    • All of 4.2.
    • (Theorem 5.1 and an example similar to Theorem 5.2 of Chapter 5 were covered in Sections 2-4 of the handout "Uncomputability in CPSC 421." Hence this may be helpful.)
    • Chapter 7 (including the Cook-Levin theorem and its proof, but not including the many reductions from 3SAT to other languages, such as SUBSET-SUM and 3COLOR).
    • Instead of Chapter 9 we covered Subbotovskaya's method of restrictions (see the handout). However, part of Section 9.3 intersects with this material (especially the diagrams on pages 380 and 381) and may help.
Practice Problems for the Final 2025 The following are good practice problems for the final exam:
  1. All homework problems, i.e., Homework 1-9 (this year, i.e., 2025), are good exam study problems.
  2. All problems on the Midterm Study Guide 2025 are recommended, plus the following problems from there (whose solutions are there): Problem 1 on Midterm 2014, and Problem 1 on Midterm 2011 (on Turing machines), and Problem 3 on Midterm 2014 with "421Simple" replaced with "Python" (on decidable/recognizable languages).
  3. All problems from Midterm 2023 (2023 midterm solutions), from Midterm 2024 (except Q.5 on Duck) (2024 midterm solutions), and from Midterm 2025 (2025 midterm solutions).
  4. Here are problems with (sometimes brief) solutions from older exams:
    1. Final Exam 2021, Part 1, Problems 1-4, except 1(a) (i.e., the first true/false question). Solutions to Final Exam 2021, Part 1.
    2. Final Exam 2021, Part 2, Problems 2(a,b,c) and all T/F questions of Problem 1 except the fourth and fifth. Solutions to Final Exam 2021, Part 2.
    3. Final Exam 2017, Problems 2,4; Problem 5: (e). (solutions).
    4. Final 2004, Problems 1,5,9. For 9(b) the hint--in the terminology we used this year--is to use the Myhill-Nerode theorem. (brief solutions only).
    5. More exams may be added.
    Here are problems for which I will not provide solutions:
    1. Final Exam 2014, Problems 1,2,5(g) (in Problem 2, Future(L,0001) means AccFut_L(0001)).
    2. Final Exam 2011, Problems 1,2,8.
  5. Problems 2 and 3 of supplemental practice problems for the final exam 2023 here are brief solutions to the problems.
Additional Remarks (Because Some of You Asked...) Remark 1: You will pass the final exam--and therefore this course--if you can (COMPLETELY) correctly solve all problems asking you to (1) describe a DFA that recognizes a given language, and/or (2) describe a Turing machine algorithm that recoginizes a given language. This usually includes explaining how they work.

Remark 2: You are allowed 2 double sided 8.5" x 11" sheets of notes on the final exam. (See above.)
Grading Scheme for Exams To get an idea of how your will be graded, here is the marking schemes from the 2020 9:30am Midterm: Midterm_2020_9_30am.pdf

UBC CS Home| Joel Friedman Home| Course Materials