The following divide-and-conquer algorithm is proposed for finding the

Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5 using insertion sort

What is the running time of insertion sort if all elements are equal?

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.

Show the result of running Shellsort on the input 9, 8, 7, 6, 5, 4, 3, 2, 1 using the increments {1, 3, 7}

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 runs in O(N5/3) time. c. Show that for any N, there exists a six-increment sequence such that Shellsort runs in O(N3/2) time.

a. Prove that the running time of Shellsort is (N2) using increments of the form 1, c,c2, ... ,ci for any integer c. b. Prove that for these increments, the average running time is (N3/2)

Prove that if a k-sorted file is then h-sorted, it remains k-sorted.

Prove that the running time of Shellsort, using the increment sequence suggested by Hibbard, is (N3/2) in the worst case. Hint: You can prove the bound by considering the special case of what Shellsort does when all elements are either 0 or 1. Set a[i] = 1 if i is expressible as a linear combination of ht, ht1, ... , h t/2+1 and 0 otherwise.

Determine the running time of Shellsort for a. sorted input b. reverse-ordered input

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.

Show how heapsort processes the input 142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102.

What is the running time of heapsort for presorted input?

Show that there are inputs that force every percolateDown in heapsort to go all the way to a leaf. (Hint: Work backward.)

4 Rewrite heapsort so that it sorts only items that are in the range low to high which are passed as additional parameters.

Sort 3, 1, 4, 1, 5, 9, 2, 6 using mergesort

How would you implement mergesort without using recursion?

7 Determine the running time of mergesort for a. sorted input b. reverse-ordered input c. random input

In the analysis of mergesort, constants have been disregarded. Prove that the number of comparisons used in the worst case by mergesort is NlogN 2logN + 1

Sort 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 using quicksort with median-of-three partitioning and a cutoff of 3.

Using the quicksort implementation in this chapter, determine the running time of quicksort for a. sorted input b. reverse-ordered input c. random input

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

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?

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?

Construct a permutation of 20 elements that is as bad as possible for quicksort using median-of-three partitioning and a cutoff of 3.

The quicksort in the text uses two recursive calls. Remove one of the calls as follows: a. Rewrite the code so that the second recursive call is unconditionally the last line in quicksort. Do this by reversing the if/else and returning after the call to insertionSort. b. Remove the tail recursion by writing a while loop and altering left.

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.

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.

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.

Write a program to implement the selection algorithm.

Solve the following recurrence: T(N) = (1/N) N 1 i=0 T(i)  + cN, T(0) = 0.

A sorting algorithm is stable if elements with equal keys are left in the same order as they occur in the input. Which of the sorting algorithms in this chapter are stable and which are not? Why?

Suppose you are given a sorted list of N elements followed by f(N) randomly ordered elements. How would you sort the entire list if a. f(N) = O(1)? b. f(N) = O(logN)? c. f(N) = O( N)? d. How large can f(N) be for the entire list still to be sortable in O(N) time?

Prove that any algorithm that finds an element X in a sorted list of N elements requires (logN) comparisons.

Using Stirlings formula, N! (N/e) N2N, give a precise estimate for log(N!).

a. In how many ways can two sorted arrays of N elements be merged? b. Give a nontrivial lower bound on the number of comparisons required to merge two sorted lists of N elements, by taking the logarithm of your answer in part (a).

Prove that merging two sorted arrays of N items requires at least 2N 1 comparisons. You must show that if two elements in the merged list are consecutive and from different lists, then they must be compared.

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.

Write a program that reads N points in a plane and outputs any group of four more colinear (i.e., points on the same line). The obvious brute-force algorithm requires 0(n4) time. However, there is a better algortihm that makes use of sorting and runs 0(nlogN)time.

Show that the two smallest elements among N can be found in N + logN 2 comparisons.

