Final Exam Study Guide, CPSC 421/501, FALL 2021

More content and corrections may be added to this page, especially the "Additional Remarks" part below.

Examinable Material (Course Coverage)
  1. The handouts to supplement the textbook based on recent content:
    1. this article on the Myhill-Nerode theorem.
  2. The handouts to supplement the textbook based on 2004 -- ???? content:
    1. All but Section 7.9 of Self-Referencing, Uncountability and Uncomputability in CPSC 421;
    2. Sections 1-3 and part of Section 4 of The Cook-Levin Theorem and how to solve and not to solve P versus NP,
  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.
    • Orale Turing machines, Section 6.3, Section 9.2, and "Turing reducibility," Section 6.3 (see also class notes: DATES HERE)
    • Sections 7.1-7.3
  4. Remarks and additional material:
    • The topics covered in the CPSC 501 presentations in the last two weeks of class are not directly examinable.
    • If you are interested in taking CPSC 536F for Spring 2022, you be interested this introduction to circuit complexity (last revised 1:03pm on Nov 26, 2020).
Practice Problems for the Final Exam Based on Material Up To 2020 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:
  • Final Exam 2017, Problem 1: 1st, 2nd; Problems 2,4 (completely); Problem 5: (c,e). (solutions).
  • Midterm 2019. (All problems.) (solutions).
  • Midterm 2014, Problems 1,2(b,c,d). Also 2(a), where "Axiom 1" is replaced with the axioms/conditions that must hold of an "expressive Program-Input" system. (solutions).
  • Midterm 2011, (All problems; Problem 2 assumes that you are talking about an "expressive Program-Input system.") (solutions).
  • Midterm 2010, All problems except 4(b); note in problem 3, our notation in 2021 is slightly different, but the Result, EncodeBoth is the same; moreover, Axiom 2 simply asserts the existence of a universal program in a Program-Input system. (solutions).
Here are some problems with some brief solutions:
  • 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. (solutions).
Here are some problems for which I will not provide solutions:
  • Midterm 2009, Problems 1,4. (Same comment on L_yes as above, i.e., L_yes is the acceptance problem, i.e., ACCEPTANCE, in any Program-Input under the various assumptions we needed to prove that ACCEPTANCE is undecidable.)
  • Final 2009, Problem 3.
  • Final 2010, Problems 1,2,4,7.
  • Final 2011, Problems 1,2,4,6,7,8.
  • Final 2014, Problems 1,2,5(a,e,f) (in Problem 2, Future(L,0001) means AccFut_L(0001)).
Practice Problems for the Final Exam Based on New Material as of 2021 All homework problems and the problems on the midterm are good practice problems. These documents will likely have additional problems added on December 14 and 15: See also the supplemental questions , and some brief solutions .
UNDER CONSTRUCTION!! Additional Remarks (Because Some of You Asked); Remark 0: See the course piazza page for other remarks regarding the final exam.

Remark 1: You will pass the final exam--and therefore this course--if you can (COMPLETELY) correctly solve all problems asking you (1) formally describe a DFA that recognizes a given language, and (2) all problems asking you to describe a Turing machine algorithm (high-, implementation-, and/or formal-level descriptions) that recoginizes a given language.

[Warning: you should know what the above terms mean. Of course, there is no way to precisely describe at which point a high-level description becomes an implementation-level description, etc., but the instructor and TA's should be able to give you a reasonable idea.]

Remark 2: You are allowed 2 double sided 8.5" x 11" sheets of notes on the final exam.

Remark 3:

Remark 4:

Remark 5:

UBC Math Home| Joel Friedman Home| Course Materials