 |
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 |
- The first two handouts to supplement the textbook:
- Self-Referencing, Uncountability
and Uncomputability in CPSC 421, Sections 1-4 and Subsection 5.2;
-
this
article on the Myhill-Nerode theorem.
-
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.
- Midterm 2021.
(brief solutions).
- The
2020 Midterm of 9:30am, the
2020 Midterm of 8:30pm
(brief solutions to both).
- Midterm 2019.
(brief solutions).
- Midterm 2014, Problems 2(b,d)
(brief solutions).
- 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
|
|