1. a. If all comparisons and assignment statements take the same amount of time to execute, then compare the execution times of the first linear search procedure and the procedure revised for greater efficiency.
b. For what values of n will the binary search be faster than the linear search of the improved procedure in the worst case?
2. When you look up a book by author in the library, what kind of a search are you doing?
3. In a ternary search of a sorted array, the array is divided into three "nearly" equal parts and searched. Key values are examined "near" 1/3 and "near" 2/3 and compared with the search key to determine in which third to search further. Determine the worst-case time for this search and compare it to the worst-case time for a binary search.
4. Suppose a sorted array stores 1,000 integers between 0 and 1,000,000. A pointer array indicates where the least integer greater than 1,000 x (i - 1) but not greater than 1,000 x i appears in the array. P[i] contains that pointer for i = 1, 2, . . . , 1,000. If no such integer is in the array, then p[i] = 0. Write a function to do an interpolation search, coupled with a binary search.
5. Assuming all comparisons and assignments take the same time to execute, do the following.
a. Determine the worst-case times for the sorts of the procedures given in the text for the maximum entry sort, the bubble sort, and the insertion sort.
b. For each value of n, determine which of the three sorts has least worst-case time.
6. What input order produces the worst case time for
a. The bubble sort?
b. The insertion sort?
7. Write a function to carry out the bubble sort when the integers are stored in a chain.
8. Write a function to carry out the insertion sort when the integers are stored in a chain.
9. Modify the insertionsort function so that it does a binary search for the proper insertion position, and then does the insertion.
10. Modify the function so that it does not deal with the last i elements after the ith pass.
11. Suppose input is given in the order
16, 18, 22, 15, 4, 50, 17, 31, 4, 90, 6, 25
Create the heap produced by
a. The first heap creation algorithm of Section 8.4.
b. The second heap creation algorithm of Section 8.4.
c. How many comparisons and interchanges were required in Exercise 11(a) and Exercise 11(b)?
12. For each heap of Exercise 11(a) and 11(b), produce
a. The reheaped heap after the root element is removed using the first reheaping algorithm of Section 8.4.
b. The reheaped heap after the root element is removed using the second reheaping algorithm of Section 8.4.
c. How many comparisons and interchanges were required in Exercises 12(a) and12(b)?
13. Why does the pointer array of Section 8.3.6 fail to help?
14. Show the entries of the data array, for the input of Exercise 11, when the heapsort function is applied after the first three elements have been output.
15. Modify the heapsort function so that it counts the number of interchanges and comparisons in each phase and returns their values as parameters.
16. Modify the heapsort function so it sorts a data array of pointers to records instead of records themselves.
17. What input sequence will cause the second heap creation algorithm to take worst-case time? Calculate the number of comparisons and interchanges it requires.
18. Determine the number of comparisons and copies required by quicksort for an array of n records, which is (a) in sorted order; (b) in reverse sorted order; (c) in order so that partition always produces two component arrays whose lengths differ by at most 1.
19. Modify partition so that it selects an entry at random to be used as the basis entry.
20. Modify partition so that it selects the median of the first, middle, and last entries as a basis entry.
21. Explain why the implementation given for quicksort requires a stack depth O(lg n).
22. Modify quicksort so that it sorts all component arrays of length at most 20 by using insertionsort.
23. Generation of n integers to fill the array a in Section 8.6 randomly was really only an approximation of a random input. This is because duplicate values might occur. While the effect of this duplication may be negligible for the simulation results, a "true" random input can be generated. You can fill array a as follows: For i from 1 to n, set a[i] to i.Then, for i from 1 to n, pick an integer int at random between i and n, and interchange a[i] and a[int].
a. Convince yourself that this will generate a "'true" random input.
b. Write a procedure to generate this "true" random input.
24. Consider the "perfect shuffle" example of Chapter 3. When 2n - 1 is a prime number p, then the number of shuffles required is p - 1. The initial configuration is in sorted order, and so is the final configuration after p - 1 shuffles. The configurations produced along the way represent different permutations of the initial input. With successive reshufflings, the configurations seem more and more like a "random" arrangement, and then less and less like a "random" arrangement. Take p = 101 and use the one hundred configurations, produced by the hundred shuffles required to reproduce the original, as inputs to the heapsort algorithm. Output the statistics table based on one hundred samples of an input of size 101.