Solutions to other chapters:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  
Java Methods Home Page Skylight Publishing



Java Methods A & AB:
Object-Oriented Programming and Data Structures

Answers and Solutions to Exercises

Chapter 18

1.
(a) T
(b) T -- log2n = log10n * log210
2. (a) O(n2)
(c) O(n)
3. (c) O(log n)
4. (a) P
(c) E.  This task is equivalent to finding the largest clique in a graph.  (A graph is a set of nodes with edges connecting some of the nodes; a set of nodes in a graph is called a clique if any two nodes in that set are connected with an edge.)   In complexity theory, there is a proof that this is what is called an NP-complete problem: it is equivalent to a whole class of problems for which no polynomial-time algorithms are known and are unlikely to be ever discovered.
7. (a) always
(b) sometimes
10. (b) F




Copyright © 2006 by Skylight Publishing