 |
Final Exam Study Guide, CPSC 421/501, FALL 2021
More content and corrections may be added to this page, especially the
"Additional Remarks" part below.
Examinable Material (Course Coverage) |
- The handouts to supplement the textbook based on recent content:
-
this article on the Myhill-Nerode theorem.
-
The handouts to supplement the textbook based on 2004 -- ???? content:
-
All but Section 7.9 of
Self-Referencing, Uncountability
and Uncomputability in CPSC 421;
-
Sections 1-3 and part of Section 4 of
The Cook-Levin
Theorem and how to solve and not to solve P versus NP,
-
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.
-
Orale Turing machines, Section 6.3, Section 9.2, and
"Turing reducibility," Section 6.3
(see also class notes: DATES HERE)
-
Sections 7.1-7.3
-
Remarks and additional material:
- The topics covered
in the CPSC 501 presentations in the last two weeks of class are
not directly examinable.
-
If you are interested in taking CPSC 536F for Spring 2022, you be
interested
this introduction to circuit complexity
(last revised 1:03pm on Nov 26, 2020).
|
Practice Problems for the Final Exam
Based on Material Up To 2020
|
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;
Problems 2,4 (completely); Problem 5: (c,e).
(solutions).
- Midterm 2019. (All problems.)
(solutions).
- Midterm 2014, Problems 1,2(b,c,d).
Also 2(a), where "Axiom 1" is replaced with the axioms/conditions that
must hold of an "expressive Program-Input" system.
(solutions).
- Midterm 2011,
(All problems; Problem 2 assumes that you are talking about an
"expressive Program-Input system.")
(solutions).
- Midterm 2010,
All problems except 4(b); note in problem 3, our notation in 2021
is slightly different, but the Result, EncodeBoth is the same;
moreover, Axiom 2 simply asserts the existence of a universal
program in a Program-Input system.
(solutions).
Here are some problems with some brief solutions:
- Final 2004,
Problems 1,5,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,4. (Same comment on L_yes as above, i.e., L_yes is
the acceptance problem, i.e., ACCEPTANCE, in any Program-Input under
the various assumptions we needed to prove that ACCEPTANCE is
undecidable.)
- Final 2009,
Problem 3.
- Final 2010,
Problems 1,2,4,7.
- Final 2011,
Problems 1,2,4,6,7,8.
- Final 2014,
Problems 1,2,5(a,e,f)
(in Problem 2, Future(L,0001) means AccFut_L(0001)).
|
Practice Problems for the Final Exam
Based on New Material as of 2021
|
All homework problems and the problems on the midterm are good practice
problems.
These documents will likely have additional problems added
on December 14 and 15:
See also the
supplemental questions
, and
some brief solutions
.
|
UNDER CONSTRUCTION!!
Additional Remarks (Because Some of You Asked);
|
Remark 0:
See the course piazza page for other remarks regarding
the final exam.
Remark 1:
You will pass the final exam--and therefore this course--if you
can (COMPLETELY)
correctly solve all problems
asking you (1) formally describe a DFA that recognizes a given language,
and (2) all problems asking you
to describe a Turing machine algorithm
(high-, implementation-, and/or formal-level descriptions) that
recoginizes a given language.
[Warning: you should know what the above terms mean. Of course,
there is no way to
precisely describe at which point a high-level description becomes an
implementation-level description, etc., but the instructor and TA's should
be able to give you a reasonable idea.]
Remark 2:
You are allowed 2 double sided 8.5" x 11" sheets of notes on the final exam.
Remark 3:
Remark 4:
Remark 5:
|
---|
|