Theory of Computations,
Test 3 for the course
CS 5315, Spring 2016

Name: _____________________________________________________

1-4. Reduce the satisfiability problem for the formula (a \/ ~b) & (~a \/ b) & (a \/ b \/ c) to:

5. What do we gain when we prove that a problem is NP-hard? Explain one negative consequence (what we cannot do) and one positive one (what we can do).

6. Show how to compute the minimum of 7 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?

7. If we take into account communication time, how fast can you compute the minimum of n numbers in parallel?

8. 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 0.1%? Give an example of a probabilistic algorithm. Why do we need probabilistic algorithms in the first place?

9. Let us consider the following particular case on an Ali-Baba problem: we have 4 objects with weights 10, 20, 30, and 10, and value 15, 40, 15, and 20. The overall weight is limited by 50. Show, step by step, what solution two greedy algorithms will produce for this example.

10. Give two examples of how non-Euclidean physics can potentially help solve NP-hard problems in polynomial time.