Midterm Study Guide, Math 421, Fall 2023

More content and corrections may be added to this page.

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

Examinable Material for Midterm 2023
  1. The first two handouts to supplement the textbook:
    1. Self-Referencing, Uncountability and Uncomputability in CPSC 421, Sections 1-4 and Subsection 5.2;
    2. this article on the Myhill-Nerode theorem.
  2. Sipser's Textbook:
    • Chapter 1, excluding the Pumping Lemma in 1.4, and the (mostly) theoretical direction of 1.3 (DFA/NFA to regular expression). Turing machines (Chapter 3 of [Sip]) will not be examined on this year's midterm.
Practice Problems for the Midterm 2023 All homework problems, i.e., Homework 1-7 (this year, i.e., 2023), are good exam study problems.
For the questions that refer to Turing machines but involve a regular language, write an efficient DFA and/or NFA for the langugages in question. Turing machines (Chapter 3 of [Sip]) will not be examined on this year's midterm. Ignore all quetions on countable sets and countability; this year, 2023, we covered decidable and recognizable languages instead.
  1. Midterm 2021. (brief solutions).
  2. The 2020 Midterm of 9:30am, the 2020 Midterm of 8:30pm (brief solutions to both).
  3. Midterm 2019. (brief solutions).
  4. Midterm 2014, Problems 2(b,d) (brief solutions).
  5. Midterm 2011, Problem 3 (brief solutions).
In addition, here are some SUPPLEMENTAL problems based on the material NEW as of 2021, but ignore problems 5,6,9: Supplemental Practice for the 2021 Midterm Solutions to some, but NOT ALL, of these problems will be released.

In addition, here are some Supplemental Practice for the 2023 Midterm problems based on the material NEW as of 2023.

Here are Solutions to some of the midterm practice questions, including Individual Homework 7, Problem (3) (last revised Nov 2, 2:58pm). Some of these solutions are brief, and some are not given at all.
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