7.1 Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5 using insertion sort. - Get solution
7.2 What is the running time of insertion sort if all elements are equal? - Get solution
7.3 Suppose we exchange elements a[i] and a[i+k], which were originally out of order.
Prove that at least 1 and at most 2k − 1 inversions are removed. - Get solution
7.4 Show the result of running Shellsort on the input 9, 8, 7, 6, 5, 4, 3, 2, 1 using the increments {1, 3, 7}. - Get solution
7.5 a. What is the running time of Shellsort using the two-increment sequence {1, 2}?
b. Show that for any N, there exists a three-increment sequence such that Shellsort - Get solution
7.7 Prove that if a k-sorted file is then h-sorted, it remains k-sorted. - Sol. Not available
7.9 Determine the running time of Shellsort for
a. sorted input
b. reverse-ordered input - Get solution
7.10 Do either of the following modifications to the Shellsort routine coded in Figure 7.4
affect the worst-case running time?
a. Before line 11, subtract one from gap if it is even.
b. Before line 11, add one to gap if it is even. - Get solution
7.11 Show how heapsort processes the input 142, 543, 123, 65, 453, 879, 572, 434,
111, 242, 811, 102. - Get solution
7.13 Show that there are inputs that force every percolateDown in heapsort to go all the
way to a leaf. (Hint: Work backward.) - Get solution
7.14 Rewrite heapsort so that it sorts only items that are in the range low to high which
are passed as additional parameters.
Solution: If the root is stored in position low, then the left child of node i is stored at position 2i + 1 - low. This requires a small change to the heapsort code.
7.15 Sort 3, 1, 4, 1, 5, 9, 2, 6 using mergesort. - Get solution
7.16 How would you implement mergesort without using recursion? - Get solution
7.17 Determine the running time of mergesort for
a. sorted input
b. reverse-ordered input
c. random input - Get solution
7.18 Sol. Not available
7.19 Sort 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 using quicksort with median-of-three partitioning
and a cutoff of 3. - Get solution
7.20 Using the quicksort implementation in this chapter, determine the running time of
quicksort for
a. sorted input
b. reverse-ordered input
c. random input - Get solution
7.21 Repeat Exercise 7.20 when the pivot is chosen as
a. the first element
b. the larger of the first two distinct elements
c. a random element
d. the average of all elements in the set - Get solution
7.22 a. For the quicksort implementation in this chapter, what is the running time when
all keys are equal?
b. Suppose we change the partitioning strategy so that neither i nor j stops when
an element with the same key as the pivot is found. What fixes need to be made
in the code to guarantee that quicksort works, and what is the running time,
when all keys are equal?
c. Suppose we change the partitioning strategy so that i stops at an element with
the same key as the pivot, but j does not stop in a similar case. What fixes need
to be made in the code to guarantee that quicksort works, and when all keys are
equal, what is the running time of quicksort? - Get solution
7.23 Suppose we choose the element in the middle position of the array as the pivot.
Does this make it unlikely that quicksort will require quadratic time? - Get solution
7.24 Construct a permutation of 20 elements that is as bad as possible for quicksort using median-of-three partitioning and a cutoff of 3. - Get solution
7.26 Continuing from Exercise 7.25, after part (a),
a. Perform a test so that the smaller subarray is processed by the first recursive call,
while the larger subarray is processed by the second recursive call.
b. Remove the tail recursion by writing a while loop and altering left or right, as
necessary.
c. Prove that the number of recursive calls is logarithmic in the worst case. - Get solution
7.27 Suppose the recursive quicksort receives an int parameter, depth, from the driver
that is initially approximately 2 logN.
a. Modify the recursive quicksort to call heapsort on its current subarray if the level
of recursion has reached depth. (Hint: Decrement depth as you make recursive
calls; when it is 0, switch to heapsort.)
b. Prove that the worst-case running time of this algorithm is O(N logN).
c. Conduct experiments to determine how often heapsort gets called.
d. Implement this technique in conjunction with tail-recursion removal in Exercise 7.25.
e. Explain why the technique in Exercise 7.26 would no longer be needed. - Sol. 7.27 Not available
7.28 When implementing quicksort, if the array contains lots of duplicates, it may be better to perform a three-way partition (into elements less than, equal to, and greater than the pivot), to make smaller recursive calls. Assume three-way comparisons, as provided by the compareTo method.
a. Give an algorithm that performs a three-way in-place partition of an N-element subarray using only N − 1 three-way comparisons. If there are d items equal to the pivot, you may use d additional Comparable swaps, above and beyond the two-way partitioning algorithm. (Hint: As i and j move toward each other, maintain five groups of elements as shown below):
EQUAL SMALL UNKNOWN LARGE EQUAL
i j
b. Prove that using the algorithm above, sorting an N-element array that contains
only d different values, takes O(dN) time. - Get 7.28a Solution / Sol. 7.28. b. Not available
7.37 Consider the following algorithm for sorting six numbers:
Sort the first three numbers using Algorithm A.
Sort the second three numbers using Algorithm B.
Merge the two sorted groups using Algorithm C.
Show that this algorithm is suboptimal, regardless of the choices for Algorithms A,
B, and C. - Get solution
7.38 Write a program that reads N points in a plane and outputs any group of four
or more colinear points (i.e., points on the same line). The obvious brute-force
algorithm requires O(N4) time. However, there is a better algorithm that makes use
of sorting and runs in O(N2 logN) time. - Get solution
7.42 Give a linear-time algorithm to sort N fractions, each of whose numerators and denominators are integers between 1 and N. - Get solution
7.43 Suppose arrays A and B are both sorted and both contain N elements. Give an O(logN) algorithm to find the median of A ∪ B. - Get solution
7.44 Suppose you have an array of N elements containing only two distinct keys, true and false. Give an O(N) algorithm to rearrange the list so that all false elements precede the true elements. You may use only constant extra space. - Get solution
7.45 Suppose you have an array of N elements, containing three distinct keys, true, false, and maybe. Give an O(N) algorithm to rearrange the list so that all false elements precede maybe elements, which in turn precede true elements. You may use only constant extra space. - Get solution
7.46 a. Prove that any comparison-based algorithm to sort 4 elements requires 5 comparisons.
b. Give an algorithm to sort 4 elements in 5 comparisons. - Get solution
7.47 a. Prove that 7 comparisons are required to sort 5 elements using any comparison based
algorithm.
b. Give an algorithm to sort 5 elements with 7 comparisons. - Get solution
7.51 Suppose we implement the median of three routine as follows: Find the median of a[left], a[center], a[right], and swap it with a[right]. Proceed with the normal partitioning step starting i at left and j at right-1 (instead of left+1 and right-2).
a. Suppose the input is 2, 3, 4, . . . ,N −1,N, 1. For this input, what is the running time of this version of quicksort?
b. Suppose the input is in reverse order. For this input, what is the running time of this version of quicksort? - Get solution
7.52 Prove that any comparison-based sorting algorithm requires (N logN) comparisons on average. - Get solution
7.53 We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1, 6, and K is 10, then the answer is yes (4 and 6). A number may be used twice.
Do the following:
a. Give an O(N2) algorithm to solve this problem.
b. Give an O(N logN) algorithm to solve this problem. (Hint: Sort the items first.
After that is done, you can solve the problem in linear time.)
c. Code both solutions and compare the running times of your algorithms. - Get solution
7.55 Repeat Exercise 7.53 for three numbers. Try to design an O(N2) algorithm. - Get solution
