538
Graphs and Trees
15. One of five coins is counterfeit and is lighter than the other four. The problem is to identify the counterfeit coin.
a. What is the number of final outcomes (the number of leaves in the decision tree)?
b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.
c. Devise an algorithm that meets this lower bound (draw its decision tree).
16. One of five coins is counterfeit and is either too heavy or too light. The problem is to identify the counterfeit coin and determine whether it is heavy or light.
a. What is the number of final outcomes (the number of leaves in the decision tree)?
b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.
c. Devise an algorithm that meets this lower bound (draw its decision tree).
17. One of four coins is counterfeit and is either too heavy or too light. The problem is to identify the counterfeit coin but not to determine whether it is heavy or light.
a. What is the number of final outcomes (the number of leaves in the decision tree)?
b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.
c. Devise an algorithm that meets this lower bound (draw its decision tree).
18. One of four coins is counterfeit and is either too heavy or too light. The problem is to identify the counterfeit coin and determine whether it is heavy or light.
a. What is the number of final outcomes (the number of leaves in the decision tree)?
b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.
c. Prove that no algorithm exists that can meet this lower bound. (Hint: The first comparison can be made
with either two coins or four coins. Consider each case.)
19. Devise an algorithm to solve the problem of Exercise 18 using three comparisons in the worst case.
20. One of eight coins is counterfeit and is either too heavy or too light. The problem is to identify the counterfeit coin and determine whether it is heavy or light.
a. What is the number of final outcomes (the number of leaves in the decision tree)?
b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.
c. Devise an algorithm that meets this lower bound (draw its decision tree).
21. In the decision tree for the binary search algorithm (and the binary tree search algorithm), we have counted
each internal node as one comparison. For example, the top of Figure 6.53 looks like this:
To get to either of the child nodes of the root, we have assumed that one comparison has been done.
However, the outcome of the comparison at each internal node is really a threeway branch:
x = node element
x < node element
x > node element
Think about how this threeway branch would be implemented in most programming languages, and write
a more accurate expression than 1 + :log n; for the number of comparisons in the worst case.
Graphs and Trees
15. One of five coins is counterfeit and is lighter than the other four. The problem is to identify the counterfeit coin.
a. What is the number of final outcomes (the number of leaves in the decision tree)?
b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.
c. Devise an algorithm that meets this lower bound (draw its decision tree).
16. One of five coins is counterfeit and is either too heavy or too light. The problem is to identify the counterfeit coin and determine whether it is heavy or light.
a. What is the number of final outcomes (the number of leaves in the decision tree)?
b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.
c. Devise an algorithm that meets this lower bound (draw its decision tree).
17. One of four coins is counterfeit and is either too heavy or too light. The problem is to identify the counterfeit coin but not to determine whether it is heavy or light.
a. What is the number of final outcomes (the number of leaves in the decision tree)?
b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.
c. Devise an algorithm that meets this lower bound (draw its decision tree).
18. One of four coins is counterfeit and is either too heavy or too light. The problem is to identify the counterfeit coin and determine whether it is heavy or light.
a. What is the number of final outcomes (the number of leaves in the decision tree)?
b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.
c. Prove that no algorithm exists that can meet this lower bound. (Hint: The first comparison can be made
with either two coins or four coins. Consider each case.)
19. Devise an algorithm to solve the problem of Exercise 18 using three comparisons in the worst case.
20. One of eight coins is counterfeit and is either too heavy or too light. The problem is to identify the counterfeit coin and determine whether it is heavy or light.
a. What is the number of final outcomes (the number of leaves in the decision tree)?
b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.
c. Devise an algorithm that meets this lower bound (draw its decision tree).
21. In the decision tree for the binary search algorithm (and the binary tree search algorithm), we have counted
each internal node as one comparison. For example, the top of Figure 6.53 looks like this:
To get to either of the child nodes of the root, we have assumed that one comparison has been done.
However, the outcome of the comparison at each internal node is really a threeway branch:
x = node element
x < node element
x > node element
Think about how this threeway branch would be implemented in most programming languages, and write
a more accurate expression than 1 + :log n; for the number of comparisons in the worst case.