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:

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

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.