THEORY OF COMPUTATION
Homeworks for the course CS 5315, Spring 2010

1. (Due January 28) Prove that the function n! is primitive recursive.

2. (Due January 28) Prove that the function n2 + 3n + 5 is primitive recursive.

3. (Due January 28) Prove that the difference a - b is primitive recursive.

4. (Due February 2) Prove that a complex if-then statement "if P then f elseif Q then g else h" is primitive recursive -- provided, of course, that the corresponding functions and conditions P, f, Q, g, and h are primitive recursive.

5. (Due February 2) Prove that integer division / is primitive recursive.

6. (Due February 2) Reproduce the proof that we had in class, that not every computable function is primitive recursive.

7. (Due February 4) Let us define an Ackermann-primitive recursive function as a function that can be obtained from 0, successor function, projections, and the Ackermann function by using composition and primitive recursion. Prove that not every computable function is Ackermann-primitive recursive. Hint: our proof that not every computable function is primitive recursive does not actually use the fact that the standard definition of the primitive recursive function only allows three basic functions: 0, successor function, and projections.

8. (Due February 9) Prove that the division function is mu-recursive.

9. (Due February 11) Design a Turing machine for computing the function n + 2.

10. (Due February 11) Design a Turing machine for computing n - 1.

11. (Due February 11) Design a Turing machine for computing π31, i.e., a function that takes a triple and returns the first number from this triple.

12. (Due February 16) Design a Turing machine for computing π32, i.e., a function that takes a triple and returns the second number from this triple.

13. (Due February 16) Take two Turing machines for computing two functions f(n) and g(n) and use an algorithm that we described in class to design a Turing machine that computes their composition.

14. (Due February 18) Provide a general description of how a Turing machine would implement primitive recursion (for-loop).

15. (Due February 18) Provide a general description of how a Turing machine would implement mu-recursion (while-loop).

16. (Due February 23) Reproduce the proof (that we had in class) that halting problem is undecidable.

17. (Due February 23) Prove that the difference and the symmetric difference between two decidable sets are both decidable.

18. (Due February 25) A factorial-checker is a function that, given a program that always halts, checks whether this program always correctly compute n!. Prove that factorial-checkers are impossible.

19. (Due March 25) On an example, show how satisfiability for CNF formulas can be reduced to the 3-SAT problem (propositional satisfiability for 3-CNF formulas in which each clause has no more than 3 literals).

20. (Due March 25) On an example, show how 3-SAT can be reduced to Clique problem.

20a. (Due March 25) On an example, show how 3-SAT can be reduced to the subset sum problem.

21. (Due March 25, for extra credit; due April 6, for regular credit) On an example, show how 3-CAT can be reduced to the 3-coloring problem: given a graph, check whether this graph can be colored in 3 colors.

22. (Due April 6) Prove that the following 4-coloring problem is NP-hard: given a graph, check whether this graph can be colored in 4 colors.

23. (Due April 6) On an example, show how 3-SAT can be reduced to interval computations.

24. (Due April 13) Show, step by step, how to compute the maximum of 8 numbers in parallel in the shortest possible time.

25. (Due April 13) Show, step by step, how to compute the product of two 2 X 2 matrices in parallel -- in shortest possible time.

26. (Due April 15) If a probabilistic algorithm produces a result with the probability of error 1/4, how many times doe we need to repeat it to reduce the probability of error to 10-6?

27. (Due April 15) Pick a satisfiability problem and apply a greedy algorithm to it.

28. (Due April 15) Pick an example of a knapsack problem and apply both greedy algorithms to it.

29. (Due April 20) Pick an example of a quadratic function, ideally of two variables, pick intervals for these variables, and do the following:

30. (Due April 20) Find what is Σ3PΠ2P.