 |
Final Exam Study Guide, Math 421, Fall 2020
More content and corrections may be added to this page.
|
Examinable Material (Course Coverage) |
- The first two handouts to supplement the textbook:
- Self-Referencing, Uncountability
and Uncomputability in CPSC 421;
-
this article on the Myhill-Nerode theorem.
-
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.
Also, notes of 10_27 where we prove
that other related languages (e.g., HALT_TM)
are undecidable and unrecognizable
(this is also covered in the first portion of 5.1 of the textbook).
-
All Chapter 7, except the definition of NP as a polynomial time verifiable
language; we defined NP only as a language decidable by a non-deterministic
T.m. in polynomial time.
-
Remarks and additional material:
- The topics I covered
and covered in the presentations in the last two weeks of class are
not covered.
-
Nonetheless, some of the material from the last two weeks, including
this introduction to circuit complexity
(last revised 1:03pm on Nov 26), may help you understand the
examinable material.
|
|---|
|
Practice Problems for the Final Exam |
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,
4th T/F; Problems 2,3,4 (completely); Problem 5: (c,e).
(solutions).
- Midterm 2019.
(solutions).
- Midterm 2014, Problems 1,2(b,c,d)
(solutions).
- Midterm 2011, Problems 1,3
(solutions).
- Midterm 2010, Problems 1,4
(solutions).
Here are some problems with some brief solutions:
- 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.
(solutions).
Here are some problems for which I will not provide solutions:
- Midterm 2009, Problems 1,2.
- Final 2009, Problems 3,4.
- Final 2010, Problems 1,2,4.
- Final 2011, Problems 1,2,4,5.
- Final 2014, Problems 1,2,4,5(a)
(in Problem 2, Future(L,0001) means AccFut_L(0001)).
One or two problems from the Final 2017 were briefly discussed at the
end of class on 12_03.
|
|---|
|