## Exercises #### Section 8.1 1. Let us assume that a search does not start at the beginning of a list when the Sequential Search algorithm ([Alogrithm 1.1](LiB0008.html#27)) is used, but rather starts wherever the list index was left at the termination of the preceding search. Let us further assume that the item for which we are searching is selected randomly and independently of the destinations of previous searches. Under these assumptions, what would be the average number of comparisons? 2. Let *S* and *T* be two arrays of *m* and *n* elements, respectively. Write an algorithm that finds all the common elements and stores them in an array *U.* Show that this can be done in Θ (*n + m*) time. 3. Improve the Binary Search algorithm ([Alogrithm 1.5](LiB0009.html#38)) assuming a successful search. Analyze your algorithm and show the results using order notation. 4. Show that, if *x* is in the array and is equally probable to be in each of the array slots, the average-case time complexity for Binary Search ([Alogrithm 1.5](LiB0009.html#38)) is bounded approximately by  *Hint*: By [Lemma 8.4](LiB0068.html#783), for some *k, n* − (2*k* − 1) is the number of nodes at the bottom level. The contribution to the *TND* for those nodes is equal to (*n* − 2*k* − 1) (*k* + 1). Add this expression to (*k* − 1) 2*k* + 1 (the formula established in the average-case analysis of Binary Search) to obtain the *TND* for the decision tree. 5. Suppose that all of the following 2*n* + 1 possibilities are equally probable:  Show that the average-case time complexity of the Binary Search algorithm ([Alogrithm 1.5](LiB0009.html#38)) is bounded approximately by  *Hint*: See the hint for Exercise 4. 6. Complete the proof of [Lemma 8.6](LiB0068.html#786). #### Section 8.2 1. Implement the Binary Search, Interpolation Search, and Robust Interpolation Search algorithms on your system and study their best-case, average-case, and worst-case performances using several problem instances. 2. Show that the average-case time complexity of Interpolation Search is in Θ (lg (lg *n*)), assuming the keys are uniformly distributed and that search key *x* is equally probable to be in each of the array slots. 3. Show that the worst-case time complexity of Interpolation Search is in Θ ((lg *n*)2), assuming the keys are uniformly distributed and that search key *x* is equally probable to be in each of the array slots. #### Section 8.3 1. Write an algorithm that finds the largest key in a binary search tree. Analyze your algorithm, and show the results using order notation. 2. [Theorem 8.3](LiB0070.html#801) states that, for a successful search, the average search time over all inputs containing *n* keys, using binary search trees, is in Θ (lg *n*). Show that this result still holds if we consider an unsuccessful search as well. 3. Write an algorithm that deletes a node from a binary search tree considering all possible cases. Analyze your algorithm and show the results using order notation. 4. Write an algorithm that creates a 3–2 tree from a list of keys. Analyze your algorithm and show the results using order notation. 5. Write an algorithm that lists all the keys in a 3–2 tree in their natural order. Analyze your algorithm and show the results using order notation. #### Section 8.4 1. Another clash (collision) resolution strategy is linear probing. In this strategy, all the elements are stored in the array of buckets (hash table). In the case of a clash, the table is searched for the next available (free) bucket. Show how linear probing resolves clashes that occur in the problem instance of [Figure 8.8](LiB0071.html#809). (Linear probing is also known as closed hashing.) 2. Discuss the advantages and disadvantages of the two clash resolution strategies, open hashing and linear probing (see Exercise 15). 3. Write an algorithm to delete an element from a hash table that uses linear probing as its clash resolution strategy. Analyze your algorithm and show the results using order notation. 4. A rehashing scheme known as double hashing uses a second hash function in case of a clash. If the first hash function is *h* and the second hash function is *s*, the entire sequence of positions of the hash table that will be checked for an available bucket is given by the following equality, where *pi* is the *i*th position in the sequence:  (% returns the remainder when the first operand is divided by the second.) Define a second hash function for the problem instance of [Figure 8.8](LiB0071.html#809) and show the table after all the keys have been inserted into the hash table. #### Section 8.5 1. Modify [Alogrithm 8.4](LiB0072.html#828) (Find Smallest and Largest Keys by Pairing Keys) so that it works when *n* (the number of keys in the given array) is odd and show that its time complexity is given by  2. Complete the proof of [Theorem 8.8](LiB0072.html#838). That is, show that a deterministic algorithm that finds the smallest and largest of *n* keys only by comparisons of keys must in the worst case do at least (3*n* − 3) /2 comparisons if *n* is odd. 3. Write an algorithm for the method discussed in [Section 8.5.3](LiB0072.html#840) for finding the second-largest key in a given array. 4. Show that for *n* in general, the total number of comparisons needed by the method discussed in [Section 8.5.3](LiB0072.html#840) for finding the second-largest key in a given array is  5. Show that the median of five numbers can be found by making six comparisons. 6. Use induction to show that the worst-case time complexity of [Alogrithm 8.6](LiB0072.html#856) (Selection Using the Median) is bounded approximately as follows:  7. Show that for an arbitrary *m* (group size), the recurrence for the worst-case time complexity of [Alogrithm 8.6](LiB0072.html#856) (Selection Using the Median) is given by  where *a* is a constant. This is Recurrence 8.2 in [Section 8.5.4](LiB0072.html#848). 8. Use induction to show that *W (n*) ∊ Ω (*n* lg *n*) for the following recurrence. This is Recurrence 8.2 in [Section 8.5.4](LiB0072.html#848) where *m* (group size) is 3.  9. Show that the constant *c* in the inequality  in the expected-value time complexity analysis of [Alogrithm 8.7](LiB0072.html#864) (Probabilistic Selection) cannot be less than 4. 10. Implement [Algorithms 8.5](LiB0072.html#849), [Algorithms 8.6](LiB0072.html#856), and [Algorithms 8.7](LiB0072.html#864) (Selection algorithms for finding the *k*th-smallest key in an array) on your system and study their best-case, average-case, and worst-case performances using several problem instances. 11. Write a probabilistic algorithm that determines whether an array of *n* elements has a majority element (the element that appears the most). Analyze your algorithm and show the results using order notation. #### Additional Problems 1. Suppose a very large sorted list is stored in external storage. Assuming that this list cannot be brought into internal memory, develop a searching algorithm that looks for a key in this list. What major factor(s) should be considered when an external search algorithm is developed? Define the major factor(s), analyze your algorithm, and show the results using order notation. 2. Discuss the advantages of using each of the following instead of the other: 1. A binary search tree with a balancing mechanism 2. A 3–2 tree 3. Give at least two examples of situations in which hashing is not appropriate. 4. Let *S* and *T* be two arrays of *n* numbers that are already in nondecreasing order. Write an algorithm that finds the median of all 2*n* numbers whose time complexity is in Θ (lg *n).* 5. Write a probabilistic algorithm that factors any integer using the functions *prime* and *factor.* Function *prime* is a boolean function that returns "true" if a given integer is a prime number and returns "false" if it is not. Function **factor** is a function that returns a nontrivial factor of a given composite integer. Analyze your algorithm, and show the results using order notation. 6. List the advantages and disadvantages of all the searching algorithms discussed in this chapter. 7. For each of the searching algorithms discussed in this chapter, give at least two examples of situations in which the algorithm is the most appropriate.