Chapter 15  Limits to Computation: Instructor's CD questions

1. To find a lower bound for problem A we can:
*a) Transform problem B with known lower bound to Problem A.
b) Transform problem A to problem B with known lower bound.

2. When doing algorithm analysis, a "hard" problem is one:
a) That we have trouble finding an algorithm for.
b) That we have trouble defining precisely enough to find an algorithm for.
c) That does not have an algorithm.
*d) For which the best known algorithm requires exponential time.

3. An algorithm is said to be NP if:
a) A random event is involved.
*b) It can be solved in polynomial time on a non-deterministic machine.
c) There are at most possible 2^n solutions to choose between.

4. What can be NP-complete?
a) An algorithm.
b) A program.
*c) A problem.
d) An input.

5. Assume that we know that problem A is NP-complete.  We can prove
that problem B is NP-complete by:
*a) transforming problem A to problem B.
b) transforming problem B to problem A.

6. A practical reason to be familiar with NP-completeness theory is
that:
a) It helps you to solve hard problems in polynomial time.
b) It helps you to write better algorithms.
*c) It helps you to justify why a given program is slow.

7. Some computer programs could be made much faster if we could prove:
*a) That problem class P is equal to problem class NP.
b) That problem class P is not equal to problem class NP.
c) All NP-complete problems can be solved quickly on a non-deterministic
machine.

8. Which problem has not been proved to be NP-complete?
a) TRAVELING SALESMAN
b) CLIQUE
c) VERTEX COVER
*d) TOWERS OF HANOI

9. Which set is uncountable?
a) Integers.
b) Positive integers.
*c) Real numbers.
d) All of the above.

10. Which set is countable?
*a) Programs.
b) Functions that take an integer as input and gives an integer as
output.
c) Functions that take an integer as input and gives a boolean value
as output.
d) a and c.