1. Given the following sequence of integers: 3, 9, 2, 15, -5, 18, 7, 5, 8
2.
1. What is the average number of comparisons for a successful
search assuming all entries are searched with equal
probability? Show your work.
2. Suppose the search probabilities for the elements of this list
are, respectively: 0.1, 0.3, 0.05, 0.2,
0.05, 0.1, 0.05, 0.1, 0.05
3.
What is the average number of comparisons for successful
search with these search probabilities? Show your work.
4. Rearrange the list entries in a way that would result in the
lowest number of comparisons on the average for successful search, given the above probabilities of search. What is this lowest number of comparisons? Show your work.
3. SOLUTION
1. In a sequential search of a list, it takes one comparison to succeed at the first element, two comparisons to succeed the second element, and so on. In general it takes i comparisons to succeed at the i-th element. With the assumption that all entries are searched with equal probability, the formula is:
(1 + 2 + 3 + 4 + … + n) / n = n*(n + 1)/2*n = (n + 1)/2 = (9+1)/2 = 5
2.
3. If the search probabilities are changed according to the given example, the average # of comparisons should be computed as follows:0.1 x 1 + 0.3 x 2 + 0.05 x 3 + 0.2 x 4 +
4. 0.05×5+0.1×6+0.05×7 +0.1×8+0.05 x9 = 4.1
5.
6. We should rearrange the entries such that entries with high search probabilities come first in the list. For example the entry “9” should be the first item since it has the highest search probability. Following this procedure, the new list
4. 5.
6. 7. 8. 9.
10. 11.
12. 13. 14. 15. 16.
17. 18. 19. 20. 21. 22. 23. 24.
should be arranged like this: 9 15 {3,5,18}
{2,-5,7,8} 7.
The entries in the brackets can be arranged in an arbitrary order since they have the same search probabilities.
An adaptive algorithm to lower average match time for sequential search is to move an item by one spot toward the front every time it is matched. (Unless it is already at the front, in which case nothing is done on a match.) Complete the following modified sequential search on a linked list with this move-toward-front adaption. Assume a generic Node class with data and next fields. public class LinkedList
private Node
int size;
…
// moves the target one place toward the
front
// doesn’t do anything if target is in the
first node
// returns true if target found, false
public boolean moveTowardFront(T target) {
// COMPLETE THIS METHOD
} }
otherwise
SOLUTION
public boolean moveTowardFront(T target) {
// COMPLETE THIS METHOD
Node ptr=front, prev=null;
while (ptr != null) {
if (ptr.data.equals(target)) {
break;
} else {
prev = ptr;
ptr = ptr.next;
25.
26. }
27. if
28.
29. }
30. if
}
(ptr == null) { // not found
return false;
(prev == null) { // front node, do
return true;
nothing
32. }
31.
33. //
switch with previous 34. T temp = prev.data;
35. prev.data = ptr.data;
36. ptr.data = temp;
37. return true;
38. }
39.
40. Draw the comparison tree for binary search on a sorted array of length 11.
1. What is the worst case number of comparisons for success? For failure?
2. What is the average number of comparisons for success, assuming equal likelihood of success at any spot?
3. What can you say about the average number of comparisons for failure? Can you approximate it within a small range? Does it depend on the distribition of the probabilities of failing at the various failure spots?
41. SOLUTION
For the comparison tree, the nodes have the index positions where comparisons are made:
(5) =
42.
43. = (2) (8) =
44. 45.=(0) (3)= =(6) (9)= 46.
47.
48. 49. 50. 51.
F(1)= F(4)= F(7)= F(10)=
FF FF FF FF
1. Worst case #comparisons for success = 7 (for positions 1, 4, 7, 10), worst case #comparisons for failure = 8 (for failures off the positions 1, 4, 7, 10)
2. Average #c for success = (1*1 + 2*3 + 4*5 + 4*7)/11 = 5
3. It would take 6 comparisons to get to any of the failure nodes at the last but one level, and 8 comparisons for the last. So the average MUST be between 6 and 8, no matter what the probability distribution is over all of these possibilities.
52.
53.* A variant of binary search, called lazy binary search, works as described in the following algorithm, where t is the target to search, and n is the size of the array:
54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69.
left <-- 0
right <-- n-1
while (left < right) do
mid <-- (left + right)/2
if (t > A[mid]) then
left <-- mid + 1
else
right <-- mid
endif
endwhile
if (t == A[left]) then
display "found at position", left
else
display "not found"
endif
1. Trace this algorithm on the following array, with 46 as the search target: 10 15 25 30 45 46 48 72 76 80 93
2.
How many comparisons are made by the time a match is found? How does your answer compare with that for regular binary search?ANSWER
4; while it takes 1 for regular binary search.
3. Repeat with 40 as the target. How many comparisons are made until failure is detected? How does your answer compare with that for regular binary search?ANSWER
5; while it takes 8 for regular binary search.
4. Draw the comparison tree for lazy binary search on an array of length 11 (same length as the example array above).SOLUTION
Actual values in the array are used instead of the index positions, for better clarity.
Note that the comparison t > A[mid] is labeled on the right branch, and its flip (≯) is labeled on the left branch, instead of against the A[mid] value itself because this makes for
easier counting as you descend the tree. (Only one comparison is actually made, so that whether you take the left or right branch, you will only count one comparison.) Also, for the comparison t == A[left] after exiting the loop, the
comparison is marked against the value in the tree, and the flip side of this comparison will result in falling through to the failure node.
1. What is the worst case number of comparisons for success? For failure?ANSWER
Worst case #comparisons for success = 5, same for failure
2. What can you say about the range of values for the average number of comparisons for success? For failure? ANSWER
Success happen at the last second-to-last and the third- to-last levels. For any success node in the second-to-last level the number of comparisons is 5, and for the third- to-last level is 4. So the average MUST be in the range 4 to 5.
Failure happens at the last and second-to-last levels. For any failure node in the last level the number of comparisons is 5, and for the second-to-last level is 4. So the average MUST be in the range 4 to 5.
3. Under what conditions is it preferable to use lazy binary search over the regular binary search?ANSWER
Lazy binary search is better when there are more failures than successes since failures take fewer comparisons on average. While matches at certain positions now take longer to get to, the average number of comparisons is reduced since the new tree is less than double the height of the old, but the number of comparisons is halved. So, in sum, lazy binary search reduces the average number of comparisons for both successes and failures, and it levels the playing field over successes and failures.