CS254 Spring 2003Practice Midterm 1
The practice midterm is below. Here are some facts about the actual
midterm: (a) The midterm will be in class . (b) It is
closed book, closed notes. Nothing will be permitted on your desk except
your pen (pencil) and test. (c) You should bring photo ID.
(d) There will be more than one version of the test. Each version
will be of comparable difficulty. (e) 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. (f) One problem (less typos)
on the actual test will be from the practice test.
1. Show directly that N! is O(en log n).
2. Give a TM (either a diagram or give its transition table you can
use more than one tape) that takes an input x and ouputs the string x
in reverse.
3. Redo problem 2. But this time give a RAM that does the same thing.
4. Show that that the language
L={x;y;z : x,y,z are strings over {0,1} such that x+y=z }
is in LOGSPACE.
5. Suppose L is decided by a one-tape machine M in time f(n). Show there
is a k-tape machine M' for some k that uses the same alphabet as M
and decides L in time εf(n) + n + 2.
6. Show the language L=
{<M> : for each n, M accepts exactly half the strings of length n}
is not recursive.
7. A many-one reduction from one language L to another L' is a recursive
function f such that x ∈L iff f(x)∈L'.
Show the halting problem language H is not many-one reducible to the
complement of H.
8. A circuit C is monotone if it does not use NOT gates.
The function HALFn(x1,...xn) is true iff at least half of its
inputs are
true. Give a monotone circuit for HALFn.
9. Prove that if f and g are proper complexity functions so is f + g.
10. Prove coNTIME(N2)is not a subset of NTIME(N).
|