Problems

2-1 Insertion sort on small arrays in merge sort¶

Although merge sort runs in $\Theta(n \lg n)$ worst-case time and insertion sort runs in $\Theta(n^2)$ worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which $n/k$ sublists of length $k$ are sorted using insertion sort and then merged using the standard merging mechanism, where $k$ is a value to be determined.

• (a) Show that insertion sort can sort the $n/k$ sublists, each of length $k$, in $\Theta(nk)$ worst-case time.

• (b) Show how to merge the sublists in $\Theta(n \lg(n/k))$ worst-case time.

• (c) Given that the modified algorithm runs in $\Theta(nk + n\lg(n/k))$ worst-case time, what is the largest value of $k$ as a function of $n$ for which the modified algorithm has the same running time as standard merge sort, in terms of $\Theta$-notation?

• (d) How should you choose $k$ in practice?

2-2 Correctness of bubblesort¶

Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order. The procedure Bubblesort sorts array $A[1:n]$.

1
2
3
4
5
BUBBLESORT(A, n)
  for i = 1 to n - 1
    for j = n downto i + 1
      if A[j] < A[j-1]
        exchange A[j] with A[j-1]

• (a) Let $A'$ denote the array $A$ after Bubblesort$(A,n)$ is executed. To prove that Bubblesort is correct, you need to prove that it terminates and that

  $$A'[1] \leq A'[2] \leq \cdots \leq A'[n].$$

  (1)

  In order to show that BUBBLESORT actually sorts, what else do you need to prove?

The next two parts prove inequality (1).

• (b) State precisely a loop invariant for the for loop in lines 2-4, and prove that this loop invariant holds. Your proof should use the structure of the loop-invariant proof presented in this chapter.

• (c) Using the termination condition of the loop invariant proved in part (b), state a loop invariant for the for loop in lines 1-4 that allows you to prove inequality (1). Your proof should use the structure of the loop-invariant proof presented in this chapter.

• d. What is the worst-case running time of Bubblesort? How does it compare with the running time of Insertion-Sort?

2-3 Correctness of Horner’s rule¶

You are given the coefficents $a_0, a_1, a_2, \ldots, a_n$ of a polynomial

and you want to evaluate this polynomial for a given value of $x$. Horner’s rule says to evaluate the polynomial according to this parenthesization:

The procedure Horner implements Horner’s rule to evaluate $P(x)$, given the coefficients

1
2
3
4
5
HORNER(A,n,x)
  p = 0
  for i = n downto 0
    p = A[i] + x * p
  return p

• (a) In terms of $\Theta$-notation, what is the running time of this procedure?

• (b) Write pseudocode to implement the naive polynomial-evaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare with Horner?

• (c) Consider the following loop invariant for the procedure Horner:

  At the start of each iteration of the for loop of lines 2-3,

  $$p = \sum_{k = 0}^{n-(i+1)}A[k+i+1] \cdot x^k.$$

  Interpret a summation with no terms as equaling 0. Following the structure of the loop-invariant proof presented in this chapter, use this loop invariant to show that, at termination, $p = \sum_{k=0}^{n}A[k] \cdot x^k$.

2-4 Inversions¶

Let $A[1:n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] > A[j]$, then the pair $(i, j)$ is called an inversion of $A$.

• (a) List the five inversions of the array $\langle 2, 3, 8, 6, 1\rangle$.

• (b) What array with elements from the set $\{1, 2, \ldots, n\}$ has the most inversions? How many does it have?

• (c) What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

• (d) Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $\Theta(n \lg n)$ worst-case time. (Hint: Modify merge sort.)