CPSC 411: Review for Final Exam
Fall 2008
You may bring two 8.5-by-11 inch sheets of paper with your own
notes on it to the exam. You may write on both sides.
The exam will be cumulative, so all the material since the first
day of class will be fair game.
Refer to the review sheets for Exams 1 and 2.
In addition,
review the lectures from Nov 18 through Dec 2.
Here is a detailed list
of what was covered (cf. slides set 12):
- Church-Turing thesis
- existence of uncomputable functions based on diagonalization argument
- uncomputability of the Halt function based on diagonalization construction
- many-one reductions
- showing a problem is undecidable using reduction from the halting problem
- Rice's theorem (applies to nontrivial functional properties of programs)
Also review:
Quiz 12 and its solution (given in class).
Homework 8 and its solution.
The format of the exam will be some short answers and some
"work-out" problems.