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:

- 3-coloring,
- clique
- subset sum problem, and
- interval computations.

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.