 |
Final Exam Study Guide, Math 421, Fall 2024
More content and corrections may be added to this page.
You will be allowed 2 two-sided sheet of notes
on 8.5 x 11 inch (Letter) sized paper.
The Exam is at 7pm on Tuesday, Dec 10, in PHRM 1201. It consists
of Part 1 (60 minutes), break (15 minutes), Part 2 (65 minutes).
Please remain outside the room until you are invited in.
|
Examinable Material for the Final, 2024 |
- All material covered in class. This is mostly included in the
sources below.
-
The handouts to supplement the textbook:
-
Uncomputability in CPSC 421, Sections 1-7.
-
Non-Regular Languages, and the
Myhill-Nerode Theorem, and Linear Algebra Tests, Sections 1,3,4.
-
Section 1 of
Sneaky Complete Languages
and Notes on Chaper 7 explains some differences in the way
we covered Chapter 7 of [Sip]. (Section 2 of this article will
not be covered.)
-
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.
-
(Theorem 5.1 and an example similar to Theorem 5.2
of Chapter 5 were covered in Sections 2-4 of
the handout "Uncomputability in CPSC 421." Hence this may be
helpful.)
-
Chapter 7 (although we didn't cover all of the examples there).
-
Chapter 8, Sections 1 and 2, and TQBF is PSPACE-complete (start of
Section 3).
-
Chapter 9: you should be able to answer
these true/false questions about our
one-day overview
of the part of Chapter 9 relevant to P vs. NP, i.e.,
Sections 9.2 and 9.3,
on Dec 2 (see class notes from that day).
|
|---|
|
Practice Problems for the Final 2024 |
The following are good practice problems for the final exam:
-
All homework problems, i.e., Homework 1-10 (this year, i.e., 2024),
are good exam study problems.
-
All problems on the
Midterm Study Guide 2024
are recommended, plus the following problems from there
(whose solutions are there):
Problem 1 on Midterm 2014, and Problem 1 on Midterm 2011 (on Turing machines),
and Problem 3 on Midterm 2014 with "421Simple" replaced with "Python"
(on decidable/recognizable languages).
-
All problems from
Midterm 2023
(2023 midterm solutions),
and from
Midterm 2024
(2024 midterm solutions).
-
Here are problems with (sometimes brief) solutions from older exams:
-
Final Exam 2021, Part 1,
Problems 1-4, except 1(a) (i.e., the first true/false question).
Solutions to
Final Exam 2021, Part 1.
-
Final Exam 2021, Part 2,
Problems 2(a,b,c) and all T/F questions of Problem 1 except the fourth and
fifth.
Solutions to
Final Exam 2021, Part 2.
-
Final Exam 2017, Problem 1: 1st, 2nd, 4th, 5th, 6th;
Problems 2,4(a); Problem 5: (e).
(solutions).
-
Final 2004,
Problems 1,5,6,8,9.
For 9(b) the hint--in the terminology we used this year--is to use the
Myhill-Nerode
theorem.
(brief solutions only).
-
More exams may be added.
Here are problems for which I
will not provide solutions:
-
Final Exam 2014,
Problems 1,2,4,5(g,h)
(in Problem 2, Future(L,0001) means AccFut_L(0001)).
-
Final Exam 2011,
Problems 1,2,4,5,8.
Problems 2 and 3 of
supplemental practice problems for the final exam 2023
here are
brief
solutions to the problems.
|
|---|
|
Additional Remarks (Because Some of You Asked...)
|
Remark 1:
You will pass the final exam--and therefore this course--if you
can (COMPLETELY)
correctly solve all problems
asking you to (1) describe a DFA that recognizes a given language,
and/or (2) describe a Turing machine algorithm that
recoginizes a given language.
This usually includes explaining how they work.
Remark 2:
You are allowed 2 double sided 8.5" x 11" sheets of notes on the final exam.
(See above.)
|
|---|
|
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
|
|---|
|