CS154 Spring 2003Practice Final
The practice final is below. Here are some facts about the actual
final: (a) The final will be in class May 21, 12:15pm-2:30pm.
(b) It is closed
book, closed notes. Nothing will be permitted on your desk except
your pen (pencil) and test. (c) It has six problems and will cover the whole
semester's material. Of these six problem one will be from before
the first midterm, one from between midterm 1 and 2, and the remaining problem will be
from after the second midterm.(d) You should bring photo ID.
(e) There will be more than one version of the test. Each version
will be of comparable difficulty. (f) If your cell-phone or beeper
goes off you will be excused from the test at that point and graded
on what you have done till your excusal. (g) One problem (less typos)
on the actual test will be from the practice test.
1. Show that the class of recursively enumerable languages is not closed under
complementation.
2. Consider the problem of whether a given Turing machine ever uses more than k tape squares. Is this problem decidable? Prove your answer.
3. Prove there is a number k such that the problem of determining whether a Turing machine M uses more than k of its states is undecidable.
4. Let B(n) be the busy beaver function. Let L be the language consisting
of strings x;y such that y <= B(x). Show this language is not
recursive.
5. With repect to the alphabet {0,1, start, space}, let K(x) be the smallest number n such that n viewed as a binary string is the encoding of a TM which
on a blank tape outputs x. Is x recursive? Prove your answer.
6. Let L be the language consisting of strings of the form M;w such that M
on input
w accepts in fewer that w|w| steps. Show this language is not
in P.
7. Show that Eulerian Cycle is in P.
8. Let coNP be those languages whose complement is in NP. Show that if NP
is not
equal to coNP then P is not equal to NP.
9. Show 3-Colorability is NP-complete.
10. Show that there is a fixed number k such that the Bounded Tiling Language
remains NP-complete even when our set of tiles is restricted to be of size k.
|