Homeworks for the course

CS 5315, Spring 2016

1. (Due January 27) Translate, step-by-step, the following for-loop into a primitive recursive expression:

int z = a * b; for(int i = 1; i <= c; i++) {z = z * (a + b);}

2. (Due January 27) Translate, step-by-step, the following primitive
recursive expression into a for-loop:
PR(add(π^{2}_{1}, π^{2}_{2}),
σ(π^{4}_{4})). Provide an explicit formula
for the corresponding function.

3. (Due January 27) Prepare a preliminary topic for your class project.

4. (Due February 1) Prove, from scratch (i.e., based only on the definition of a primitive recursive function), that integer division a / b is primitive recursive.

5. (Due February 1) Write down a proof that there exists a computable function which is not primitive recursive. This must be a detailed text, with all the words and all needed formulas, so that a reader who is not familiar with this result will understand and be convinced that this is true. By February 1, it is Ok to have a proof with gaps clearly indicating that some parts are still not clear; a full proof with all details right is expected by February 8.

6. (Due February 3) Prove that division is mu-recursive, similar to how we proved, in class, that subtraction is mu-recursive.

7. (Due February 3) Translate the following while-loop into a mu-recursive expression:

int z = a * b; i = 1; while(z < c) {z = z * (a + b);}

8. (Due February 3) Translate the following mu-recursive
expression into Java code: μc.(add(a,c) ≥ b), where
add = PR(π^{1}_{1},
σ(π^{3}_{3})).

9. (Due February 8) Write down a proof that there exists a computable function which is not primitive recursive. This time, the proof must be absolutely correct.

10. (Due February 8) If A is r.e. and B is decidable, is their union r.e.?is it decidable? is their intersection r.e.? decidable?

11. (Due February 8) Write down, in all needed details, a proof that zero-checker is not possible. Please try to make this proof as complete and clear as possible; it is Ok if there are some minor faults or gaps in your description. The final (absolutely correct) version of this proof is due on February 15.

12. (Due February 8) Prove that a cube-checker is not possible. To
be more precise, prove that no algorithm is possible that, given a
program p that always halts, check whether this program always
computes n^{3}.

13. (Due February 8) Write down the rules of a Turing machine that
computes 0 based on a binary input. Trace your Turing machine
step-by-step on the example of input 01_{2} (i.e., 01 in
binary code). Please do not forget to take into account that we
assume that the binary number is stored in the Turing machine
starting with the lowest bit (in the given example, with 1).

14. (Due February 10, extra credit if returned by February 8)
Write down the rules of a Turing machine that computes the
function π^{3}_{1}. You can assume that numbers
are given in unary code. Trace your Turing machine on the example
of a triple (2,2,1).

15. (Due February 10) Design a Turing machine for computing the
function π^{3}_{2}. Provide a step-by-step
example of how this machine works.

16. (Due February 10) Use the general algorithm for composition to design a Turing machine that computes a function f(n) = (n + 1) + 1; assume that the input n is given in binary code.

17. (Due February 15) Write down, in all needed details, a proof that zero-checker is not possible. This time the proof must be absolutely correct.

18. (Due February 15) Give two examples:

- an example when an algorithm is feasible in the sense of the formal definition but not practically feasible, and
- an example when an algorithm is practically feasible, but not feasible according to the formal definition.

19. (Due February 15) Similarly to a Turing machine that we had in
class, that copies a number in unary code, design a Turing machine
that copies a binary number. Test it on the example of a binary
number 110 (stored as 011). The result should be 110_110, with a
blank space in between. *Hint*: instead of marking 1s, mark
both 0s and 1s; instead of state carry, we can now have two
different states: carry0 and carry1.

20. (Due February 15) For the Turing machine that you designed in Problem 16, trace how it works for n = 1. Describe, for each step, how the corresponding state of the Turing machine can be represented as two stacks, and what pops and pushes are involved in each transition.

21. (Due February 22) Logarithms were invented to make multiplication and division faster: they reduce:

- multiplication to addition and
- division to subtraction

- instead of directly
computing the product y = x
_{1}* x_{2}, we first compute X_{1}= ln(x_{1}) and X_{2}= ln(x_{2}), then compute Y = X_{1}+ X_{2}, and then y = exp(Y); - instead of directly computing the ratio
y = x
_{1}/ x_{2}, we first compute X_{1}= ln(x_{1}) and X_{2}= ln(x_{2}), then compute Y = X_{1}- X_{2}, and then y = exp(Y).

22. (Due March 2) Submit progress report on your class project.

23. (Due March 16) Illustrate step-by-step a general reduction of problems from the class NP to propositional satisfiability on the example of the following simple problem:

- given a string x,
- return a string y of the same length for which the following property C(x, y) is satisfied: x implies y.

*Comment.* This illustration should be similar to what we
described in class, the only difference is that in class, we
considered a different property C(x, y): the property that x =
y.

24. (Due March 23) Take any formula in CNF and show how checking its satisfiability can be reduced to checking satisfiability of a 3-CNF formula.

25. (Due March 28) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to coloring a graph in 3 colors.

26. (Due March 28) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to an instance of the subset sum problem (i.e., the problem of exact change).

27. (Due March 30) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to an instance of the clique problem.

28. (Due March 30) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to an instance of the interval computation problem.

29. (Due April 4) Show how to compute the product of eight numbers in parallel if we have an unlimited number of processors. How many processors do we need and how much time will this computation take? Why do we need parallel processing in the first place?

30. (Due April 4) If we take into account communication time, how fast can you compute the product of n numbers in parallel?

31. (Due April 6) Suppose that we have a probabilistic algorithm that gives a correct answer half of the time. How many times do we need to repeat this algorithm to make sure that the probability of a false answer does not exceed 1%? Give an example of a probabilistic algorithm. Why do we need probabilistic algorithms in the first place?

32. (Due April 11) Pick an example of an Ali-Baba problem, and explain, step by step, what solution two greedy algorithms will produce for this example.

33. (Due April 13) Solve problems 4-12 from last year's Test 3.

34. (Due April 25) Use the variable-elimination algorithm for
checking satisfiability of 2-SAT formulas that we had in class to
find the values that satisfy the following formula:

(a \/ ~b)
& (~a \/ b) & (~a \/ ~b) & (a \/ ~c) & (~a \/ ~c) & (b \/ ~c).

35. (Due May 2) What class of the polynomial hierarchy contains
Σ_{2}P^{Π2P}?