Final Exam Study Guide, Math 421, Fall 2023

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.

Examinable Material for the Final, 2023
  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-6, except Subsection 5.1 (on countably infinite sets).
    2. Non-Regular Languages, and the Myhill-Nerode Theorem, and Linear Algebra Tests, Sections 1-5.
    3. Introduction to Solving P versus NP, and Subbotovskaya's Restriction Method, Sections 1-5 except: Subsection 3.2, and Definition 3.5 and Theorem 3.6; the proofs of Proposition 4.1 and 4.3 (but you should know the statements of these propositions).
    4. 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.)
  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 Section 2 of the handout "Uncomputability in CPSC 421." Hence this may be helpful.)
    • Chapter 7 (although we didn't cover all of the examples there).
    • (In Section 9.3, the diagrams on pages 380 and 381 and the proof of Theorem 9.30 were referred to in "Introduction to Solving P versus NP, and Subbotovskaya's Restriction Method." Hence this may be helpful.)
Practice Problems for the Final 2023 The following are good practice problems for the final exam:
  1. All homework problems, i.e., Homework 1-11 (this year, i.e., 2023), are good exam study problems.
  2. All problems on the Midterm Study Guide 2023 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. Problems from Midterm 2023 (2023 midterm solutions).
  4. Here are problems with (sometimes brief) solutions from older exams:
    1. Final Exam 2021, Part 1, Problems 2-4, and the 2nd and 3rd T/F questions of Problem 1. Solutions to Final Exam 2021, Part 1.
    2. Final Exam 2021, Part 2, Problems 2(b,c) and all T/F questions of Problem 1 except the first three. Solutions to Final Exam 2021, Part 2.
    3. Final Exam 2017, Problem 1: 4th, 7th; Problems 2,3,4; Problem 5: (c). (solutions).
    4. Final 2004, Problems 1,2,5,6,7,8,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-4,5(g,h) (in Problem 2, Future(L,0001) means AccFut_L(0001)).
    2. Final Exam 2011, Problems 1,3,4,5,8.
  5. Here is a collection of some supplemental practice problems for the final exam 2023 here are brief solutions to the problems so far. Some typos on the problems were corrected on Dec 10 (to Questions 1(a,b)) and the morning of Dec 11 (to Question 3); the solutions remain the same.
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.)

Remark 3: There are some problems that I do not recommend on older final exams that, nonetheless, you should be able to answer.
A good example is the 5th T/F problem of Part 1 of the 2021 final exam.
In 2021, we studied "countable sets," which are sets, S, such that there is a surjection from the naturals to S. Hence we were used to questions stated as such.
in 2023, we did not discuss "countable sets." Howwever, we used the fact that the set of ASCII strings could be listed as i_1,i_2,... (to show that certain languages such as ACCEPT-SOME-INPUT 09_20 are recognizable). This was done by writing all strings of length 0, then of length 1, etc. This also works for strings over {a,b}, and was done for {a,b} in class on 09_20. Hence in 2023 you do have the tools to answer the above T/F problem, although we were not used to questions stated in this way.

Remark 4:

Remark 5:

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