 |
Midterm Study Guide, Math 421, Fall 2024
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 2024 |
- The first two handouts to supplement the textbook:
- Uncomputability in CPSC 421/501,
Sections 1-7;
-
Non-Regular Languages and the Myhill-Nerode Theorem,
Sections 1,3,4.
-
Sipser's Textbook:
-
Chapter 1, excluding the Pumping Lemma in 1.4, and excluding the part of
1.3 that converts a DFA to a regular expression.
Turing machines (Chapter 3 of [Sip])
will not be examined on this year's midterm.
|
|---|
|
Practice Problems for the Midterm 2024 |
All homework problems, i.e., Homework 1-7 (this year, i.e., 2024),
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.
- 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).
In addition, here are some SUPPLEMENTAL
problems based on the
material NEW as of 2021,
but ignore problems 5,6,9:
some brief solutions may appear.
Supplemental Practice for the 2021 Midterm
Solutions to some, but NOT ALL, of these problems will be released.
Some additional problems will be added; some of these will have brief
solutions, and some will not.
In addition, here are some
Supplemental Practice for the 2024 Midterm
problems based on the
material NEW as of 2023 and 2024.
|
|---|
|
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
|
|---|
|