The following divide-and-conquer algorithm is proposed for finding the simultaneous maximum and minimum: If there is one item, it is the maximum and minimum, and if there are two items, then compare them and in one comparison you can find the maximum and minimum. Otherwise, split the input into two halves, divided as evenly as possibly (if N is odd, one of the two halves will have one more element than the other). Recursively find the maximum and minimum of each half, and then in two additional comparisons produce the maximum and minimum for the entire problem. a. Suppose N is a power of 2. What is the exact number of comparisons used by this algorithm? b. Suppose N is of the form 3 2k. What is the exact number of comparisons used by this algorithm? c. Modify the algorithm as follows: When N is even, but not divisible by four, split the input into sizes of N/2 1 and N/2 + 1. What is the exact number of comparisons used by this algorithm?

Suppose we want to partition N items into G equal-sized groups of size N/G, such that the smallest N/G items are in group 1, the next smallest N/G items are in group 2, and so on. The groups themselves do not have to be sorted. For simplicity, you may assume that N and G are powers of two. a. Give an O(N logG) algorithm to solve this problem. b. Prove an (N log G) lower bound to solve this problem using comparison-based algorithms.

Give a linear-time algorithm to sort N fractions, each of whose numerators and denominators are integers between 1 and N.

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.

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.

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

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

a. Prove that 7 comparisons are required to sort 5 elements using any comparisonbased algorithm. b. Give an algorithm to sort 5 elements with 7 comparisons.

Write an efficient version of Shellsort and compare performance when the following increment sequences are used: a. Shells original sequence b. Hibbards increments c. Knuths increments: hi = 1 2 (3i + 1) d. Gonnets increments: ht = N 2.2 , and hk = hk+1 2.2  (with h1 = 1 if h2 = 2) e. Sedgewicks increments.

Implement an optimized version of quicksort and experiment with combinations of the following: a. Pivot: first element, middle element, random element, median of three, median of five. b. Cutoff values from 0 to 20.

Write a routine that reads in two alphabetized files and merges them together, forming a third, alphabetized, file.

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?

Prove that any comparison-based sorting algorithm requires (N logN) comparisons on average.

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.

Repeat Exercise 7.53 for four numbers. Try to design an O(N2 logN) algorithm. (Hint: Compute all possible sums of two elements. Sort these possible sums. Then proceed as in Exercise 7.53.)

Repeat Exercise 7.53 for three numbers. Try to design an O(N2) algorithm.

Consider the following strategy for percolateDown. We have a hole at node X. The normal routine is to compare Xs children and then move the child up to X if it is larger (in the case of a (max)heap) than the element we are trying to place, thereby pushing the hole down; we stop when it is safe to place the new element in the hole. The alternative strategy is to move elements up and the hole down as far as possible, without testing whether the new cell can be inserted. This would place he new cell in a leaf and probably violate the heap order; to fix the heap order, percolate the new cell up in the normal manner. Write a routine to include this idea, and compare the running time with a standard implementation of heapsort.

Propose an algorithm to sort a large file using only two tapes.

a. Show that a lower bound of N!/22N on the number of heaps is implied by the fact that buildHeap uses at most 2N comparisons. b. Use Stirlings formula to expand this bound.

M is an N-by-N matrix in which the entries in each rows are in increasing order and the entries in each column are in increasing order (reading top to bottom). Consider the problem of determining if x is in M using three-way comparisons (i.e., one comparison of x with M[i][j] tells you either that x is less than, equal to, or greater than M[i][j]). a. Give an algorithm that uses at most 2N 1 comparisons. b. Prove that any algorithm must use at least 2N 1 comparisons.

There is a prize hidden in a box; the value of the prize is a positive integer between 1 and N, and you are given N. To win the prize, you have to guess its value. Your goal is to do it in as few guesses as possible; however, among those guesses, you may only make at most g guesses that are too high. The value g will be specified at the start of the game, and if you make more than g guesses that are too high, you lose. So, for example, if g = 0, you then can win in N guesses by simply guessing the sequence 1, 2, 3, .... a. Suppose g = logN. What strategy minimizes the number of guesses? b. Suppose g = 1. Show that you can always win in O( N1/2 ) guesses. c. Suppose g = 1. Show that any algorithm that wins the prize must use  ( N1/2 ) guesses. d. Give an algorithm and matching lower bound for any constant g.