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

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 product of 10 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 product 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 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 100, 200, 300, and 100, and value 150, 400, 150, and 200. The overall weight is limited by 500. 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.