Introduction to Algorithms Exercises
Introduction to Algorithms Exercises
I will put the actual implementation of exercises here.
I Foundations
1 The Role of Algorithms in Computing
1.1 Algorithms
1.11
Give a realworld example that requires sorting or a realworld example that requires computing a convex hull.
Skipped.
1.12
Other than speed, what other measures of efficiency might one use in a realworld setting?
Memory consumption.
1.13
Select a data structure that you have seen previously, and discuss its strengths and limitations.
Linked lists, where insertion and deletion take constant time, but locating an element by index takes linear time.
1.14
How are the shortestpath and travelingsalesman problems given above similar? How are they different?
They both need to minimize the total distance for travelling. But shortestpath is to find the shortest path between only two locations, while travelingsalesman is to find the shortest path containing all given locations.
1.15
Come up with a realworld problem in which only the best solution will do. Then come up with one in which a solution that is βapproximatelyβ the best is good enough.
Skipped.
1.2 Algorithms as a technology
1.21
Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.
The Minesweeper game. You have to figure out if there is a mime under a button base on the numbers that you recovered. That is an algorithm.
1.22
Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in $8 n^2$ steps, while merge sort runs in 64 n lg n steps. For which values of n does insertion sort beat merge sort?
We can solve $8 n^2 < 64 n \lg n$ for n. Assume n β₯ 0, we get n < 8 lg n. With the help of Wolfram Alpha, we know that 1.1 < n < 43.5593. So for n β [2, 43], insertion sort beats merge sort.
1.23
What is the smallest value of n such that an algorithm whose running time is $100 n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?
Solve $100 n^2 < 2^n$ for n (using Wolfram Alpha), we get 0.096704 < n < 0.103658 or n > 14.3247, so the smallest value of n is 0.
Question: Should I only consider positive integer values for n?
1.X Problems
11 Comparison of running times
For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.
1 second 1 minute 1 hour 1 day 1 month 1 year 1 century $\lg n$ $\sqrt{n}$ n $n \lg n$ $n^2$ $n^3$ $2^n$ $n!$
 1 second = $10^6$ microseconds
 1 minute = 6 Γ $10^7$ microseconds
 1 hour = 3.6 Γ $10^9$ microseconds
 1 day = 8.64 Γ $10^{10}$ microseconds
 1 month = 2.628 Γ $10^{12}$ microseconds
 1 year = 3.154 Γ $10^{13}$ microseconds
 1 century = 3.156 Γ $10^{15}$ microseconds
1 second  1 minute  1 hour  1 day  1 month  1 year  1 century  

$\lg n$  $10^{301029.9957}$  $10^{18061799.7398}$  $10^{1083707984.3903}$  $10^{26008991625.368}$  $10^{791106828604.9426}$  $10^{9494486063241.967}$  $10^{950050666315524.8}$ 
$\sqrt{n}$  $10^{12}$  $10^{15.5563}$  $10^{19.1126}$  $10^{21.873}$  $10^{24.8393}$  $10^{26.9977}$  $10^{30.9983}$ 
$n$  $10^{6}$  $10^{7.7782}$  $10^{9.5563}$  $10^{10.9365}$  $10^{12.4196}$  $10^{13.4989}$  $10^{15.4991}$ 
$n \lg n$  $10^{4.7976}$  $10^{6.4474}$  $10^{8.1251}$  $10^{9.4401}$  $10^{10.8623}$  $10^{11.9019}$  $10^{13.8367}$ 
$n^2$  $10^{3}$  $10^{3.8891}$  $10^{4.7782}$  $10^{5.4683}$  $10^{6.2098}$  $10^{6.7494}$  $10^{7.7496}$ 
$n^3$  $10^{2}$  $10^{2.5927}$  $10^{3.1854}$  $10^{3.6455}$  $10^{4.1399}$  $10^{4.4996}$  $10^{5.1664}$ 
$2^n$  $10^{1.2995}$  $10^{1.4123}$  $10^{1.5017}$  $10^{1.5603}$  $10^{1.6155}$  $10^{1.6517}$  $10^{1.7117}$ 
$n!$  $10^{0.9636}$  $10^{1.0432}$  $10^{1.0984}$  $10^{1.1458}$  $10^{1.178}$  $10^{1.205}$  $10^{1.2421}$ 
The table is generated using following JavaScript code:
function generateTable() {
function binarySearch(f, target) {
const start = 0.000001;
const epsilon = 0.0000000001;
let left = start;
let right = start;
while (f(right) < target) {
right *= 2;
}
while (right  left > epsilon) {
const middle = left + (right  left) / 2;
const value = f(middle);
if (value < target) {
left = middle;
} else if (value > target) {
right = middle;
} else {
return middle;
}
}
return left + (right  left) / 2;
}
function normalize(x) {
return Math.round(x * 10000) / 10000;
}
const algorithms = [
{
label: "$\\lg n$",
func: (t) => Math.log10(2) * t
},
{
label: "$\\sqrt{n}$",
func: (t) => Math.log10(t) * 2
},
{
label: "$n$",
func: (t) => Math.log10(t)
},
{
label: "$n \\lg n$",
func: (t) => binarySearch(n => n * Math.pow(10, n) * Math.log2(10), t)
},
{
label: "$n^2$",
func: (t) => Math.log10(t) / 2
},
{
label: "$n^3$",
func: (t) => Math.log10(t) / 3
},
{
label: "$2^n$",
func: (t) => Math.log10(Math.log2(t))
},
{
label: "$n!$",
func: function (t) {
// TODO: use the Ξ function (use Stirling's approximation?).
function fact(n) {
let result = 1;
let i = 2;
for (; i <= n; i++) {
result *= i;
}
if (i > n) {
result += result * (i  1) * (n + 1  i);
}
return result;
}
return binarySearch((x) => fact(Math.pow(10, x)), t);
}
}
];
const times = [
{
label: "1 second",
microseconds: 1e6
},
{
label: "1 minute",
microseconds: 6e7
},
{
label: "1 hour",
microseconds: 3.6e9
},
{
label: "1 day",
microseconds: 8.64e10
},
{
label: "1 month",
microseconds: 2.628e12
},
{
label: "1 year",
microseconds: 3.154e13
},
{
label: "1 century",
microseconds: 3.156e15
}
];
let result = `  ${times.map((x) => x.label).join("  ")} \n` +
`   ${times.map((x) => "").join("  ")} \n`;
for (const algorithm of algorithms) {
result += ` ${algorithm.label} `;
for (const time of times) {
result += ` $10^{${normalize(algorithm.func(time.microseconds))}}$ `;
}
result += "\n";
}
return result;
}
2 Getting Started
2.1 Insertion sort
2.11
Using Figure 2.2 as a model, illustrate the operation of InsertionSort on the array A = β¨31, 41, 59, 26, 41, 58β©.
Skipped.
2.12
Rewrite the InsertionSort procedure to sort into nonincreasing instead of nondecreasing order.
Just change A[i] > key to A[i] < key in the original code.
2.13
Consider the searching problem:
Input: A sequence of n numbers $A = β¨a_1, a_2, β¦, a_nβ©$ and a value v.
Output: An index i such that $v = A[i]$ or the special value nil if v does not appear in A.
Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
LinearSearch(A, v)
 for i = 1 to A.length
 Β Β Β Β if A[i] == v
 Β Β Β Β Β Β Β Β return i
 return nil
Loop invariant: A[1β₯i  1] does not contain value v. The only way the loop continues is that A[i] β v, so we know A[1β₯i] does not contain value v. Then we increase i by 1, so again, A[1β₯i  1] still does not contain value v. If the loop is completed, i must be equal to A.length + 1, so the whole array does not contain value v, then we return nil.
If for some i, A[i] == v, we will find it in line 2 and return i in line 3. The only way to escape the loop is either for some i, A[i] == v, or none of the elements equals to v. we can guarantee that if there is an element in A, we will find it.
2.14
Consider the problem of adding two nbit binary integers, stored in two nelement arrays A and B. The sum of the two integers should be stored in binary form in an (n + 1)element array C. State the problem formally and write pseudocode for adding the two integers.
Problem: Array A and B only contain elements of 0 and 1, and A.length == B.length == n. Array C that have length n + 1. Rewrite the elements in C so that C only contains 0s and 1s, and $β_{i=1}^n A[i] Γ 2^{n  i} + β_{i=1}^n B[i] Γ 2^{n  i} = β_{i=1}^{n + 1} C[i] Γ 2^{n + 1  i}$.
Pseudocode:
AddBinary(A, B, C)
 carry = 0
 for i = 1 to A.length
 Β Β Β Β sum = A[n  i] + B[n  i] + carry
 Β Β Β Β C[n + 1  i] = sum mod 2
 Β Β Β Β carry = sum / 2
 C[0] = carry
2.2 Analyzing algorithms
2.21
Express the function $n^3/1000  100 n^2  100 n + 3$ in terms of Ξnotation.
$Ξ\left(n^3\right)$.
2.22
Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n  1 elements of A. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n  1 elements, rather than for all n elements? Give the bestcase and worstcase running times of selection sort in Ξnotation.
Solution is implemented here.
The loop invariant: at the start of each iteration of loop, The first i elements contains the smallest i elements in A, and they are in nondecreasing order.
It only need to run for first n  1 elements because after the loop, we have rearrange the smallest n  1 elements, to the front of A, so the last element must be the biggest one, so the whole array is ordered.
Bestcase and worstcase running times are both $Ξ\left(n^2\right)$.
2.23
Consider linear search again (see Exercise 2.13). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the averagecase and worstcase running times of linear search in Ξnotation? Justify your answers.
Assume the element to be searched is in the array, then the average elements to be checked is (n + 1) / 2.
Best case running time is Ξ(1), worst case running time is Ξ(n). If we are lucky, we can find the element at the first position, where only one element need to be checked. If we are unlucky, we can find the element at the last position, where all elements will be checked.
2.24
How can we modify almost any algorithm to have a good bestcase running time?
Precompute the result for some special cases, and test the inputs for such cases. If the input matches such cases we return the precomputed result.
2.3 Designing algorithms
2.31
Using Figure 2.4 as a model, illustrate the operation of merge sort on the array A = β¨3, 41, 52, 26, 38, 57, 9, 49β©.
Skipped.
2.32
Rewrite the Merge procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.
See here for implementation.
2.33
Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence
$T\left(n\right) = \begin{cases} 2 &\text{if } n = 2 \\ 2 T\left(n / 2\right) + n &\text{if } n = 2^k, \text{ for } k > 1 \end{cases}$
is $T\left(n\right) = n \lg n$.
 Base case: If $n = 2$, $T\left(n\right) = 2$. Since $n \lg n = 2 \lg 2 = 2$, $T\left(n\right) = n \lg n$, so the claim holds.
 Inductive case: If $n > 2$, $T\left(n\right) = 2 T\left(n / 2\right) + n$, by induction, we know that $T\left(n / 2\right) = \left(n / 2\right) \lg \left(n / 2\right)$, so $T\left(n\right) = 2 \left(n / 2\right) \lg \left(n / 2\right) + n = n \lg \left(n / 2\right) + n = n \left(\lg n  1\right) + n = n \lg n$, The claim holds.
2.34
We can express insertion sort as a recursive procedure as follows. In order to sort A[1β₯n], we recursively sort A[1β₯n  1] and then insert A[n] into the sorted array A[1β₯n  1]. Write a recurrence for the worstcase running time of this recursive version of insertion sort.
See here for implementation.
$$T\left(n\right) = \begin{cases} 1 &\text{if $n < 2$} \\ T(n  1) + Ξ\left(n\right) &\text{if $n >= 2$} \end{cases}$$
2.35
Referring back to the searching problem (see Exercise 2.13), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worstcase running time of binary search is Ξ(lg n).
See here for implementation.
BinarySearch(A, v)
 left = 1
 right = A.length + 1
 while left < right
 Β Β Β Β middle = β(left + right) / 2β
 Β Β Β Β if A[middle] < v
 Β Β Β Β Β Β Β Β left = middle + 1
 Β Β Β Β else
 Β Β Β Β Β Β Β Β right = middle
 if left β€ A.length and A[left] == v
 Β Β Β Β return left
 else
 Β Β Β Β return nil
After each iteration, the length of the searching range reduces by half, until the range is empty. So we have:
T(n) = $c_1$, if n = 0;
T(n) = T(n / 2) + $c_2$, if n > 0.
We prove T(n) = Ξ(lg n) by induction:
 If n = 0, Ξ(lg n) = Ξ(lg 0) = Ξ(β), β¦ Not sure how to go from here.
 If n > 0, Ξ(lg n) = T(n / 2) + $c_2$ = Ξ(T(n / 2)). By induction, we know T(n / 2) = Ξ(lg (n / 2)), so Ξ(lg n) = Ξ(lg (n / 2)) = Ξ((lg n)  1) = Ξ(lg n).
2.36
Observe that the while loop of lines 5β7 of the InsertionSort procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[1β₯j  1]. Can we use a binary search (see Exercise 2.35) instead to improve the overall worstcase running time of insertion sort to Ξ(n lg n)?
No, we can not. Because despite the searching takes Ξ(lg n) time, we still need to move n elements in the worstcase scenario, which takes Ξ(n) time.
2.37 β
Describe a Ξ(n lg n)time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
See here for implementations.
2.X Problems
21 Insertion sort on small arrays in merge sort
Although merge sort runs in $Ξ\left(n \lg n\right)$ worstcase time and insertion sort runs in $Ξ\left(n^2\right)$ worstcase 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.
 Show that insertion sort can sort the $n / k$ sublists, each of length k, in $Ξ\left(n k\right)$ worstcase time.
 Show how to merge the sublists in $Ξ\left(n \lg \left(n / k\right)\right)$ worstcase time.
 Given that the modified algorithm runs in $Ξ\left(n k + n \lg \left(n / k\right)\right)$ worstcase 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 $Ξ$notation?
 How should we choose k in practice?
 Sort a sublist of length k takes $k^2$ time, so sorting $n / k$ sublists takes $\left(n / k\right) Ξ\left(k^2\right) = Ξ\left(\left(n / k\right) k^2\right) = Ξ\left(n k\right)$ time.
 Assume merging n sublists takes $T(n)$ time, we have $T\left(n\right) = 2 T\left(n\right) + c_1 n$, if $n > 1$. Also, $T\left(n\right) = c_2$, if $n = 1$. Notice this is the same as equation 2.1 and 2.2. So we have $T\left(n\right) = Ξ\left(n \lg n\right)$. So merging $n / k$ sublists takes $T\left(n / k\right) = Ξ\left(\left(n / k\right) \lg \left(n / k\right)\right) = Ξ\left(n \lg \left(n / k\right)\right)$.
 We need to solve the equation $n k + n \lg \left(n / k\right) < c n \lg \left(n\right)$. We can get $k  \lg k < \left(c1\right) \lg n$ from it. I think $k < Ξ\left(\lg n\right)$, but I canβt prove it.
 With benchmarks and profiling.
22 Correctness of bubblesort
Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order.
Bubblesort(A)
 for i = 1 to A.length  1
 Β Β Β Β for j = A.length downto i + 1
 Β Β Β Β Β Β Β Β if A[j] < A[j  1]
 Β Β Β Β Β Β Β Β Β Β Β Β exchange A[j] with A[j  1]
Let Aβ² denote the output of Bubblesort(A). To prove that Bubblesort is correct, we need to prove that it terminates and that
Aβ²[1] β€ Aβ²[2] β€ β¦ β€ Aβ²[n], (2.3)
where n = A.length. In order to show that Bubblesort actually sorts, what else do we need to prove?
The next two parts will prove inequality (2.3).
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.
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 will allow you to prove inequality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter.
What is the worstcase running time of bubblesort? How does it compare to the running time of insertion sort?

We also need to prove that the elements in A is the same as in Aβ².

The loop invariant: At the start of each iteration, A[j] is the smallest element in A[jβ₯A.length].
Proof:
 Initialization: Before the first iteration, j = A.length, So A[j] is the only element in A[jβ₯A.length], the claim holds.
 Maintenance:
 If A[j] < A[j  1], because we know that A[j] is the smallest element in A[jβ₯A.length], we can be sure A[j] is the smallest element in A[j  1β₯A.length], after swapping A[j] and A[j  1], A[j  1] became the smallest element in A[j  1β₯A.length]. After decreasing j, the loop invariant holds.
 If A[j] β₯ A[j  1], we know that A[j  1] is the smallest element in A[j  1β₯A.length]. After decreasing j, the loop invariant holds.
 Termination: After termination, j = i, so we know that A[i] is the smallest element in A[iβ₯A.length].

The loop invariant: At the start of the loop, A[1β₯i  1] is empty or contains the smallest i elements and are sorted.
Proof:
 Initialization: Before the first iteration, i = 1, So A[1β₯i  1] is empty, the claim holds.
 Maintenance: After the inner loop, we know that A[i] is the smallest element in A[iβ₯A.length].
 If A[1β₯i  1] is empty, i = 1, then A[1β₯i] contains only one element and it is the smallest one in A[iβ₯A.length], so A[1β₯i] is sorted and contains the smallest i element in A[1β₯A.length]. After increasing i, the loop invariant holds.
 If A[1β₯i  1] is not empty, then A[1β₯i  1] contains the smallest i  1 element in A[1β₯A.length] in sorted order, so A[i  1] β€ A[i]. Because A[i] is the smallest element in A[iβ₯A.length], we know that A[1β₯i] is sorted and contains the smallest i element in A[1β₯A.length]. After increasing i, the loop invariant holds.
 Termination: After termination, i = A.length, and A[1β₯A.length  1] contains the smallest A.length  1 elements in sorted order, so we know A[A.length  1] β€ A[A.length], so the whole array is sorted.

Worstcase running time is $Ξ\left(n^2\right)$, it is the same as insertion sort. But insertion sort have a bestcase running time which is $Ξ\left(n\right)$, while the bestcase running time of bubble sort is still $Ξ\left(n^2\right)$.
23 Correctness of Hornerβs rule
The following code fragment implements Hornerβs rule for evaluating a polynomial
$\begin{aligned} P\left(x\right) &= β_{k=0}^n a_k x^k \\ &=a_0 + x\left(a_1 + x\left(a_2 + β¦ + x\left(a_{n  1} + x a_n\right) β¦\right)\right), \end{aligned}$
given the coefficients $a_0$, $a_1$, β¦, $a_n$ and a value for x:
 y = 0
 for i = n downto 0
 Β Β Β Β y = $a_i$ + x β y
In terms of Ξnotation, what is the running time of this code fragment for Hornerβs rule?
Write pseudocode to implement the naive polynomialevaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare to Hornerβs rule?
Consider the following loop invariant:
At the start of each iteration of the for loop of lines 2β3,
$y = \displaystyle β_{k = 0}^{n  \left(i + 1\right)} a_{k + i + 1} 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, $y = β_{k = 0}^n a_k x^k$.
Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients $a_0$, $a_1$, β¦, $a_n$.
See here for implementation.

Ξ(n).

The pseudocode:
 y = 0
 for i = 0 to n
 Β Β Β Β p = $a_i$
 Β Β Β Β for j = 0 to i
 Β Β Β Β Β Β Β Β p = p β x
 Β Β Β Β y = y + p
The running time of this algorithm is $Ξ\left(n^2\right)$. It takes more time than Hornerβs rule.

Proof:
 Initialization: Before the first iteration, i = n, $y = β_{k = 0}^{n  \left(i + 1\right)} a_{k + i + 1} x^k = β_{k = 0}^{1} a_{k + n + 1} x^k = 0$, so the claim holds.
 Maintenance: After line 3, $y' = a_i + x β y = a_i + x \left(β_{k = 0}^{n  \left(i + 1\right)} a_{k + i + 1} x^k\right) = a_i β x^0 + β_{k = 0}^{n  \left(i + 1\right)} a_{k + i + 1} x^{k + 1} = a_i β x^0 + β_{k = 1}^{n  i} a_{k + i} x^k = β_{k = 0}^{n  i} a_{k + i} x^k$. After decreasing i, the claim holds.
 Termination: At termination, i = 1, so $y = β_{k = 0}^{n  \left(\left(1\right) + 1\right)} a_{k + \left(1\right) + 1} x^k = β_{k = 0}^n a_k x^k$.

I thought I have proved it at step 3.
24 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.
 List the five inversions of the array β¨2, 3, 8, 6, 1β©.
 What array with elements from the set {1, 2, β¦, n} has the most inversions? How many does it have?
 What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
 Give an algorithm that determines the number of inversions in any permutation on n elements in Ξ(n lg n) worstcase time. (Hint: Modify merge sort.)

The five inversions are (1, 5), (2, 5), (3, 4), (3, 5) and (4, 5).

The array β¨n, β¦, 2, 1β© has the most inversions. It has n Γ (n  1) / 2 inversions.

Let k be the inversion of an array, the the running time of insertion sort on it is Ξ(k).
Let $k_i$ be the numbers of inversions whose second element is i. The total sorting time is $β_{i = 1}^n\left(c_1 k_i + c_2\right) = c_1 k + c_2 n = Ξ\left(k\right)$.

See here for implementation.
3 Growth of Functions
3.1 Asymptotic notation
Notation  Definition 

f(n) = O(g(n))  β c > 0, $n_0$ > 0: β n β₯ $n_0$: 0 β€ f(n) β€ c g(n) 
f(n) = Ξ©(g(n))  β c > 0, $n_0$ > 0: β n β₯ $n_0$: 0 β€ c g(n) β€ f(n) 
f(n) = Ξ(g(n))  β $c_1$ > 0, $c_2$ > 0, $n_0$ > 0: β n β₯ $n_0$: 0 β€ $c_1$ g(n) β€ f(n) β€ $c_2$ g(n) 
f(n) = o(g(n))  β c > 0: β $n_0$ > 0: β n β₯ $n_0$: 0 β€ f(n) < c g(n) 
f(n) = Ο(g(n))  β c > 0: β $n_0$ > 0: β n β₯ $n_0$: 0 β€ c g(n) < f(n) 
3.11
Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic definition of Ξnotation, prove that max(f(n), g(n)) = Ξ(f(n) + g(n)).
In the following statements, n is big enough that both f(n) and g(n) is nonnegative.
Because f(n) β€ max(f(n), g(n)), and g(n) β€ max(f(n), g(n)), we know that f(n) + g(n) β€ 2 max(f(n), g(n)). So 0.5 (f(n) + g(n)) β€ max(f(n), g(n)).
Because f(n) β€ f(n) + g(n), and g(n) β€ f(n) + g(n), we know that max(f(n), g(n)) β€ f(n) + g(n).
So we have 0.5 (f(n) + g(n)) β€ max(f(n), g(n)) β€ f(n) + g(n), max(f(n), g(n)) = Ξ(f(n) + g(n)).
3.12
Show that for any real constants a and b, where b > 0,
$\left(n + a\right)^b = Ξ\left(n^b\right)$. (3.2)
We want to find constant $c_1$, $c_2$ and $n_0$ so that if $n > n_0$, $c_1 n^b β€ \left(n + a\right)^b β€ c_2 n^b$.
$c_1 n^b β€ \left(n + a\right)^b β€ c_2 n^b$
β $\left({c_1}^{1 / b}\right)^b n^b β€ \left(n + a\right)^b β€ \left({c_2}^{1 / b}\right)^b n^b$
β $\left({c_1}^{1 / b} n\right)^b β€ \left(n + a\right)^b β€ \left({c_2}^{1 / b} n\right)^b$
β ${c_1}^{1 / b} n β€ n + a β€ {c_2}^{1 / b} n$
β ${c_1}^{1 / b} n  n β€ a β€ {c_2}^{1 / b} n  n$
β $\left({c_1}^{1 / b}  1\right) n β€ a β€ \left({c_2}^{1 / b}  1\right) n$
We need n to be greater than some $n_0$, so we should have ${c_1}^{1 / b}  1 < 0$, and ${c_2}^{1 / b}  1 > 0$, then we have $n β₯ \frac{a}{ {c_1}^{1 / b}  1}$, and $n β₯ \frac{a}{ {c_1}^{1 / b}  1}$, i.e. $n β₯ \max\left(\frac{a}{ {c_1}^{1 / b}  1}, \frac{a}{ {c_2}^{1 / b}  1}\right)$. Let $c_1 = \left(\frac{1}{2}\right)^b$, $c_2 = 2^b$, we have $n β₯ \max\left(2 a, a\right)$. So $n_0$ can be $\max\left(2 a, a\right)$.
Formally, for any $n > \max\left(2 a, a\right)$, $\left(\frac{1}{2}\right)^b n^b β€ \left(n + a\right)^b β€ 2^b n^b$, $\left(n + a\right)^b = Ξ(n^b)$.
3.13
Explain why the statement, βThe running time of algorithm A is at least $O\left(n^2\right)$,β is meaningless.
It is like saying x is at least less than or equal to 10.
3.14
Is $2^{n + 1} = O\left(2 ^ n\right)$? Is $2^{2 n} = O\left(2^n\right)$?
$2^{n + 1} = 2 Γ 2^n = O\left(2 ^ n\right)$, $2^{2 n} = \left(2^n\right)^2 β O\left(2^n\right)$.
3.15
Prove Theorem 3.1.
If f(n) = Ξ(g(n)), c1 g(n) β€ f(n) β€ c2 g(n), for all n β₯ n0, for some c1, c2 and n0. Because f(n) β€ c2 g(n), we know that f(n) = O(g(n)). Because c1 g(n) β€ f(n), we know that f(n) = Ξ©(g(n)).
If f(n) = O(g(n)) then f(n) β€ c2 g(n), for all n β₯ n0, for some c2 and n0. If f(n) = Ξ©(g(n)), then c1 g(n) β€ f(n), for all n β₯ n1, for some c1 and n1. So c1 g(n) β€ f(n) β€ c2 g(n), for all n β₯ max(n0, n1).
3.16
Prove that the running time of an algorithm is Ξ(g(n)) if and only if its worstcase running time is O(g(n)) and its bestcase running time is Ξ©(g(n)).
Running time of an algorithm is Ξ(g(n)) means the running time is bounded by a function f(n) that c1 g(n) β€ f(n) β€ c2 g(n), for all n β₯ n0, for some c1, c2 and n0 > 0. So the worstcase running time is bounded by c2 g(n), and the bestcase running time is bounded by c1 g(n). So the worstcase running time is O(g(n)), and the bestcase running time is Ξ©(g(n)).
If the worstcase running time is O(g(n)), it means the running time is bounded by a function f1(n) from above that f1(n) β€ c2 g(n) for sufficiently large n for some c2. If the bestcase running time is Ξ©(g(n)), it means the running time is bounded from below by a function f2(n) that c1 f(n) β€ f2(n) for sufficiently large n for some c1. Because f1(n) and f2(n) is the worstcast running time and the bestcase running time, the running time is bounded by c1 g(n) c2 g(n), so the running time is Ξ(g(n)).
3.17
Prove that o(g(n)) β© Ο(g(n)) is the empty set.
Assume there exist a function f(n) that f(n) = o(g(n)) and f(n) = Ο(g(n)), we have:
 For all c1 > 0, for some n0 > 0, for all n β₯ n0, c1 f(n) < g(n).
 For all c2 > 0, for some n1 > 0, for all n β₯ n1, c2 f(n) > g(n).
Let c2 = c1, n = max(n0, n1), we have c1 f(n) < g(n) and c1 f(n) > g(n) which is impossible, so f(n) does not exist. So o(g(n)) β© Ο(g(n)) is the empty set.
3.18
We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n, m), we denote by O(g(n, m)) the set of functions
O(g(n, m)) = { f(n, m) : there exist positive constants c, $n_0$, and $m_0$ such that 0 β€ f(n, m) β€ c g(n, m) for all n β₯ $n_0$ or m β₯ $m_0$ }.
Give corresponding definitions for Ξ©(g(n, m)) and Ξ(g(n, m)).
Ξ©(g(n, m)) = { f(n, m) : there exist positive constants c, $n_0$, and $m_0$ such that 0 β€ c g(n, m) β€ f(n, m) for all n β₯ $n_0$ or m β₯ $m_0$ }.
Ξ(g(n, m)) = { f(n, m) : there exist positive constants $c_1$, $c_2$, $n_0$, and $m_0$ such that 0 β€ $c_1$ g(n, m) β€ f(n, m) β€ $c_2$ g(n, m) for all n β₯ $n_0$ or m β₯ $m_0$ }.
3.2 Standard notations and common functions
3.21
Show that if f(n) and g(n) are monotonically increasing functions, then so are the functions f(n) + g(n) and f(g(n)), and if f(n) and g(n) are in addition nonnegative, then f(n) β g(n) is monotonically increasing.
 m β€ n β (f(m) β€ f(n)) β§ (g(m) β€ g(n)) β f(m) + g(m) β€ f(n) + g(n).
 m β€ n β g(m) β€ g(n) β f(g(m)) β€ f(g(n)).
 (m β€ n) β§ (β x: f(x) β₯ 0) β§ (β x: g(x) β₯ 0)
β (f(m) β€ f(n)) β§ (g(m) β€ g(n)) β§ (β x: f(x) β₯ 0) β§ (β x: g(x) β₯ 0)
β f(m) β g(m) β€ f(n) β g(m) β€ f(n) β g(n)
β f(m) β g(m) β€ f(n) β g(n).
3.22
Prove equation (3.16).
$a^{\log_b c} = \left(c^{\log_c a}\right)^{\log_b c} = c^{\left(\log_c a\right)\left(\log_b c\right)} = c^{\frac{\ln a}{\ln c} \frac{\ln c}{\ln b}} = c^{\frac{\ln a}{\ln b}} = c^{\log_b a}$.
3.23
Prove equation (3.19). Also prove that n! = Ο($2^n$) and n! = o($n^n$).
Proving equation (3.19):
According to equation (3.18), we know that
$\sqrt{2 Ο n} \left(\frac{n}{e}\right)^n \left(1 + \frac{c_1}{n}\right) β€ n! β€ \sqrt{2 Ο n} \left(\frac{n}{e}\right)^n \left(1 + \frac{c_2}{n}\right)$
So
$\ln \left(\sqrt{2 Ο n} \left(\frac{n}{e}\right)^n \left(1 + \frac{c_1}{n}\right)\right) β€ \ln \left(n!\right) β€ \ln \left(\sqrt{2 Ο n} \left(\frac{n}{e}\right)^n \left(1 + \frac{c_2}{n}\right)\right)$
β $\ln \left(\left(\frac{n}{e}\right)^n\right) + \ln \left(\sqrt{2 Ο n} \left(1 + \frac{c_1}{n}\right)\right) β€ \ln \left(n!\right) β€ \ln \left(\left(\frac{n}{e}\right)^n\right) + \ln \left(\sqrt{2 Ο n} \left(1 + \frac{c_2}{n}\right)\right)$
β $n \ln \left(\frac{n}{e}\right) + \ln \left(\sqrt{2 Ο n} \left(1 + \frac{c_1}{n}\right)\right) β€ \ln \left(n!\right) β€ n \ln \left(\frac{n}{e}\right) + \ln \left(\sqrt{2 Ο n} \left(1 + \frac{c_2}{n}\right)\right)$
β $n \left(\ln n  1\right) + \ln \left(\sqrt{2 Ο n} \left(1 + \frac{c_1}{n}\right)\right) β€ \ln \left(n!\right) β€ n \left(\ln n  1\right) + \ln \left(\sqrt{2 Ο n} \left(1 + \frac{c_2}{n}\right)\right)$
β $n \ln n  n + \ln \left(\sqrt{2 Ο n} \left(1 + \frac{c_1}{n}\right)\right) β€ \ln \left(n!\right) β€ n \ln n  n + \ln \left(\sqrt{2 Ο n} \left(1 + \frac{c_2}{n}\right)\right)$
β $n \ln n  n + \frac{1}{2} \ln {\left(2 Ο n\right)} + \ln {\left(1 + \frac{c_1}{n}\right)} β€ \ln \left(n!\right) β€ n \ln n  n + \frac{1}{2} \ln {\left(2 Ο n\right)} + \ln {\left(1 + \frac{c_2}{n}\right)}$.
So we have $\ln \left(n!\right) = Ξ©\left(n \ln n\right)$, and $\ln \left(n!\right) = O\left(n \ln n\right)$, so $\ln \left(n!\right) = Ξ\left(n \ln n\right)$.
Proving n! = Ο($2^n$):
$\lim_{n β β}\frac{2^n}{n!} = \lim_{n β β}\frac{2 Γ 2 Γ 2 Γ 2 Γ 2 Γ β¦ Γ 2}{1 Γ 2 Γ 3 Γ 4 Γ 5 Γ β¦ Γ n} = \lim_{n β β}\left(\frac{2}{1} Γ \frac{2}{2} Γ \frac{2}{3} Γ \frac{2}{4} Γ \frac{2}{5} Γ β¦ Γ \frac{2}{n}\right) = 2 \lim_{n β β}\left(\frac{2}{3} Γ \frac{2}{4} Γ \frac{2}{5} Γ β¦ Γ \frac{2}{n}\right) β€ 2 \lim_{n β β}\left(\frac{2}{n}\right) = 0$.
Proving n! = o($n^n$):
$\lim_{n β β}\frac{n!}{n^n} = \lim_{n β β}\frac{1 Γ 2 Γ 3 Γ 4 Γ 5 Γ β¦ Γ n}{n Γ n Γ n Γ n Γ n Γ β¦ Γ n} = \lim_{n β β}\left(\frac{1}{n} Γ \frac{2}{n} Γ \frac{3}{n} Γ \frac{4}{n} Γ \frac{5}{n} Γ β¦ Γ \frac{n}{n}\right) β€ \lim_{n β β}\left(\frac{1}{n}\right) = 0$.
3.24 β
Is the function βlg nβ! polynomially bounded? Is the function βlg lg nβ! polynomially bounded?
Skipped.
3.25 β
Which is asymptotically larger: $\lg \left(\lg^* n\right)$ or $\lg^* \left(\lg n\right)$?
By the definition of $\lg^*$, we have
$\lg^* n = \begin{cases}0&n β€ 1\\ \lg^* \left(\lg n\right) + 1&n > 1\end{cases}$.
So $\lg^* n = Ξ\left(\lg^* \left(\lg n\right)\right)$. Because $\lg^* n$ is asymptotically larger than $\lg \left(\lg^* n\right)$, we know that $\lg^* \left(\lg n\right)$ is asymptotically larger than $\lg \left(\lg^* n\right)$.
3.26
Show that the golden ratio $Ο$ and its conjugate $\hat{Ο}$ both satisfy the equation $x^2 = x + 1$.
$Ο^2 = \left(\frac{1 + \sqrt{5}}{2}\right)^2 = \frac{1 + 2 \sqrt{5} + 5}{4} = \frac{6 + 2 \sqrt{5}}{4} = \frac{3 + \sqrt{5}}{2} = \frac{1 + \sqrt{5}}{2} + 1 = Ο + 1$.
$\hat{Ο}^2 = \left(\frac{1  \sqrt{5}}{2}\right)^2 = \frac{1  2 \sqrt{5} + 5}{4} = \frac{6  2 \sqrt{5}}{4} = \frac{3  \sqrt{5}}{2} = \frac{1  \sqrt{5}}{2} + 1 = \hat{Ο} + 1$.
3.27
Prove by induction that the ith Fibonacci number satisfies the equality
$F_i = \dfrac{Ο^i  \hat{Ο}^i}{\sqrt{5}}$,
where $Ο$ is the golden ratio and $\hat{Ο}$ is its conjugate.
Base cases:
 If i = 0, $\frac{Ο^i  \hat{Ο}^i}{\sqrt{5}} = \frac{1  1}{\sqrt{5}} = 0$, the claim holds.
 If i = 1, $\frac{Ο^i  \hat{Ο}^i}{\sqrt{5}} = \frac{Ο  \hat{Ο}}{\sqrt{5}} = \frac{\frac{1 + \sqrt{5}}{2}  \frac{1  \sqrt{5}}{2}}{\sqrt{5}} = \frac{\sqrt{5}}{\sqrt{5}} = 1$, the claim holds.
Inductive case:
 By induction, we have $F_{i  2} = \frac{Ο^{i  2}  \hat{Ο}^{i  2}}{\sqrt{5}}$ and $F_{i  1} = \frac{Ο^{i  1}  \hat{Ο}^{i  1}}{\sqrt{5}}$. So $F_i = F_{i  2} + F_{i  1} = \frac{Ο^{i  2}  \hat{Ο}^{i  2}}{\sqrt{5}} + \frac{Ο^{i  1}  \hat{Ο}^{i  1}}{\sqrt{5}} = \frac{Ο^{i  2} \left(1 + Ο\right)  \hat{Ο}^{i  2} \left(1 + \hat{Ο}\right)}{\sqrt{5}}$. Base on the conclusion of exercise 3.26, we have $1 + Ο = Ο^2$ and $1 + \hat{Ο} = \hat{Ο}^2$, so $F_i = \frac{Ο^{i  2} Ο^2  \hat{Ο}^{i  2} \hat{Ο}^2}{\sqrt{5}} = \frac{Ο^i  \hat{Ο}^i}{\sqrt{5}}$, the claim holds.
3.28
Show that k ln k = Ξ(n) implies k = Ξ(n / ln n).
Skipped.
3.X Problems
31 Asymptotic behavior of polynomials
Let
$p(n) = \displaystyle β_{i=0}^d a_i n^i$,
where $a_d > 0$, be a degreed polynomial in n, and let k be a constant. Use the definitions of the asymptotic notations to prove the following properties.
 If k β₯ d, then p(n) = O($n^k$).
 If k β€ d, then p(n) = Ξ©($n^k$).
 If k = d, then p(n) = Ξ($n^k$).
 If k > d, then p(n) = o($n^k$).
 If k < d, then p(n) = Ο($n^k$).
Skipped.
32 Relative asymptotic growths
Indicate, for each pair of expressions (A, B) in the table below, whether A is O, o, Ξ©, Ο, or Ξ of B. Assume that k β₯ 1, Ο΅ > 0, and c > 1 are constants. Your answer should be in the form of the table with βyesβ or βnoβ written in each box.
A B O o Ξ© Ο Ξ a. $\lg^k n$ $n^Ο΅$ b. $n^k$ $c^n$ c. $\sqrt{n}$ $n^{\sin n}$ d. $2^n$ $2^{n / 2}$ e. $n^{\lg c}$ $c^{\lg n}$ f. $\lg\left(n!\right)$ $\lg\left(n^n\right)$
A  B  O  o  Ξ©  Ο  Ξ  

a.  $\lg^k n$  $n^Ο΅$  yes  yes  no  no  no 
b.  $n^k$  $c^n$  yes  yes  no  no  no 
c.  $\sqrt{n}$  $n^{\sin n}$  no  no  no  no  no 
d.  $2^n$  $2^{n / 2}$  no  no  yes  yes  no 
e.  $n^{\lg c}$  $c^{\lg n}$  yes  no  yes  no  yes 
f.  $\lg\left(n!\right)$  $\lg\left(n^n\right)$  yes  no  yes  no  yes 
33 Ordering by asymptotic growth rates
Rank the following functions by order of growth; that is, find an arrangement $g_1$, $g_2$, β¦, $g_{30}$ of the functions satisfying $g_1 = Ξ©\left(g_2\right)$, $g_2 = Ξ©\left(g_3\right)$, β¦, $g_{29} = Ξ©\left(g_{30}\right)$. Partition your list into equivalence classes such that functions f(n) and g(n) are in the same class if and only if $f\left(n\right) = Ξ\left(g\left(n\right)\right)$.
$\lg\left(\lg^* n\right)$ $2^{\lg^* n}$ $\left(\sqrt{2}\right)^{\lg n}$ $n^2$ $n!$ $\left(\lg n\right)!$ $\left(\frac{3}{2}\right)^n$ $n^3$ $\lg^2 n$ $\lg\left(n!\right)$ $2^{2^n}$ $n^{1 / \lg n}$ $\ln \ln n$ $\lg^* n$ $n β 2^n$ $n^{\lg \lg n}$ $\ln n$ $1$ $2^{\lg n}$ $\left(\lg n\right)^{\lg n}$ $e^n$ $4^{\lg n}$ $\left(n + 1\right)!$ $\sqrt{\lg n}$ $\lg^*\left(\lg n\right)$ $2^{\sqrt{2 \lg n}}$ n $2^n$ $n \lg n$ $2^{2^{n + 1}}$ Give an example of a single nonnegative function f(n) such that for all functions $g_i\left(n\right)$ in part (a), f(n) is neither $O\left(g_i\left(n\right)\right)$ nor $Ξ©\left(g_i\left(n\right)\right)$.
Skipped.
34 Asymptotic notation properties
Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.
 f(n) = O(g(n)) implies g(n) = O(f(n)).
 f(n) + g(n) = Ξ(min(f(n), g(n))).
 f(n) = O(g(n)) implies lg(f(n)) = O(lg(g(n))), where lg(g(n)) β₯ 1 and f(n) β₯ 1 for all sufficiently large n.
 f(n) = O(g(n)) implies $2^{f\left(n\right)} = O\left(2^{g\left(n\right)}\right)$.
 f(n) = O($\left(f\left(n\right)\right)^2$).
 f(n) = O(g(n)) implies g(n) = Ξ©(f(n)).
 f(n) = Ξ(f(n / 2)).
 f(n) + o(f(n)) = Ξ(f(n)).
Too lazy to prove. Just list my guessing here.
 False.
 False.
 Not sure.
 Not sure.
 Not sure.
 True.
 False.
 True.
35 Variations on O and Ξ©
Some authors define Ξ© in a slightly different way than we do; letβs use $\overset{β}{Ξ©}$ (read βomega infinityβ) for this alternative definition. We say that $f\left(n\right) = \overset{β}{Ξ©}\left(g\left(n\right)\right)$ if there exists a positive constant c such that $f\left(n\right) β₯ c g\left(n\right) β₯ 0$ for infinitely many integers n.
 Show that for any two functions f(n) and g(n) that are asymptotically nonnegative, either $f \left(n\right) = O\left(g\left(n\right)\right)$ or $f\left(n\right) = \overset{β}{Ξ©}\left(g\left(n\right)\right)$ or both, whereas this is not true if we use $Ξ©$ in place of $\overset{β}{Ξ©}$.
 Describe the potential advantages and disadvantages of using $\overset{β}{Ξ©}$ instead of $Ξ©$ to characterize the running times of programs.
Some authors also define O in a slightly different manner; letβs use $O'$ for the alternative definition. We say that $f\left(n\right) = O'\left(g\left(n\right)\right)$ if and only if $\leftf\left(n\right)\right = O\left(g\left(n\right)\right)$.
 What happens to each direction of the βif and only ifβ in Theorem 3.1 if we substitute $O'$ for O but still use $Ξ©$?
Some authors define $\widetilde{O}$ (read βsoftohβ) to mean O with logarithmic factors ignored:
$\widetilde{O}\left(g\left(n\right)\right)$ = { f(n) : there exist positive constants c, k, and $n_0$ such that $0 β€ f \left(n\right) β€ c g\left(n\right) \lg^k\left(n\right)$ for all $n β₯ n_0$ }.
 Define $\widetilde{Ξ©}$ and $\widetilde{Ξ}$ in a similar manner. Prove the corresponding analog to Theorem 3.1.
Skipped.
36 Iterated functions
We can apply the iteration operator $^\ast$ used in the $\lg^\ast$ function to any monotonically increasing function f(n) over the reals. For a given constant $c β β$, we define the iterated function $f_c^*$ by
$f_c^*\left(n\right) = \min \lbrace i β₯ 0 : f^{\left(i\right)}\left(n\right) β€ c \rbrace$,
which need not be well defined in all cases. In other words, the quantity $f_c^*\left(n\right)$ is the number of iterated applications of the function f required to reduce its argument down to c or less.
For each of the following functions f(n) and constants c, give as tight a bound as possible on $f_c^*\left(n\right)$.
f(n)  c  $f_c^*\left(n\right)$  

a.  n  1  0  βnβ 
b.  lg n  1  Donβt know 
c.  n / 2  1  βlg nβ 
d.  n / 2  2  βlg n  1β 
e.  $\sqrt{n}$  2  βlg lg nβ 
f.  $\sqrt{n}$  1  β 
g.  $n^{1 / 3}$  2  β$\log_3 \lg n$β 
h.  n / lg n  2  Donβt know 
4 DivideandConquer
4.1 The maximumsubarray problem
4.11
What does FindMaximumSubarray return when all elements of A are negative?
An array containing the single maximum element of the original array.
4.12
Write pseudocode for the bruteforce method of solving the maximumsubarray problem. Your procedure should run in Ξ($n^2$) time.
FindMaximumSubarrayBruteForce(A)
 maxleft = 0
 maxright = 0
 maxsum = β
 for i = 1 to A.Length
 Β Β Β Β sum = 0
 Β Β Β Β for j = i to A.Length
 Β Β Β Β Β Β Β Β sum = sum + A[j]
 Β Β Β Β Β Β Β Β if sum > maxsum
 Β Β Β Β Β Β Β Β Β Β Β Β maxleft = i
 Β Β Β Β Β Β Β Β Β Β Β Β maxright = j
 Β Β Β Β Β Β Β Β Β Β Β Β maxsum = sum
 return (maxleft, maxright, maxsum)
4.13
Implement both the bruteforce and recursive algorithms for the maximumsubarray problem on your own computer. What problem size $n_0$ gives the crossover point at which the recursive algorithm beats the bruteforce algorithm? Then, change the base case of the recursive algorithm to use the bruteforce algorithm whenever the problem size is less than $n_0$. Does that change the crossover point?
See here for recursive implementation.
See here for bruteforce implementation.
Skipped crossover point test for now.
4.14
Suppose we change the definition of the maximumsubarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?
Run the original algorithm first, if the maximum sum is negative, return an empty subarray.
4.15
Use the following ideas to develop a nonrecursive, lineartime algorithm for the maximumsubarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1β₯j], extend the answer to find a maximum subarray ending at index j + 1 by using the following observation: a maximum subarray of A[1β₯j + 1] is either a maximum subarray of A[1β₯j] or a subarray A[iβ₯j + 1], for some 1 β€ i β€ j + 1. Determine a maximum subarray of the form A[iβ₯j + 1] in constant time based on knowing a maximum subarray ending at index j.
See here for implementation.
4.2 Strassenβs algorithm for matrix multiplication
4.21
Use Strassenβs algorithm to compute the matrix product
$\begin{pmatrix}1 & 3\\7 & 5\end{pmatrix}\begin{pmatrix}6 & 8\\4 & 2\end{pmatrix}$.
Show your work.
Skipped.
4.22
Write pseudocode for Strassenβs algorithm.
Skipped.
4.23
How would you modify Strassenβs algorithm to multiply n Γ n matrices in which n is not an exact power of 2? Show that the resulting algorithm runs in time Ξ($n^{\lg 7}$).
Skipped.
4.24
What is the largest k such that if you can multiply 3 Γ 3 matrices using k multiplications (not assuming commutativity of multiplication), then you can multiply n Γ n matrices in time o($n^{\lg 7}$)? What would the running time of this algorithm be?
Skipped.
4.25
V. Pan has discovered a way of multiplying 68 Γ 68 matrices using 132,464 multiplications, a way of multiplying 70 Γ 70 matrices using 143,640 multiplications, and a way of multiplying 72 Γ 72 matrices using 155,424 multiplications. Which method yields the best asymptotic running time when used in a divideandconquer matrixmultiplication algorithm? How does it compare to Strassenβs algorithm?
Skipped.
4.26
How quickly can you multiply a k n Γ n matrix by an n Γ k n matrix, using Strassenβs algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.
Skipped.
4.27
Show how to multiply the complex numbers a + b i and c + d i using only three multiplications of real numbers. The algorithm should take a, b, c, and d as input and produce the real component a c  b d and the imaginary component a d + b c separately.
Reference: (a + b i) Γ (c + d i) = a c  b d + (a d + b c) i.
Let w = (a + b) Γ (c  d), x = a Γ d, y = b Γ c, which uses three real number multiplications, then the result can be calculated as (w + x  y) + (x + y) i.
4.3 The substitution method for solving recurrences
4.31
Show that the solution of T(n) = T(n  1) + n is O($n^2$).
T(n)
= T(n  1) + n
β€ c $\left(n  1\right)^2$ + n
= c $n^2$  2 c n + c + n
= c $n^2$  (2 c  1) n + c
Here we choose c = 1, we have
c $n^2$  (2 c  1) n + c = $n^2$  n + 1.
If n β₯ 1, we have $n^2$  n + 1 β€ $n^2$, that is, T(n) β€ c $n^2$, since c = 1.
4.32
Show that the solution of T(n) = T(βn / 2β) + 1 is O(lg n).
T(n)
= T(βn / 2β) + 1
β€ c lg βn / 2β + 1
= c lg (βn / 2β $2^{1 / c}$)
< c lg ((n / 2 + 1) $2^{1 / c}$)
= c lg ($2^{1 / c  1}$ n + $2^{1 / c}$)
If we choose c = 2, we have
c lg ($2^{1 / c  1}$ n + $2^{1 / c}$) = 2 lg ($2^{1 / 2}$ n + $2^{1 / 2}$).
If n β₯ 2 $\sqrt{2}$ + 2, we have $2^{1 / 2}$ n + $2^{1 / 2}$ β€ n.
So for c = 2 and n β₯ 2 $\sqrt{2}$ + 2, we have T(n) < c lg ($2^{1 / c  1}$ n + $2^{1 / c}$) β€ c lg n.
4.33
We saw that the solution of T(n) = 2 T(βn / 2β) + n is O(n lg n). Show that the solution of this recurrence is also Ξ©(n lg n). Conclude that the solution is Ξ(n lg n).
T(n)
= 2 T(βn / 2β) + n
β₯ 2 c βn / 2β lg βn / 2β + n
> 2 c (n / 2  1) lg (n / 2  1) + n
Skipped.
4.34
Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition T(1) = 1 for recurrence (4.19) without adjusting the boundary conditions for the inductive proof.
Skipped.
4.35
Show that Ξ(n lg n) is the solution to the βexactβ recurrence (4.3) for merge sort.
Skipped.
4.36
Show that the solution to T(n) = 2 T(βn / 2β + 17) + n is O(n lg n).
T(n)
= 2 T(βn / 2β + 17) + n
β€ 2 c (βn / 2β + 17) lg (βn / 2β + 17) + n
< 2 c ((n + 2) / 2 + 17) lg ((n + 2) / 2 + 17) + n
Skipped.
4.37
Using the master method in Section 4.5, you can show that the solution to the recurrence T(n) = 4 T(n / 3) + n is T(n) = Ξ($n^{\log_3 4}$). Show that a substitution proof with the assumption T(n) β€ c $n^{\log_3 4}$ fails. Then show how to subtract off a lowerorder term to make a substitution proof work.
Suppose T(n) = c $n^{\log_3 4}$  3 n, we have:
T(n)
= 4 T(n / 3) + n
= 4 (c $\left(n / 3\right)^{\log_3 4}$  3 (n / 3)) + n
= 4 (c $n^{\log_3 4}$ / 4  n) + n
= c $n^{\log_3 4}$  3 n.
That is exactly what we want.
4.38
Using the master method in Section 4.5, you can show that the solution to the recurrence T(n) = 4 T(n / 2) + n is T(n) = Ξ($n^2$). Show that a substitution proof with the assumption T(n) β€ c $n^2$ fails. Then show how to subtract off a lowerorder term to make a substitution proof work.
Suppose T(n) = c $n^2$  n, we have
T(n)
= 4 (c $\left(n / 2\right)^2$  n / 2) + n
= 4 (c $n^2$ / 4  n / 2) + n
= c $n^2$  2 n + n
= c $n^2$  n.
That is exactly what we want.
4.39
Solve the recurrence T(n) = 3 T($\sqrt{n}$) + log n by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.
Let m = log n, we have n = $10^m$, so
T($10^m$)
= 3 T($\sqrt{10^m}$) + log $10^m$
= 3 T($10^{m / 2}$) + m.
Let S(m) = T($10^m$), we have:
S(m) = 3 S(m / 2) + m.
I guess S(m) = c $m^{\lg 3}$  2 m,
S(m)
= 3 (c $(m / 2)^{\lg 3}$  2 (m / 2)) + m
= 3 (c $m^{\lg 3}$ / 3  m) + m
= c $m^{\lg 3}$  3 m + m
= c $m^{\lg 3}$  2 m.
So my guess is right.
T(n)
= S(log n)
= c $(\log n)^{\lg 3}$  2 log n.
Notes:
Solving T(n) = a T(n / b) + k $n^p$: if p = $\log_b a$, T(n) = k $n^p \log_b n$ + c $n^p$, otherwise T(n) = c $n^{\log_b a}$ + (k / (1  a / $b^p$)) $n^p$.
4.4 The recursiontree method for solving recurrences
4.41
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 3 T(βn / 2β) + n. Use the substitution method to verify your answer.
T(n) β€ c $n^{\lg 3}$  2 n.
Verification:
T(n)
= 3 T(βn / 2β) + n
β€ 3 (c $\left\lfloor{}n / 2\right\rfloor^{\lg 3}$  2 βn / 2β) + n
β€ 3 (c $\left(n / 2\right)^{\lg 3}$  2 (n / 2)) + n
= 3 (c $n^{\lg 3}$ / 3  n) + n
= 3 c $n^{\lg 3}$ / 3  3 n + n
= c $n^{\lg 3}$  2 n.
4.42
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = T(n / 2) + $n^2$. Use the substitution method to verify your answer.
T(n) = c + (4 / 3) $n^2$.
Verification:
T(n)
= c + (4 / 3) $\left(n / 2\right)^2$ + $n^2$
= c + (1 / 3) $n^2$ + $n^2$
= c + (4 / 3) $n^2$.
4.43
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 4 T(n / 2 + 2) + n. Use the substitution method to verify your answer.
T(n) = c $n^2$  (8 c + 1) n + 16 c + 8 / 3.
Verification:
T(n)
= 4 T(n / 2 + 2) + n
= 4 (c $\left(n / 2 + 2\right)^2$  (8 c + 1) (n / 2 + 2) + 16 c + 8 / 3) + n
= 4 (c ($n^2$ / 4 + 2 n + 4)  (4 c n + 16 c + n / 2 + 2) + 16 c + 8 / 3) + n
= 4 (c $n^2$ / 4  (2 c + 1 / 2) n + 4 c + 2 / 3) + n
= c $n^2$  (8 c + 2) n + 16 c + 8 / 3 + n
= c $n^2$  (8 c + 1) n + 16 c + 8 / 3.
4.44
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 2 T(n  1) + 1. Use the substitution method to verify your answer.
T(n) = c $2^n$  1
Verification:
T(n)
= 2 T(n  1) + 1
= 2 (c $2^{n  1}$  1) + 1
= c $2^n$  2 + 1
= c $2^n$  1.
4.45
Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = T(n  1) + T(n / 2) + n. Use the substitution method to verify your answer.
T(n) = O($2^n$), and T(n) = Ξ©(n lg n).
Skipped.
4.46
Argue that the solution to the recurrence T(n) = T(n / 3) + T(2 n / 3) + c n, where c is a constant, is Ξ©(n lg n) by appealing to a recursion tree.
On each level of recursion whose depth is less than lg n / lg 3, the cost on this level is c n, so the cost is at least c n lg n / lg 3, that is T(n) = Ξ©(n lg n).
4.47
Draw the recursion tree for T(n) = 4 T(βn / 2β) + c n, where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method.
T(n) β₯ k $n^2$  (c  4 k) n + 4 k  4 c / 3.
Verification:
T(n)
= 4 T(βn / 2β) + c n
β₯ 4 T(n / 2  1) + c n
β₯ 4 (k $(n / 2  1)^2$  (c  4 k) (n / 2  1) + 4 k  4 c / 3) + c n
= k $n^2$  (c  4 k) n + 4 k  4 c / 3.
T(n) β€ k $n^2$  c n.
Verification:
T(n)
= 4 T(βn / 2β) + c n
β€ 4 T(n / 2) + c n
β€ 4 (k $(n / 2)^2$  c (n / 2)) + c n
= k $n^2$  c n.
So T(n) = Ξ($n^2$).
4.48
Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(n  a) + T(a) + c n, where a β₯ 1 and c > 0 are constants.
T(n) = (c / (2 a)) $n^2$ + k n  a c.
Verification:
T(n)
= T(n  a) + T(a) + c n
= (c / (2 a)) $\left(n  a\right)^2$ + k (n  a)  a c + (c / (2 a)) $a^2$ + k a  a c + c n
= (c / (2 a)) ($n^2$  2 a n + $a^2$) + k n  a k  2 a c + a c / 2 + k a + c n
= (c / (2 a)) $n^2$  c n + a c / 2 + k n  2 a c + a c / 2 + c n
= (c / (2 a)) $n^2$ + k n  a c
4.49
Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(Ξ± n) + T((1  Ξ±) n) + c n, where Ξ± is a constant in the range 0 < Ξ± < 1 and c > 0 is also a constant.
Like exercise 4.46, we can prove T(n) = Ξ©(n lg n), and T(n) = O(n lg n), so T(n) = Ξ(n lg n).
4.5 The master method for solving recurrences
4.51
Use the master method to give tight asymptotic bounds for the following recurrences.
 T(n) = 2 T(n / 4) + 1.
 T(n) = 2 T(n / 4) + $\sqrt{n}$.
 T(n) = 2 T(n / 4) + n.
 T(n) = 2 T(n / 4) + $n^2$.
 T(n) = Ξ($\sqrt{n}$).
 T(n) = Ξ($\sqrt{n}$ lg n).
 T(n) = Ξ(n).
 T(n) = Ξ($n^2$).
4.52
Professor Caesar wishes to develop a matrixmultiplication algorithm that is asymptotically faster than Strassenβs algorithm. His algorithm will use the divideandconquer method, dividing each matrix into pieces of size n / 4 Γ n / 4, and the divide and combine steps together will take Ξ($n^2$) time. He needs to determine how many subproblems his algorithm has to create in order to beat Strassenβs algorithm. If his algorithm creates a subproblems, then the recurrence for the running time T(n) becomes T(n) = a T(n / 4) + Ξ($n^2$). What is the largest integer value of a for which Professor Caesarβs algorithm would be asymptotically faster than Strassenβs algorithm?
The answer is 48. Since $log_4 49$ = lg 7.
4.53
Use the master method to show that the solution to the binarysearch recurrence T(n) = T(n / 2) + Ξ(1) is T(n) = Ξ(lg n). (See Exercise 2.35 for a description of binary search.)
Since Ξ(1) = Ξ($n^{\log_2 1}$), T(n) = Ξ($n^{\log_2 1}$ lg n) = Ξ(lg n).
4.54
Can the master method be applied to the recurrence T(n) = 4 T(n / 2) + $n^2$ lg n? Why or why not? Give an asymptotic upper bound for this recurrence.
The master method can not be applied to that recurrence, because $n^2$ lg n is asymptotically large than $n^{\log_2 4} = n^2$, but it is not polynomially asymptotically large than $n^{\log_2 4}$.
T(n) = $n^2 \left(\lg^2 n + \lg n + c\right)$ / 2.
Verification:
T(n)
= 4 T(n / 2) + $n^2$ lg n
= 4 $(n / 2)^2 \left(\lg^2 (n / 2) + \lg (n / 2) + c\right)$ / 2 + $n^2$ lg n
= 4 $(n / 2)^2 \left((\lg n  1)^2 + \lg n  1 + c\right)$ / 2 + $n^2$ lg n
= 4 $(n / 2)^2 \left(\lg^2 n  2 \lg n + 1 + \lg n  1 + c\right)$ / 2 + $n^2$ lg n
= $n^2 \left(\lg^2 n  \lg n + c\right)$ / 2 + $n^2$ lg n
= $n^2 \left(\lg^2 n + \lg n + c\right)$ / 2.
4.55 β
Consider the regularity condition a f(n / b) β€ c f(n) for some constant c < 1, which is part of case 3 of the master theorem. Give an example of constants a β₯ 1 and b > 1 and a function f(n) that satisfies all the conditions in case 3 of the master theorem except the regularity condition.
Skipped.
4.6 Proof of the master theorem β
4.61 β
Give a simple and exact expression for $n_j$ in equation (4.27) for the case in which b is a positive integer instead of an arbitrary real number.
Theorem 3.4 and 3.5:
For any real number x β₯ 0 and integers a, b > 0:
 $\left\lceil\frac{\left\lceil x / a\right\rceil}{b}\right\rceil = \left\lceil\frac{x}{a b}\right\rceil$,
 $\left\lfloor\frac{\left\lfloor x / a\right\rfloor}{b}\right\rfloor = \left\lfloor\frac{x}{a b}\right\rfloor$.
$n_j$ = βn / $b^j$β.
Proof by induction:
 If j = 0, $n_j$ = βn / $b^j$β = βn / $b^0$β = βnβ = n, the claim holds.
 If j > 0, $n_j$ = β$n_{j  1}$ / bβ = ββn / $b^{j  1}$β / bβ, since both b and $b^{j  1}$ are integers, ββn / $b^{j  1}$β / bβ = βn / $b^{j  1}$ / bβ = βn / $b^j$β. So $n_j$ = βn / $b^j$β, the claim holds.
Notes:
In the book Concrete Mathematics, there is a theorem:

Let f(x) be any continuous, monotonically increasing function with the property that
 f(x) = integer β x = integer.
Then we have
 βf(x)β = βf(βxβ)β and βf(x)β = βf(βxβ)β,
whenever f(x), f(βxβ), and f(βxβ) are defined.
Proof:
f(βxβ)  1 < βf(βxβ)β β€ f(βxβ)
β βf(βxβ)β β€ f(βxβ) < βf(βxβ)β + 1
β $f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor\right)$ β€ $f^{1}\left(f\left(\left\lfloor x\right\rfloor\right)\right)$ < $f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor + 1\right)$
β $f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor\right)$ β€ βxβ < $f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor + 1\right)$.
Since $\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor + 1$ is an integer, and we also have f(x) = integer β x = integer, we know that $f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor + 1\right)$ is an integer. Because βxβ < $f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor + 1\right)$, we have x < $f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor + 1\right)$. So:
$f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor\right)$ β€ βxβ < $f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor + 1\right)$
β $f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor\right)$ β€ x < $f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor + 1\right)$
β $f\left(f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor\right)\right)$ β€ f(x) < $f\left(f^{1}\left(\left\lfloor f\left(\left\lfloor x\right\rfloor\right)\right\rfloor + 1\right)\right)$
β βf(βxβ)β β€ f(x) < βf(βxβ)β + 1
β f(x) = βf(βxβ)β.
The same method can be applied to proving βf(x)β = βf(βxβ)β.
4.62 β
Show that if f(n) = Ξ($n^{\log_b a} \lg^k n$), where k β₯ 0, then the master recurrence has solution T(n) = Ξ($n^{\log_b a} \lg^{k + 1} n$). For simplicity, confine your analysis to exact powers of b.
T(n)
= Ξ($n^{\log_b a}$) + $β_{j = 0}^{\log_b n  1} a^j f(n / b^j)$
= Ξ($n^{\log_b a}$) + $β_{j = 0}^{\log_b n  1} a^j Ξ\left(\left(n / b^j\right)^{\log_b a} \lg^k \left(n / b^j\right)\right)$
= Ξ($n^{\log_b a}$) + $β_{j = 0}^{\log_b n  1} Ξ\left(a^j \left(n / b^j\right)^{\log_b a} \lg^k \left(n / b^j\right)\right)$
= Ξ($n^{\log_b a}$) + $β_{j = 0}^{\log_b n  1} Ξ\left(n^{\log_b a} \left(\lg n  \lg \left(b^j\right)\right)^k\right)$
= Ξ($n^{\log_b a}$) + $β_{j = 0}^{\log_b n  1} Ξ\left(n^{\log_b a} \left(\lg n  j \lg b\right)^k\right)$
= Ξ($n^{\log_b a}$) + $β_{j = 0}^{\log_b n  1} Ξ\left(n^{\log_b a} \lg^k n\right)$
= Ξ($n^{\log_b a}$) + $n^{\log_b a} Ξ\left(\left(\log_b n  1\right)\lg^k n\right)$
= Ξ($n^{\log_b a}$) + $n^{\log_b a} Ξ\left(\log_b n \lg^k n  \lg^k n\right)$
= Ξ($n^{\log_b a}$) + $n^{\log_b a} Ξ\left(\lg^{k + 1} n\right)$
= Ξ($n^{\log_b a} \lg^{k + 1} n$).
4.63 β
Show that case 3 of the master theorem is overstated, in the sense that the regularity condition a f(n / b) β€ c f(n) for some constant c < 1 implies that there exists a constant Ο΅ > 0 such that f(n) = Ξ©($n^{\log_b a + Ο΅}$).
Let Ο΅ = $\log_b c$, I guess f(n) = Ξ©($n^{\log_b a  \log_b c}$).
f(n)
β₯ (a / c) f(n / b)
= (a / c) Ξ©($\left(n / b\right)^{\log_b a  \log_b c}$)
= (a / c) Ξ©($n^{\log_b a  \log_b c} / \left(a / c\right)$)
= Ξ©($n^{\log_b a  \log_b c}$).
4.X Problems
41 Recurrence examples
Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n β€ 2. Make your bounds as tight as possible, and justify your answers.
 T(n) = 2 T(n / 2) + $n^4$.
 T(n) = T(7 n / 10) + n.
 T(n) = 16 T(n / 4) + $n^2$.
 T(n) = 7 T(n / 3) + $n^2$.
 T(n) = 7 T(n / 2) + $n^2$.
 T(n) = 2 T(n / 4) + $\sqrt{n}$
 T(n) = T(n  2) + $n^2$.
 T(n) = c n + (8 / 7) $n^4$.
 T(n) = (10 / 3) n + c.
 T(n) = $n^2 \log_4 n$ + c $n^2$.
 T(n) = (9 / 2) $n^2$ + c $n^{\log_3 7}$.
 T(n) = c $n^{\lg 7}$  (4 / 3) $n^2$.
 T(n) = $\sqrt{n} \log_4 n$ + c $\sqrt{n}$.
 T(n) = $n^3$ / 6 + $n^2$ / 2 + n / 3 + c.
42 Parameterpassing costs
Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an Nelement array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself. This problem examines the implications of three parameterpassing strategies:
 An array is passed by pointer. Time = Ξ(1).
 An array is passed by copying. Time = Ξ(N), where N is the size of the array.
 An array is passed by copying only the subrange that might be accessed by the called procedure. Time = Ξ(q  p + 1) if the subarray A[pβ₯q] is passed.
 Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 2.35). Give recurrences for the worstcase running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let N be the size of the original problem and n be the size of a subproblem.
 Redo part (a) for the MergeSort algorithm from Section 2.3.1.
 Binary search algorithm

By pointer: T(n) = T(n / 2) + Ξ(1).
T(N) = Ξ(lg N).

By copying: T(n) = T(n / 2) + Ξ(N).
T(N) = Ξ(N lg N).

By copying subrange: T(n) = T(n / 2) + Ξ(n).
T(N) = Ξ(N).

 Merge sort algorithm

By pointer: T(n) = 2 T(n / 2) + Ξ(n).
T(N) = Ξ(N lg N).

By copying: T(n) = 2 T(n / 2) + Ξ(n) + Ξ(N*).
T(n)
= Ξ(n) + $β_{j = 0}^{\lg n  1} Ξ\left(2^j (n / 2^j)\right)$ + $β_{j = 0}^{\lg n  1} Ξ\left(2^j N\right)$
= Ξ(n) + Ξ(n lg n) + Ξ(N n)T(N) = Ξ($N^2$).

By copying subrange: T(n) = 2 T(n / 2) + Ξ(n), T(N) = Ξ(N lg N).

43 More recurrence examples
Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for sufficiently small n. Make your bounds as tight as possible, and justify your answers.
 T(n) = 4 T(n / 3) + n lg n.
 T(n) = 3 T(n / 3) + n / lg n.
 T(n) = 4 T(n / 2) + $n^2 \sqrt{n}$.
 T(n) = 3 T(n / 3  2) + n / 2.
 T(n) = 2 T(n / 2) + n / lg n.
 T(n) = T(n / 2) + T(n / 4) + T(n / 8) + n.
 T(n) = T(n  1) + 1 / n.
 T(n) = T(n  1) + lg n.
 T(n) = T(n  2) + 1 / lg n.
 T(n) = $\sqrt{n}$ T($\sqrt{n}$) + n
 T(n) = c $n^{\log_3 4}$  3 n lg n  12 n lg 3.
 T(n) = Ξ(n), according to exercise 4.62.
 T(n) = (2 + $\sqrt{2}$) $n^{5 / 2}$ + c $n^2$.
 T(n) = (1 / 2) n $\log_3 \left(n + 3\right)$ + c n + (3 / 2) $\log_3 \left(n + 3\right)$ + 3 c + 3 / 4.
 T(n) = Ξ(n), according to exercise 4.62.
 T(n) = 8 n.
 T(n) = c + $β_{j = 2}^n \left(1 / j\right)$ = Ξ(lg n).
 T(n) = c + $β_{j = 2}^n \lg n$ = c + $\lg β_{j = 2}^n n$ = c + lg n! = Ξ(n lg n).
 Skipped.
 T(n) = n lg lg n + c n.
44 Fibonacci numbers
This problem develops properties of the Fibonacci numbers, which are defined by recurrence (3.22). We shall use the technique of generating functions to solve the Fibonacci recurrence. Define the generating function (or formal power series) β± as
$\begin{aligned} β±\left(z\right) &= \displaystyle β_{i = 0}^β F_i z^i\\ &= 0 + z + z^2 + 2 z^3 + 3 z^4 + 5 z^5 + 8 z^6 + 13 z^7 + 21 z^8 + β―, \end{aligned}$
where $F_i$ is the ith Fibonacci number.
Show that β±(z) = z + z β±(z) + $z^2$ β±(z).
Show that
$\begin{aligned} β±\left(z\right) &= \frac{z}{1  z  z^2}\\ &= \frac{z}{\left(1  Ο z\right)\left(1  \hat{Ο} z\right)}\\ &= \frac{1}{\sqrt{5}}\left(\frac{1}{1  Ο z}  \frac{1}{1  \hat{Ο} z}\right), \end{aligned}$
where
$Ο$ = $\dfrac{1 + \sqrt{5}}{2}$ = 1.61803β¦
and
$\hat{Ο}$ = $\dfrac{1  \sqrt{5}}{2}$ =  1.61803β¦ .
Show that
β±(z) = $\displaystyle β_{i = 0}^β \frac{1}{\sqrt{5}}\left(Ο^i  \hat{Ο}^i\right) z^i$.
Use part (c) to prove that $F_i = Ο^i / \sqrt{5}$ for i > 0, rounded to the nearest integer. (Hint: Observe that $\hat{Ο}$ < 1.)

By definition:
$\begin{aligned} z + z β±\left(z\right) + z^2 β±\left(z\right) &= z + z β_{i = 0}^β F_i z^i + z^2 β_{i = 0}^β F_i z^i\\ &= z + β_{i = 0}^β F_i z^{i + 1} + β_{i = 0}^β F_i z^{i + 2}\\ &= z + β_{i = 1}^β F_{i  1} z^i + β_{i = 2}^β F_{i  2} z^i\\ &= z + \left(F_0 z^1 + β_{i = 2}^β F_{i  1} z^i\right) + β_{i = 2}^β F_{i  2} z^i\\ &= z + F_0 z^1 + \left(β_{i = 2}^β F_{i  1} z^i + β_{i = 2}^β F_{i  2} z^i\right)\\ &= F_1 z^1 + F_0 z^0 + β_{i = 2}^β F_i z^i\\ &= F_0 z^0 + F_1 z^1 + β_{i = 2}^β F_i z^i\\ &= β_{i = 0}^β F_i z^i\\ &= β±\left(z\right). \end{aligned}$

β±(z) = z + z β±(z) + $z^2$ β±(z)
β β±(z)  z β±(z)  $z^2$ β±(z) = z
β β±(z) (1  z  $z^2$) = z
β β±(z) = z / (1  z  $z^2$).z / ((1  Ο z) (1  $\hat{Ο}$ z))
= z / (1  (Ο + $\hat{Ο}$) z + Ο $\hat{Ο} z^2$)
= z / (1  z  $z^2$)
= β±(z).$\frac{1}{\sqrt{5}} \left(\frac{1}{1  Ο z}  \frac{1}{1  \hat{Ο} z}\right)$
= $\frac{1}{\sqrt{5}} \frac{\left(1  \hat{Ο} z\right)  \left(1  Ο z\right)}{\left(1  Ο z\right) \left(1  \hat{Ο} z\right)}$
= $\frac{1}{\sqrt{5}} \frac{\left(Ο  \hat{Ο}\right) z}{\left(1  Ο z\right) \left(1  \hat{Ο} z\right)}$
= $\frac{1}{\sqrt{5}} \frac{\sqrt{5} z}{\left(1  Ο z\right) \left(1  \hat{Ο} z\right)}$
= $\frac{z}{\left(1  Ο z\right) \left(1  \hat{Ο} z\right)}$
= β±(z).An interesting discovery: if we let z = 1, we have β±(1) = 1 / (1  1  $1^2$) = 1. Also, according to the definition of β±, we have: $β±\left(1\right) = β_{i = 0}^β F_i 1^i = β_{i = 0}^β F_i$.
So we have $β_{i = 0}^β F_i$ = 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + β¦ = 1, WTF?

$β_{i = 0}^β \frac{1}{\sqrt{5}}\left(Ο^i  \hat{Ο}^i\right) z^i$
= $\frac{1}{\sqrt{5}} β_{i = 0}^β \left(Ο^i  \hat{Ο}^i\right) z^i$
= $\frac{1}{\sqrt{5}} \left(β_{i = 0}^β \left(Ο z\right)^i  β_{i = 0}^β \left(\hat{Ο} z\right)^i\right)$
= $\frac{1}{\sqrt{5}} \left(\frac{1}{1  Ο z}  \frac{1}{1  \hat{Ο} z}\right)$
= β±(z). 
$F_i = \frac{1}{\sqrt{5}}\left(Ο^i  \hat{Ο}^i\right) = Ο^i / \sqrt{5}  \hat{Ο}^i / \sqrt{5}$
β $F_i  Ο^i / \sqrt{5} =  \hat{Ο}^i / \sqrt{5}$.Since $\left \hat{Ο}^i / \sqrt{5}\right$ < 0.5, and $F_i$ is an integer, $F_i = Ο^i / \sqrt{5}$, rounded to the nearest integer.
45 Chip testing
Professor Diogenes has n supposedly identical integratedcircuit chips that in principle are capable of testing each other. The professorβs test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Thus, the four possible outcomes of a test are as follows:
Chip A says Chip B says Conclusion B is good A is good both are good, or both are bad B is good A is bad at least one is bad B is bad A is good at least one is bad B is bad A is bad at least one is bad
 Show that if at least n / 2 chips are bad, the professor cannot necessarily determine which chips are good using any strategy based on this kind of pairwise test. Assume that the bad chips can conspire to fool the professor.
 Consider the problem of finding a single good chip from among n chips, assuming that more than n / 2 of the chips are good. Show that βn / 2β pairwise tests are sufficient to reduce the problem to one of nearly half the size.
 Show that the good chips can be identified with Ξ(n) pairwise tests, assuming that more than n / 2 of the chips are good. Give and solve the recurrence that describes the number of tests.

If there are at least n / 2 chips are bad, there must exist same number of bad chips from good chips, and the bad chips can simulate whatever the behavior the good chips have, so it is not possible to distinguish bad chips from good chips.

Generalize the original problem to this:
Assume there are no less good chip than bad chips:
 If the number of good chips is greater than the number of bad chips, find a good chip.
 If the number of good chips is greater than or equal to the number of bad chips, find a good chip or say the number of good chips equal to the number of bad chips.
 Otherwise, the result is undefined.
Solution:
 Base case: If there is zero chip, we say that the number of good chips equal to the number of bad chips.
 Inductive cases:
 If the number of chips is even, we group them into pairs, then in each pair, we test each chip with the other chip. If the chips in one pair both say the other one is a good chip, we throw away any one chip in this pair; otherwise, we throw away both chips. Then we will be left with at most half of the original chips. And since chip pairs that do not say each other is good ether have one bad chip or have two bad chips, throwing them away does not change the fact that good chips are not less than bad chips. The remaining chip pairs are either both good chips or bad chips, after throwing away one chip in every those pairs, we have reduced the size of the problem to at most half of the original problem size.
 If the number of chips is odd, we know that the number of good chip must be greater than the number of bad chips, since there can not be the same number of good chips and bad chips. We randomly remove one chip from the chips, and we will be left with even number of chips, in which good chips are no less than bad chips. We process the remaining chips with the method used in the even number case. After the remaining chips being processed, either we get a good chip, or we are told that the number of good chips are the same as the number of bad chips, which means the chip we removed is a good chip. Either way, we can get a good chip.
The solution to the generalized problem applies to the original problem.

With the solution above, we can find one good chip in number T(n) β€ T(n / 2) + Ξ(n) pair tests. According to the master theorem, we have T(n) = O(n). After we found one good we can identify all good chips with that good chip in Ξ(n) time, so the total number of pairwise tests equals to O(n) + Ξ(n) = Ξ(n).
The solution is implemented here.
46 Monge arrays
An m Γ n array A of real numbers is a Monge array if for all i, j, k, and l such that 1 β€ i < k β€ m and 1 β€ j < l β€ n, we have
A[i, j] + A[k, l] β€ A[i, l] + A[k, j].
In other words, whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersections of the rows and the columns, the sum of the upperleft and lowerright elements is less than or equal to the sum of the lowerleft and upperright elements. For example, the following array is Monge:
10 17 13 28 23 17 22 16 29 23 24 28 22 34 24 11 13 6 17 7 45 44 32 37 23 36 33 19 21 6 75 66 51 53 34
Prove that an array is Monge if and only if for all i = 1, 2, β¦, m  1 and j = 1, 2, β¦, n  1, we have A[i, j] + A[i + 1, j + 1] β€ A[i, j + 1] + A[i + 1, j].
(Hint: For the βifβ part, use induction separately on rows and columns.)
The following array is not Monge. Change one element in order to make it Monge. (Hint: Use part (a).)
37 23 22 32 21 6 7 10 53 34 30 31 32 13 9 6 43 21 15 8 Let f(i) be the index of the column containing the leftmost minimum element of row i. Prove that f(1) β€ f(2) β€ β― β€ f(m) for any m Γ n Monge array.
Here is a description of a divideandconquer algorithm that computes the leftmost minimum element in each row of an m Γ n Monge array A:
 Construct a submatrix Aβ² of A consisting of the evennumbered rows of A. Recursively determine the leftmost minimum for each row of Aβ². Then compute the leftmost minimum in the oddnumbered rows of A.
Explain how to compute the leftmost minimum in the oddnumbered rows of A (given that the leftmost minimum of the evennumbered rows is known) in O(m + n) time.
Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is O(m + n log m).

Proof:
 The βonly ifβ part is trivial.
 The βifβ part:

First, we prove that: for all i, j, and l such that 1 β€ i < m and 1 β€ j < l β€ n, we have A[i, j] + A[i + 1, l] β€ A[i, l] + A[i + 1, j].
Proof by induction:

Base case: Trivially, A[i, j] + A[i + 1, j + 1] β€ A[i, j + 1] + A[i + 1, j].

Inductive case: by induction, we have A[i, j] + A[i + 1, l  1] β€ A[i, l  1] + A[i + 1, j]. Since A[i, l  1] + A[i + 1, l] β€ A[i, l] + A[i + 1, l  1], we have:
(A[i, j] + A[i + 1, l  1]) + (A[i, l  1] + A[i + 1, l]) β€ (A[i, l  1] + A[i + 1, j]) + (A[i, l] + A[i + 1, l  1])
β (A[i, j] +A[i + 1, l  1]) + (A[i, l  1]+ A[i + 1, l]) β€ (A[i, l  1]+ A[i + 1, j]) + (A[i, l] +A[i + 1, l  1])
β A[i, j] + A[i + 1, l] β€ A[i + 1, j] + A[i, l]
β A[i, j] + A[i + 1, l] β€ A[i, l] + A[i + 1, j].


Second, we prove the original claim by induction.

Base case: according to the first step, we have: for all i, j, and l such that 1 β€ i < m and 1 β€ j < l β€ n, we have A[i, j] + A[i + 1, l] β€ A[i, l] + A[i + 1, j].

Inductive case: by induction, A[i, j] + A[k  1, l] β€ A[i, l] + A[k  1, j]. Since A[k  1, j] + A[k, l] β€ A[k  1, l] + A[k, j], we have:
(A[i, j] + A[k  1, l]) + (A[k  1, j] + A[k, l]) β€ (A[i, l] + A[k  1, j]) + (A[k  1, l] + A[k, j])
β (A[i, j] +A[k  1, l]) + (A[k  1, j]+ A[k, l]) β€ (A[i, l] +A[k  1, j]) + (A[k  1, l]+ A[k, j])
β A[i, j] + A[k, l] β€ A[i, l] + A[k, j]



Result:
37 23 24 32 21 6 7 10 53 34 30 31 32 13 9 6 43 21 15 8 
Proof by contradiction:
Assume for some i, f(i) > f(i + 1), let f(i) = j, and f(i + 1) = l. Since f(i) is the leftmost minimum element of row i, and f(i + 1) is the leftmost minimum element of row i + 1, we have
A[i, l] > A[i, j], and A[i + 1, j] > A[i + 1, l]
β A[i, l] + A[i + 1, j] > A[i, j] + A[i + 1, l].That violates the condition of Monge array, so our assumption is wrong. That proves the claim is right.

If f(i  1) = j, and f(i + 1) = l, j β€ f(i) β€ l.
The time for computing the leftmost minimal element of odd row i is Ξ(f(i + 1)  f(i  1) + 1).

If the number of rows is even, the time for computing the leftmost minimal element of all odd rows is
Ξ(f(2) + $β_{i = 1}^{m / 2  1} \left(f\left(2 i + 2\right)  f\left(2 i\right) + 1\right)$)
= Ξ(f(2) + (f(m)  f(2) + m / 2  1))
= Ξ(f(m) + m / 2  1)
= O(n + m / 2  1)
= O(n + m) 
If the number of rows is odd, the time for computing the leftmost minimal element of all odd rows is:
Ξ(f(2) + $β_{i = 1}^{\left(m  3\right) / 2} \left(f\left(2 i + 2\right)  f\left(2 i\right) + 1\right)$ + (n  f(m  1) + 1))
= Ξ(f(2) + (f(m  1)  f(2) + (m  3) / 2) + (n  f(m  1) + 1))
= Ξ((m  3) / 2 + n + 1)
= Ξ(m / 2 + n  1 / 2)
= O(m + n)
So the time cost for computing the leftmost minimum in the oddnumbered rows is O(m + n).


T(m, n) = T(m / 2, n) + O(m + n).
T(m, n)
= Ξ(1) + O($β_{i=0}^{\lg m  1} \left(m / \left(2^i\right) + n\right)$)
= Ξ(1) + O($β_{i=0}^{\lg m  1} \left(m / \left(2^i\right)\right) + β_{i=0}^{\lg m  1} n$)
= Ξ(1) + O(m $β_{i=0}^{\lg m  1} \left(1 / 2\right)^i + β_{i=0}^{\lg m  1} n$)
= Ξ(1) + O(m (1  $\left(1 / 2\right)^{\lg m}$) / (1  1 / 2) + n lg m)
= Ξ(1) + O(2 m (1  (1 / m)) + n lg m)
= Ξ(1) + O(2 m  2 + n lg m)
= O(m + n lg m)
5 Probabilistic Analysis and Randomized Algorithms
5.1 The hiring problem
5.11
Show that the assumption that we are always able to determine which candidate is best, in line 4 of procedure HireAssistant, implies that we know a total order on the ranks of the candidates.
We can prove it by proving its contrapositive:
 If the ranks of the candidates donβt form a total order, there exist a set of candidates in which we are not able to determine which candidate is best.
Proof:
 Total relation is violated: If there exist two candidates that we can not compare them, then we can not decide which one is best.
 Reflexive is violated: Skipped.
 Antisymmetric is violated: If candidate a is better than or equal to candidate b, and candidate b is better than or equal to candidate a, but they are not the same people, we can not decide which one is the best.
 Transitive is violated: If candidate a is better than or equal to candidate b, and candidate b is better than or equal to candidate c, but a is not better than or equal to candidate c, we can not decide which one is best.
5.12 β
Describe an implementation of the procedure Random(a, b) that only makes calls to Random(0, 1). What is the expected running time of your procedure, as a function of a and b?
The procedure is implemented here.
let n = βlg (b  a + 1)β be the number of bits need to generate.
After generating n bits of number we are in a space of $2^n$ numbers. But the space we need to generate is of size b  a + 1. We have the possibility of p = (b  a + 1) / $2^n$ to get a usable random number, and possibility of 1  p to generate the number again.
Let k = Ξ(n) be the time needed to generate an n bit random number.
T(a, b) = p k + (1  p) (k + T(a, b)).
β T(a, b) = p k + (1  p) k + (1  p) T(a, b).
β T(a, b) = k + (1  p) T(a, b).
β T(a, b) = k / (1  (1  p)).
β T(a, b) = k / p.
β T(a, b) = Ξ(n) / ((b  a + 1) / $2^n$).
β T(a, b) = Ξ(n) $2^{\left\lceil\lg \left(b  a + 1\right)\right\rceil}$ / (b  a + 1).
β T(a, b) = Ξ(n $2^{\left\lceil\lg \left(b  a + 1\right)\right\rceil}$ / (b  a + 1)).
β T(a, b) = Ξ(n $2^{\lg \left(b  a + 1\right)}$ / (b  a + 1)), because $Ξ(n) = 2^n β€ 2^{\left\lceil n\right\rceil} < 2^{n + 1} = 2 Γ 2^n = Ξ(n)$.
β T(a, b) = Ξ(n (b  a + 1) / (b  a + 1)).
β T(a, b) = Ξ(n).
β T(a, b) = Ξ(βlg (b  a + 1)β).
5.13 β
Suppose that you want to output 0 with probability 1 / 2 and 1 with probability 1 / 2. At your disposal is a procedure BiasedRandom, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1  p, where 0 < p < 1, but you do not know what p is. Give an algorithm that uses BiasedRandom as a subroutine, and returns an unbiased answer, returning 0 with probability 1 / 2 and 1 with probability 1 / 2. What is the expected running time of your algorithm as a function of p?
Solution is implemented here.
Let k be the time used to generate and compare two random value, T(p) be the expected running time of our algorithm, we have:
T(p) = 2 p (1  p) k + (1  2 p (1  p)) (k + T(p))
β T(p) = k / (2 p ( 1  p)) = Ξ(1 / (p (1  p))).
5.2 Indicator random variables
5.21
In HireAssistant, assuming that the candidates are presented in a random order, what is the probability that you hire exactly one time? What is the probability that you hire exactly n times?
The probability of hiring exactly one time is 1 / n.
The probability of hiring exactly n times is 1 / n!.
5.22
In HireAssistant, assuming that the candidates are presented in a random order, what is the probability that you hire exactly twice?
The first candidate will be hired, so if there are two candidates being hired, the second candidate must be the best one, and all candidates between the first candidate and the best candidate are less good than the first candidate.
Let i be the rank of the first candidate, then there is i candidates are better than the first candidate, and n  i  1 candidates are less good than the first candidate. If there are j candidates between the first candidate and the best candidate, there are P(n  i  1, j) (n  j  2)! different situations.
So the probability is
$\frac{β_{i = 1}^{n  1} β_{j = 0}^{n  i  1} P(n  i  1, j) (n  j  2)!}{n!} = H_{n  1} / n$,
where $H_n$ is the nth harmonic number.
5.23
Use indicator random variables to compute the expected value of the sum of n dice.
Let $X_i$ be the indicator variable associated with the event in which the value of one dice is i.
So the expected value of one dice is:
E[X] = $β_{i = 1}^6 i \Pr\left\lbrace X_i = 1\right\rbrace$ = $β_{i = 1}^6 i / 6$ = 7 / 2.
So the expected value of n dices is:
$\operatorname{E}\left[β_{j = 1}^{n} X\right]$ = $β_{j = 1}^{n}\operatorname{E}\left[X\right]$ = 7 n / 2.
5.24
Use indicator random variables to solve the following problem, which is known as the hatcheck problem. Each of n customers gives a hat to a hatcheck person at a restaurant. The hatcheck person gives the hats back to the customers in a random order. What is the expected number of customers who get back their own hat?
Let $X_i$ be the indicator variable associated with the event in which the ith customer get back its own hat.
E[X]
= $\operatorname{E}\left[β_{i = 1}^n X_i\right]$
= $β_{i = 1}^n \operatorname{E}\left[X_i\right]$
= $β_{i = 1}^n 1 / n$
= $β_{i = 1}^n 1 / n$
= 1.
5.25
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. (See Problem 24 for more on inversions.) Suppose that the elements of A form a uniform random permutation of β¨1, 2, β¦, nβ©. Use indicator random variables to compute the expected number of inversions.
Let $X_{i j}$ be the indicator variable associated with the event in which the A[i] > A[j], where i < j.
E[X]
= $E\left[β_{i = 1}^{n  1} β_{j = i + 1}^{n} X_{i j}\right]$
= $β_{i = 1}^{n  1} E\left[β_{j = i + 1}^{n} X_{i j}\right]$
= $β_{i = 1}^{n  1} β_{j = i + 1}^{n} E\left[X_{i j}\right]$
= $β_{i = 1}^{n  1} β_{j = i + 1}^{n} 1 / 2$
= $β_{i = 1}^{n  1} \left(n  i\right) / 2$
= n (n  1) / 4.
5.31
Professor Marceau objects to the loop invariant used in the proof of Lemma 5.5. He questions whether it is true prior to the first iteration. He reasons that we could just as easily declare that an empty subarray contains no 0permutations. Therefore, the probability that an empty subarray contains a 0permutation should be 0, thus invalidating the loop invariant prior to the first iteration. Rewrite the procedure RandomizeInPlace so that its associated loop invariant applies to a nonempty subarray prior to the first iteration, and modify the proof of Lemma 5.5 for your procedure.
Solution is implemented here.
5.32
Professor Kelp decides to write a procedure that produces at random any permutation besides the identity permutation. He proposes the following procedure:
PermuteWithoutIdentity(A)
 n = A.length
 for i = 1 to n  1
 Β Β Β Β swap A[i] with A[Random(i + 1, n)]
Does this code do what Professor Kelp intends?
No, the algorithm above could not produce the permutation β¨A[1], A[3], A[2], A[4], A[5], β¦, A[n]β© which is not the identity permutation, because the first element always is always swapped away from its original position.
5.33
Suppose that instead of swapping element A[i] with a random element from the subarray A[iβ₯n], we swapped it with a random element from anywhere in the array:
PermuteWithAll(A)
 n = A.length
 for i = 1 to n
 Β Β Β Β swap A[i] with A[Random(1, n)]
Does this code produce a uniform random permutation? Why or why not?
In each iteration, there are n different possible outcomes of the Random function with the same possibility, so there are total of $n^n$ (possibly same) outcomes of the algorithm with the same possibility. But the uniform random permutation requires there are n! different possible outcomes. It is possible that $n^n / n!$ is not an integer, in which case, it is impossible to divide $n^n$ probabilities into $n!$ same probabilities. So, the code does not produce a uniform random permutation.
5.34
Professor Armstrong suggests the following procedure for generating a uniform random permutation:
PermuteByCyclic(A)
 n = A.length
 let B[1β₯n] be a new array
 offset = Random(1, n)
 for i = 1 to n
 Β Β Β Β dest = i + offset
 Β Β Β Β if dest > n
 Β Β Β Β Β Β Β Β dest = dest  n
 Β Β Β Β B[dest] = A[i]
 return B
Show that each element A[i] has a 1 / n probability of winding up in any particular position in B. Then show that Professor Armstrong is mistaken by showing that the resulting permutation is not uniformly random.
The permutation is generated by shifting the array by length Random(1, n). So for each position, any element can wind up at that position with probability of 1 / n.
There can only be n different outcomes with PermuteByCyclic, while the uniform distribution requires n! different results. So the result permutation can not be uniformly random.
5.35 β
Prove that in the array P in procedure PermuteBySorting, the probability that all elements are unique is at least 1  1 / n.
The probability is:
$P\left(n^3, n\right) / \left(n^3\right)^n$
= $\left(n^3! / \left(n^3  n\right)!\right) / \left(n^3\right)^n$
= $\left(β_{i = 0}^{n  1} \left(n^3  i\right)\right) / \left(β_{i = 0}^{n  1} n^3\right)$
= $β_{i = 0}^{n  1} \left(\left(n^3  i\right) / n^3\right)$
= $β_{i = 0}^{n  1} \left(1  i / n^3\right)$
β₯ $β_{i = 0}^{n  1} \left(1  n / n^3\right)$
= $β_{i = 0}^{n  1} \left(1  1 / n^2\right)$
= $\left(1  1 / n^2\right)^n$
Not sure how to go from here.
5.36
Explain how to implement the algorithm PermuteBySorting to handle the case in which two or more priorities are identical. That is, your algorithm should produce a uniform random permutation, even if two or more priorities are identical.
Skipped.
5.37
Suppose we want to create a random sample of the set {1, 2, 3, β¦, n}, that is, an melement subset S, where 0 β€ m β€ n, such that each msubset is equally likely to be created. One way would be to set A[i] = i for i = 1, 2, 3, β¦, n, call RandomizeInPlace(A), and then take just the first m array elements. This method would make n calls to the Random procedure. If n is much larger than m, we can create a random sample with fewer calls to Random. Show that the following recursive procedure returns a random msubset S of {1, 2, 3, β¦, n}, in which each msubset is equally likely, while making only m calls to Random:
RandomSample(m, n)
 if m == 0
 Β Β Β Β return β
 else S = RandomSample(m  1, n  1)
 Β Β Β Β i = Random(1, n)
 Β Β Β Β if i β S
 Β Β Β Β Β Β Β Β S = S βͺ {n}
 Β Β Β Β else S = S βͺ {i}
 Β Β Β Β return S
The algorithm is implemented here.
Like exercise 5.34, it is not enough by just proving β i β β and 1 β€ i β€ n, the probability of i β RandomSample(m, n) is m / n.
Lemma: RandomSample(m, n) generates any msubset with the probability of 1 / C(n, m).
Proof by induction on m:

Base case: RandomSample(0, n) only returns the empty set, and the only 0subset is the empty set, so the probability is 1, which equals to 1 / C(n, 0), the claim holds.

Inductive cases:

For a certain msubset containing n, there are two different ways to generate it:
 When i β S, which has the probability of (m  1) / n,
 Or i = n, which has the probability of 1 / n,
So the probability of generating an msubset containing n is (m  1) / n + 1 / n = m / n.
By induction, generating an (m  1)subset on the set [1, n  1] has the probability of 1 / C(n  1, m  1), so generating an msubset on the set [1, n] on set [1, n  1] has the probability of (1 / C(n  1, m  1)) (m / n) = 1 / C(n, m).

For a certain msubset does not contain n, let the last element being added to S can be k, then k can be any element in the msubset.
So the probability of generating a certain msubset does not contain n is $β_{j = 1}^{m} \left(1 / C\left(n  1, m  1\right)\right) \left(1 / n\right)$ = (1 / C(n  1, m  1)) (m / n) = 1 / C(n, m).
So all msubsets have the probability of 1 / C(n, m) of being generated, the claim holds.

5.4 Probabilistic analysis and further uses of indicator random variables β
5.41
How many people must there be in a room before the probability that someone has the same birthday as you do is at least 1 / 2? How many people must there be before the probability that at least two people have a birthday on July 4 is greater than 1 / 2?

The probability that no people in a room has the same birthday as me is $364^{k  1} / 365^{k  1}$, so the probability that someone has the same birthday as me is $1  364^{k  1} / 365^{k  1}$.
Solving 1  $364^{k  1} / 365^{k  1}$ β₯ 1 / 2, we get k β₯ 254.

The probability that x people in a room has the a birthday on July 4 is C(k, x) $364^{k  x} / 365^k$,
Solving 1  C(k, 0) $364^k / 365^k$  C(k, 1) $364^{k  1} / 365^k$ > 1 / 2, we get k β₯ 613.
5.42
Suppose that we toss balls into b bins until some bin contains two balls. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses?
The probability that toss k balls into b bins to get the first bin containing two balls is: (P(b, k  1) / $b^{k  1}$) ((k  1) / b).
So the expected number of ball tosses is:
$β_{k = 2}^{b + 1} \left(P\left(b, k  1\right) / b^{k  1}\right) \left(\left(k  1\right) / b\right) k$
5.43 β
For the analysis of the birthday paradox, is it important that the birthdays be mutually independent, or is pairwise independence sufficient? Justify your answer.
Skipped.
5.44 β
How many people should be invited to a party in order to make it likely that there are three people with the same birthday?
Skipped.
5.45 β
What is the probability that a kstring over a set of size n forms a kpermutation? How does this question relate to the birthday paradox?
The probability is P(n, k) / $n^k$.
Itβs the same as saying k people whose birthdays are in n days all have different birthday.
5.46 β
Suppose that n balls are tossed into n bins, where each toss is independent and the ball is equally likely to end up in any bin. What is the expected number of empty bins? What is the expected number of bins with exactly one ball?
Let $X_{i}$ being the indicator variable in which bin i have k balls, then
E[$X_{i k}$] = C(n, k) $\left(1 / n\right)^k \left(1  1 / n\right)^{n  k}$.
So the expected number of bins with exactly k balls is
E[$β_{i = 1}^{n} X_{i k}$]
= $β_{i = 1}^{n} \operatorname{E}\left[X_{i k}\right]$
= $β_{i = 1}^{n} C\left(n, k\right) \left(1 / n\right)^k \left(1  1 / n\right)^{n  k}$
= n C(n, k) $\left(1 / n\right)^k \left(1  1 / n\right)^{n  k}$.
So the expected number of bins with exactly 0 ball is:
n C(n, 0) $\left(1 / n\right)^0 \left(1  1 / n\right)^{n  0}$
= n $\left(1  1 / n\right)^n$.
So the expected number of bins with exactly 1 ball is:
n C(n, 1) $\left(1 / n\right)^1 \left(1  1 / n\right)^{n  1}$
= n $\left(1  1 / n\right)^{n  1}$.
5.47 β
Sharpen the lower bound on streak length by showing that in n flips of a fair coin, the probability is less than 1 / n that no streak longer than lg n  2 lg lg n consecutive heads occurs.
Skipped.
5.X Problems
51 Probabilistic counting
With a bbit counter, we can ordinarily only count up to $2^b$  1. With R. Morrisβs probabilistic counting, we can count up to a much larger value at the expense of some loss of precision.
We let a counter value of i represent a count of $n_i$ for i = 0, 1, β¦, $2^b$  1, where the $n_i$ form an increasing sequence of nonnegative values. We assume that the initial value of the counter is 0, representing a count of $n_0$ = 0. The Increment operation works on a counter containing the value i in a probabilistic manner. If i = $2^b$  1, then the operation reports an overflow error. Otherwise, the Increment operation increases the counter by 1 with probability 1 / ($n_{i + 1}  n_i$), and it leaves the counter unchanged with probability 1  1 / ($n_{i + 1}  n_i$).
If we select $n_i$ = i for all i β₯ 0, then the counter is an ordinary one. More interesting situations arise if we select, say, $n_i = 2^{i  1}$ for i > 0 or $n_i = F_i$ (the ith Fibonacci numberβsee Section 3.2).
For this problem, assume that $n_{2^b  1}$ is large enough that the probability of an overflow error is negligible.
 Show that the expected value represented by the counter after n Increment operations have been performed is exactly n.
 The analysis of the variance of the count represented by the counter depends on the sequence of the $n_i$. Let us consider a simple case: $n_i$ = 100 i for all i β₯ 0. Estimate the variance in the value represented by the register after n Increment operations have been performed.

For any counter value $n_i$, the expected value increased by one increment operation is:
$\left(n_{i + 1}  n_i\right) \left(1 / \left(n_{i + 1}  n_i\right)\right) + 0 \left(1 / \left(n_{i + 1}  n_i\right)\right)$ = 1.
Let $X_i$ be the random variable in which the counter values increased by the ith increment operation. So the expected value of the counter after n Increment operations is:
E[$β_{i = 1}^{n} X_i$]
= $β_{i = 1}^{n} \operatorname{E}\left[X_i\right]$
= $β_{i = 1}^{n} 1$.
= n. 
Skipped.
52 Searching an unsorted array
This problem examines three algorithms for searching for a value x in an unsorted array A consisting of n elements.
Consider the following randomized strategy: pick a random index i into A. If A[i] = x, then we terminate; otherwise, we continue the search by picking a new random index into A. We continue picking random indices into A until we find an index j such that A[j] = x or until we have checked every element of A. Note that we pick from the whole set of indices each time, so that we may examine a given element more than once.
a. Write pseudocode for a procedure RandomSearch to implement the strategy above. Be sure that your algorithm terminates when all indices into A have been picked.
b. Suppose that there is exactly one index i such that A[i] = x. What is the expected number of indices into A that we must pick before we find x and RandomSearch terminates?
c. Generalizing your solution to part (b), suppose that there are k β₯ 1 indices i such that A[i] = x. What is the expected number of indices into A that we must pick before we find x and RandomSearch terminates? Your answer should be a function of n and k.
d. Suppose that there are no indices i such that A[i] = x. What is the expected number of indices into A that we must pick before we have checked all elements of A and RandomSearch terminates?
Now consider a deterministic linear search algorithm, which we refer to as DeterministicSearch. Specifically, the algorithm searches A for x in order, considering A[1], A[2], A[3], β¦, A[n] until either it finds A[i] = x or it reaches the end of the array. Assume that all possible permutations of the input array are equally likely.
e. Suppose that there is exactly one index i such that A[i] = x. What is the averagecase running time of DeterministicSearch? What is the worstcase running time of DeterministicSearch?
f. Generalizing your solution to part (e), suppose that there are k β₯ 1 indices i such that A[i] = x. What is the averagecase running time of DeterministicSearch? What is the worstcase running time of DeterministicSearch? Your answer should be a function of n and k.
g. Suppose that there are no indices i such that A[i] = x. What is the averagecase running time of DeterministicSearch? What is the worstcase running time of DeterministicSearch?
Finally, consider a randomized algorithm ScrambleSearch that works by first randomly permuting the input array and then running the deterministic linear search given above on the resulting permuted array.
h. Letting k be the number of indices i such that A[i] = x, give the worstcase and expected running times of ScrambleSearch for the cases in which k = 0 and k = 1. Generalize your solution to handle the case in which k β₯ 1.
i. Which of the three searching algorithms would you use? Explain your answer.
a.
ScrambleSearch(A, v)
 V = an array with A.length False values
 c = 0
 while c < A.length
 Β Β Β Β i = Random(1, n)
 Β Β Β Β if not V[i]
 Β Β Β Β Β Β Β Β if A[i] == v
 Β Β Β Β Β Β Β Β Β Β Β Β return i
 Β Β Β Β Β Β Β Β V[i] = True
 Β Β Β Β Β Β Β Β c = c + 1
 return nil
b. Each pick has the probability of 1 / n of being succeed, so the expected number of indices to pick is n.
c. Each pick has the probability of k / n of being succeed, so the expected number of indices to pick is n / k.
d. It is like the coupon collectorβs problem, the expected number of indices to pick is n(ln n + O(1)).
e. Averagecase running time is Ξ((1 + n) / 2), Worstcase running time is Ξ(n).
f. The expected number of indices to pick is:
$β_{i = 1}^{n  k + 1} i P\left(n  k, i  1\right) k P(n  i, n  i) / P(n, n)$ = (n + 1) / (k + 1). (By WolframAlpha)
Worstcase running time is Ξ(n  k + 1).
g. They are both Ξ(n).
h. The worstcase, expected running time are all Ξ(n).
i. I will use DeterministicSearch, it is superior in every way.
II Sorting and Order Statistics
6 Heapsort
6.1 Heaps
6.11
What are the minimum and maximum numbers of elements in a heap of height h?
The minimum number of elements is $2^h$, the maximum number of elements is $2^{h + 1}  1$.
6.12
Show that an nelement heap has height βlg nβ.
According to exercise 6.11, we know that if the height of a heap is h, the number of elements is in range [$2^h$, $2^{h + 1}  1$]. Also, if $2^h$ β€ n β€ $2^{h + 1}  1$, we must have βlg nβ = h, so an nelement heap must have height βlg nβ.
6.13
Show that in any subtree of a maxheap, the root of the subtree contains the largest value occurring anywhere in that subtree.
Proof by induction:
Base case: if a maxheap has one element, then the only subtree is the oneelement tree, the root contains the largest value, since it is the only value the tree has.
Inductive case: if a maxheap H has more than one element, by induction, we know that for any subtree in the Hβs children, the subtreeβs root contains the largest value in the subtree. So the left child H contains the largest value in the left subtree; and if H have a right child, it must also contain the largest value in the right subtree. Since we have that for every node in the heap, the value of the parent is always greater or equal than its children, we know that the value of the root of H must be always greater or equal than its children. So it must be the largest element in the heap.
6.14
Where in a maxheap might the smallest element reside, assuming that all elements are distinct?
The smallest element must be in the leaf nodes, otherwise the heap property will be violated.
6.15
Is an array that is in sorted order a minheap?
Yes, since the index of a child node must be greater than the corresponding parent node, and the array is in sorted order, we know that the value of the child node must be greater or equal to the corresponding parent node, which satisfies the minheap property.
6.16
Is the array with values β¨23, 17, 14, 6, 13, 10, 1, 5, 7, 12β© a maxheap?
Nope.
6.17
Show that, with the array representation for storing an nelement heap, the leaves are the nodes indexed by βn / 2β + 1, βn / 2β + 2, β¦, n.
The index of the last element is n, so the index of the parent of the last element is βn / 2β, so the leaves are the nodes starts with βn / 2β, and ends with n.
6.2 Maintaining the heap property
6.21
Using Figure 6.2 as a model, illustrate the operation of MaxHeapify(A, 3) on the array A = β¨27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0β©.
Skipped.
6.22
Starting with the procedure MaxHeapify, write pseudocode for the procedure MinHeapify(A, i), which performs the corresponding manipulation on a minheap. How does the running time of MinHeapify compare to that of MaxHeapify?
Solution is implemented here.
The running time of MinHeapify is the same as MaxHeapify.
6.23
What is the effect of calling MaxHeapify(A, i) when the element A[i] is larger than its children?
Nothing happens.
6.24
What is the effect of calling MaxHeapify(A, i) for i > A.heapsize / 2?
Nothing happens.
6.25
The code for MaxHeapify is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MaxHeapify that uses an iterative control construct (a loop) instead of recursion.
The solution is implemented here.
6.26
Show that the worstcase running time of MaxHeapify on a heap of size n is Ξ©(lg n). (Hint: For a heap with n nodes, give node values that cause MaxHeapify to be called recursively at every node on a simple path from the root down to a leaf.)
The height of a heap of size n is βlg nβ, if MaxHeapify is called at every node on a simple path from the root down to a leaf, the expected running time is linear to the height of the heap, that is βlg nβ, so the worstcase running time is Ξ©(lg n).
6.3 Building a heap
6.31
Using Figure 6.3 as a model, illustrate the operation of BuildMaxHeap on the array A = β¨5, 3, 17, 10, 84, 19, 6, 22, 9β©.
Skipped.
6.32
Why do we want the loop index i in line 2 of BuildMaxHeap to decrease from βA.length / 2β to 1 rather than increase from 1 to βA.length / 2β?
Because MaxHeapify requires that its child subtree being a heap, so we have to do this bottomup style.
6.33
Show that there are at most βn / $2^{h + 1}$β nodes of height h in any nelement heap.
Proof by induction:
Base case: the nodes of height 0 are leaf nodes. according to exercise 6.17, we know that the number of leaf nodes is n  (βn / 2β + 1) + 1 = n  βn / 2β = βn / 2β = βn / $2^{0 + 1}$β, since βFor any integer n, βn / 2β + βn / 2β = nβ.
Inductive case: by induction, we know that in height h + 1, there are at most βn / $2^{h + 2}$β nodes. So there are at most ββn / $2^{h + 2}$β / 2β nodes in height h. According to equation (3.4), we have ββn / $2^{h + 2}$β / 2β = βn / $2^{h + 2}$ / 2β = βn / $2^{h + 1}$β.
6.4 The heapsort algorithm
6.41
Using Figure 6.4 as a model, illustrate the operation of Heapsort on the array A = β¨5, 13, 2, 25, 7, 17, 20, 8, 4β©.
Skipped.
6.42
Argue the correctness of Heapsort using the following loop invariant:
At the start of each iteration of the for loop of lines 2β5, the subarray A[1β₯i] is a maxheap containing the i smallest elements of A[1β₯n], and the subarray A[i + 1β₯n] contains the n  i largest elements of A[1β₯n], sorted.
Skipped.
6.43
What is the running time of Heapsort on an array A of length n that is already sorted in increasing order? What about decreasing order?
Both Ξ(n lg n).
6.44
Show that the worstcase running time of Heapsort is Ξ©(n lg n).
Skipped.
6.45 β
Show that when all elements are distinct, the bestcase running time of Heapsort is Ξ©(n lg n).
Skipped.
6.5 Priority queues
6.51
Illustrate the operation of HeapExtractMax on the heap A = β¨15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1β©.
Skipped.
6.52
Illustrate the operation of MaxHeapInsert(A, 10) on the heap A = β¨15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1β©.
Skipped.
6.53
Write pseudocode for the procedures HeapMinimum, HeapExtractMin, HeapDecreaseKey, and MinHeapInsert that implement a minpriority queue with a minheap.
Solution is implemented here.
6.54
Why do we bother setting the key of the inserted node to β in line 2 of MaxHeapInsert when the next thing we do is increase its key to the desired value?
We must ensure that when calling HeapIncreaseKey, the value of key must be equal to or greater than A[i], so we use β to do this.
6.55
Argue the correctness of HeapIncreaseKey using the following loop invariant:
At the start of each iteration of the while loop of lines 4β6, A[Parent(i)] β₯ A[Left(i)] and A[Parent(i)] β₯ A[Right(i)], if these nodes exist, and the subarray A[1β₯A.heapsize] satisfies the maxheap property, except that there may be one violation: A[i] may be larger than A[Parent(i)].
You may assume that the subarray A[1β₯A.heapsize] satisfies the maxheap property at the time HeapIncreaseKey is called.
Skipped.
6.56
Each exchange operation on line 5 of HeapIncreaseKey typically requires three assignments. Show how to use the idea of the inner loop of InsertionSort to reduce the three assignments down to just one assignment.
Solution is implemented here.
6.57
Show how to implement a firstin, firstout queue with a priority queue. Show how to implement a stack with a priority queue. (Queues and stacks are defined in Section 10.1.)
Solution is implemented here.
6.58
The operation HeapDelete(A, i) deletes the item in node i from heap A. Give an implementation of HeapDelete that runs in O(lg n) time for an nelement maxheap.
Solution is implemented here.
6.59
Give an O(n lg k)time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a minheap for kway merging.)
Solution is implemented here.
6.X Problems
61 Building a heap using insertion
We can build a heap by repeatedly calling MaxHeapInsert to insert the elements into the heap. Consider the following variation on the BuildMaxHeap procedure:
BuildMaxHeapβ²(A)
 A.heapsize = 1
 for i = 2 to A.length
 Β Β Β Β BuildMaxHeapβ²(A, A[i])
a. Do the procedures BuildMaxHeap and BuildMaxHeapβ² always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.
b. Show that in the worst case, BuildMaxHeapβ² requires Ξ(n lg n) time to build an nelement heap.
a. No. For array β¨0, 1, 2, 3β©, BuildMaxHeap produces β¨3, 1, 2, 0β©, while BuildMaxHeapβ² produces β¨3, 2, 1, 0β©.
b. If A is in increasing order, every insertion will have to travel all the way from leaf to root, which has the run time of Ξ(n lg n).
62 Analysis of dary heaps
A dary heap is like a binary heap, but (with one possible exception) nonleaf nodes have d children instead of 2 children.
a. How would you represent a dary heap in an array?
b. What is the height of a dary heap of n elements in terms of n and d?
c. Give an efficient implementation of ExtractMax in a dary maxheap. Analyze its running time in terms of d and n.
d. Give an efficient implementation of Insert in a dary maxheap. Analyze its running time in terms of d and n.
e. Give an efficient implementation of IncreaseKey(A, i, k), which flags an error if k < A[i], but otherwise sets A[i] = k and then updates the dary maxheap structure appropriately. Analyze its running time in terms of d and n.
a. The solution is implemented here.
b. The maximum number of elements of height h is $β_{i = 0}^{h} d^h = \frac{1  d^h}{1  d}$, so we have $\frac{1  d^{h  1}}{1  d} < n β€ \frac{1  d^h}{1  d}$. Solving it, we have $\log_d\left(\left(d  1\right) n + 1\right) β€ h < \log_d\left(\left(d  1\right) n + 1\right) + 1$. Since h is an integer, we have h = $\left\lceil\log_d\left(\left(d  1\right) n + 1\right)\right\rceil$ = Ξ($\log_d n$).
c. The solution is implemented here. The worstcase running time is linear to the height of the heap, and on every level we have to find the maximum element in Ξ(d) time. So the worst case running time is Ξ(d $\log_d n$).
d. The solution is implemented here. The worstcase running time is linear to the height of the heap. So the worst case running time is O($\log_d n$).
e. The solution is implemented here. The worst case running time is Ξ($\log_d n$).
63 Young tableaus
An m Γ n Young tableau is an m Γ n matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be β, which we treat as nonexistent elements. Thus, a Young tableau can be used to hold r β€ m n finite numbers.
a. Draw a 4 Γ 4 Young tableau containing the elements {9, 16, 3, 2, 4, 8, 5, 14, 12}.
b. Argue that an m Γ n Young tableau Y is empty if Y[1, 1] = β. Argue that Y is full (contains m n elements) if Y[m, n] < β.
c. Give an algorithm to implement ExtractMin on a nonempty m Γ n Young tableau that runs in O(m + n) time. Your algorithm should use a recursive subroutine that solves an m Γ n problem by recursively solving either an (m  1) Γ n or an m Γ (n  1) subproblem. (Hint: Think about MaxHeapify.) Define T(p), where p = m + n, to be the maximum running time of ExtractMin on any m Γ n Young tableau. Give and solve a recurrence for T(p) that yields the O(m + n) time bound.
d. Show how to insert a new element into a nonfull m Γ n Young tableau in O(m + n) time.
e. Using no other sorting method as a subroutine, show how to use an n Γ n Young tableau to sort $n^2$ numbers in O($n^3$) time.
f. Give an O(m + n)time algorithm to determine whether a given number is stored in a given m Γ n Young tableau.
a.
2  3  4  5 
8  9  12  14 
16  β  β  β 
β  β  β  β 
b.
 Since Y[1, 1] = β, the first row will only contain β, which means that the first element of every column is β, which means every column will only contain β, which means the table will only contain β, which means Y is empty.
 Since Y[m, n] < β, the last row will not contain β, which means that the last element of every column is not β, which means every column will not contain β, which means the table will not contain β, which means Y full.
c.
Solution is implemented here.
T(p) = T(p  1) + O(1).
d.
Solution is implemented here.
The solution is very similar to the ExtractMin and they have the same running time bound.
e.
Solution is implemented here.
f.
You are thinking about binary search, arenβt you? Too bad this problem isnβt about that.
Solution is implemented here.
7 Quicksort
7.1 Description of quicksort
7.11
Using Figure 7.1 as a model, illustrate the operation of Partition on the array A = β¨13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11β©.
Skipped.
7.12
What value of q does Partition return when all elements in the array A[pβ₯r] have the same value? Modify Partition so that q = β(p + r) / 2β when all elements in the array A[pβ₯r] have the same value.
 Partition returns r when all elements have the same value.
 Solution is implemented here.
7.13
Give a brief argument that the running time of Partition on a subarray of size n is Ξ(n).
There is only one loop that updates j from p to r  1, and the loop body requires constant time to run, so the running time is Ξ(r  p) = Ξ(n  1) = Ξ(n).
7.14
How would you modify Quicksort to sort into nonincreasing order?
Do you mean that I canβt modify Partition?
Fine, the solution is implemented here.
7.2 Performance of quicksort
7.21
Use the substitution method to prove that the recurrence T(n) = T(n  1) + Ξ(n) has the solution T(n) = Ξ($n^2$), as claimed at the beginning of Section 7.2.
Let T(n) = T(n  1) + f(n), where for some $c_1$, $c_2$ and $n_0$, for any n > $n_0$, $c_1 n β€ f\left(n\right) β€ c_2 n$.
Suppose T(n) β₯ $\left(c_1 / 2\right) n^2 + \left(c_1 / 2\right) n + c_3$ for large enough n, we have
T(n)
= T(n  1) + f(n)
β₯ T(n  1) + $c_1$ n
β₯ $\left(c_1 / 2\right) \left(n  1\right)^2 + \left(c_1 / 2\right) \left(n  1\right) + c_3 + c_1 n$
= $\left(c_1 / 2\right) n^2  c_1 n + c_1 / 2 + \left(c_1 / 2\right) \left(n  1\right) + c_3 + c_1 n$
= $\left(c_1 / 2\right) n^2 + \left(c_1 / 2\right) n + c_3$.
So T(n) = Ξ©($n^2$). Similarly, we can prove T(n) = O($n^2$), so T(n) = Ξ(n).
7.22
What is the running time of Quicksort when all elements of array A have the same value?
Ξ($n^2$).
7.23
Show that the running time of Quicksort is Ξ($n^2$) when the array A contains distinct elements and is sorted in decreasing order.
Letβs say we have an array β¨n, n  1, β¦, 2, 1β© to sort.
At the first partition, we will choose 1 as the pivot element. so after partition, we get two arrays: β¨β© and β¨n  1, n  2, β¦, 2, nβ©. This is the worst case scenario.
At the second partition, we will choose n as the pivot element. so after partition, we get two arrays: β¨n  1, n  2, β¦, 2β© and β¨β©. This is the worst case scenario.
Notice that after the second partition, the subarray β¨n  1, n  2, β¦, 2β© is in decreasing order, so we get ourselves a subproblem of the original problem. Since the first two partitions of the partition is the worst cast scenario, we know that the subproblem will also be the worst case scenario. So the running time is Ξ($n^2$).
7.24
Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants usually cash them with reasonable dispatch. The problem of converting timeoftransaction ordering to checknumber ordering is therefore the problem of sorting almostsorted input. Argue that the procedure InsertionSort would tend to beat the procedure Quicksort on this problem.
According to problem 24, the InsertionSort algorithm has the running time of Ξ(k), where k is the inversions of the array. An almost sorted array as a few number of inversions, so the expected running time of InsertionSort should be low, while the Quicksort algorithm requires at Ξ©(n lg n) time. So InsertionSort would tend to beat the procedure Quicksort on this problem.
7.25
Suppose that the splits at every level of quicksort are in the proportion 1  Ξ± to Ξ±, where 0 < Ξ± β€ 1 / 2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately lg n / lg Ξ± and the maximum depth is approximately lg n / lg(1  Ξ±). (Donβt worry about integer roundoff.)
At each level of recursion the problem of size n is divided into problems of size Ξ± n and size (1  Ξ±) n. Since Ξ± β€ 1 / 2, the minimum depth is on the path n β Ξ± n β $Ξ±^2$ n β β― β 1, the maximum depth is on the path n β (1  Ξ±) n β $\left(1  Ξ±\right)^2$ n β β― β 1.
Solving $Ξ±^i$ n = 1 for i, we get i = lg n / lg Ξ±.
Solving $\left(1  Ξ±\right)^i$ n = 1 for i, we get i = lg n / lg (1  Ξ±).
7.26 β
Argue that for any constant 0 < Ξ± β€ 1 / 2, the probability is approximately 1  2 Ξ± that on a random input array, Partition produces a split more balanced than 1  Ξ± to Ξ±.
Let n be the size of the array. Being more balanced than 1  Ξ± to Ξ± means that the number of elements is greater than or equal to A[n] is greater than a n and less than (1  a) n, which means A[n] must be greater than the (a n)th smallest element and less than the ((1  a) n)th biggest element. There are (1  a) n  a n = (1  2 a) n different cases to choose. So the probability is (1  2 a) n / n = 1  2 a.
7.3 A randomized version of quicksort
7.31
Why do we analyze the expected running time of a randomized algorithm and not its worstcase running time?
The worstcase running time doesnβt change if we randomize the algorithm, since we might generate the very same worst case by chance.
7.32
When RandomizedQuicksort runs, how many calls are made to the randomnumber generator Random in the worst case? How about in the best case? Give your answer in terms of Ξnotation.
 Best case: T(n) = 2 T((n  1) / 2) + 1 β T(n) = Ξ(n).
 Worst case: T(n) = T(n  1) + 1 β T(n) = Ξ(n).
7.4 Analysis of quicksort
7.41
Show that in the recurrence
T(n) = $\underset{0 β€ q β€ n  1}{\max} \left(T\left(q\right) + T\left(n  q  1\right)\right) + Ξ\left(n\right)$,
T(n) = Ξ©($n^2$).
Suppose T(n) β₯ c $n^2$ for some c, we have:
T(n)
= $\underset{0 β€ q β€ n  1}{\max} \left(T(q) + T(n  q  1)\right) + Ξ\left(n\right)$
β₯ $\underset{0 β€ q β€ n  1}{\max} \left(c q^2 + c \left(n  q  1\right)^2\right)$ + Ξ(n)
= c β
$\underset{0 β€ q β€ n  1}{\max} \left(q^2 + \left(n  q  1\right)^2\right)$ + Ξ(n)
= c β
$\left(n  1\right)^2$ + Ξ(n)
= c $n^2$  c (2 n  1) + Ξ(n)
β₯ c $n^2$.
7.42
Show that quicksortβs bestcase running time is Ξ©(n lg n).
The best case running time is:
T(n) = 2 T((n  1) / 2) + Ξ(n).
Suppose T(n) β₯ c (n + 1) lg (n + 1) for some c, we have:
T(n)
= 2 T((n  1) / 2) + Ξ(n)
β₯ 2 c ((n  1) / 2 + 1) lg ((n  1) / 2 + 1) + Ξ(n)
= 2 c ((n + 1) / 2) lg ((n + 1) / 2) + Ξ(n)
= c (n + 1) (lg (n + 1)  1) + Ξ(n)
= c (n + 1) lg (n + 1)  c (n + 1) + Ξ(n)
β₯ c (n + 1) lg (n + 1).
7.43
Show that the expression $q^2 + \left(n  q  1\right)^2$ achieves a maximum over q = 0, 1, β¦, n  1 when q = 0 or q = n  1.
$\frac{\partial\left(q^2 + \left(n  q  1\right)^2\right)}{\partial q}$
= 2 q  2 (n  q  1)
= 4 q  2 n + 2
When q < (n  1) / 2, 4 q  2 n + 2 > 0; when q > (n  1) / 2, 4 q  2 n + 2 < 0, so we have the value of $q^2 + \left(n  q  1\right)^2$ decreasing when q < (n  1) / 2, and increasing when q > (n  1) / 2. Since 0 β€ q β€ n  1, we have maximum when q = 0 or q = n  1.
7.44
Show that RandomizedQuicksortβs expected running time is Ξ©(n lg n).
Skipped.
7.45
We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is βnearlyβ sorted. Upon calling quicksort on a subarray with fewer than k elements, let it simply return without sorting the subarray. After the toplevel call to quicksort returns, run insertion sort on the entire array to finish the sorting process. Argue that this sorting algorithm runs in O(n k + n lg (n / k)) expected time. How should we pick k, both in theory and in practice?
Skipped.
7.46 β
Consider modifying the Partition procedure by randomly picking three elements from array A and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst an Ξ±to(1  Ξ±) split, as a function of Ξ± in the range 0 < Ξ± < 1.
Skipped.
7.X Problems
71 Hoare partition correctness
The version of Partition given in this chapter is not the original partitioning algorithm. Here is the original partition algorithm, which is due to C. A. R. Hoare:
HoarePartition(A, p, r)
 x = A[p]
 i = p  1
 j = r + 1
 while True
 Β Β Β Β repeat
 Β Β Β Β Β Β Β Β j = j  1
 Β Β Β Β until A[j] β€ x
 Β Β Β Β repeat
 Β Β Β Β Β Β Β Β i = i + 1
 Β Β Β Β until A[i] β₯ x
 Β Β Β Β if i < j
 Β Β Β Β Β Β Β Β exchange A[i] with A[j]
 Β Β Β Β else return j
a. Demonstrate the operation of HoarePartition on the array A = β¨13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21β©, showing the values of the array and auxiliary values after each iteration of the while loop in lines 4β13.
The next three questions ask you to give a careful argument that the procedure HoarePartition is correct. Assuming that the subarray A[pβ₯r] contains at least two elements, prove the following:
b. The indices i and j are such that we never access an element of A outside the subarray A[pβ₯r].
c. When HoarePartition terminates, it returns a value j such that p β€ j < r.
d. Every element of A[pβ₯j] is less than or equal to every element of A[j + 1β₯r] when HoarePartition terminates.
The Partition procedure in Section 7.1 separates the pivot value (originally in A[r]) from the two partitions it forms. The HoarePartition procedure, on the other hand, always places the pivot value (originally in A[p]) into one of the two partitions A[pβ₯j] and A[j + 1β₯r]. Since p β€ j < r, this split is always nontrivial.
e. Rewrite the Quicksort procedure to use HoarePartition.
a.
Skipped.
b.
At the first iteration of the outer loop, the algorithm first find the first element from right that is less than or equal to x, and the index element wonβt be less than p since A[p] = x. Then the program find the first element that is greater or equal than x, which will have the index of p. If the algorithm doesnβt terminate, the rest of the first element is just swapping element A[i] and A[j]. So the first iteration wonβt access outside the subarray A[pβ₯r].
After the first iteration, the following loop invariant will hold for each outer loop iteration:
 At the beginning of each iteration, i < j, and A[i] β€ x, A[j] β₯ x.
 In the body of each iteration, i will be less than or equal to the initial value of j, and j will be more than or equal to the initial value of i.
Proof by induction:

Base case: If the first iteration doesnβt terminate, A[i] will be equal to some value that is less than or equal to x, and A[j] will be equal to x, so the loop invariant holds for the second iteration of the outer loop.

Inductive case: For the nth iteration, where n > 1, by induction, we know that at the beginning, i < j, and A[i] β€ x, A[j] β₯ x. Let m, n be the values of i, j at the beginning of this iteration, we know at line 11:
 i β€ n,
 j β₯ m,
 A[i] β₯ x,
 A[j] β€ x.
If i < j at line 11, after swapping A[i] and A[j]. we have A[i] β€ x, and A[j] β₯ x. Now the (n + 1)th iteration begins, the loop invariant still holds.
If i β₯ j at line 11, the algorithm terminates, so the loop invariant still holds.
c.
Since A[pβ₯r] contains at least two elements, we know that p < r.
First, we prove that the returned j is less than r:
At the beginning of the first iteration, i = p  1, and j = r + 1. Notice that line 6 and line 9 will be executed at least once, also, we have A[p] = x, so we know i must equal to p in line 11. If line 6 is executed only once, j will equal to p at line 11. Since p < r, we know i < j, so the second iteration of the outer loop will be executed, which will cause j being decremented to a value that is less than r. If line 6 is executed more than once, j is still decremented to a value that is less than r.
Then, we prove that the returned j is greater than or equal to i:
If the loop terminates at the first iteration, i will be equal to p, otherwise the second iteration will be executed, which will cause i being incremented to a value that is more than p.
d.
The outer loop has the following loop invariant:
 At the beginning of each iteration, elements in A[pβ₯i] is less than or equal to x, and elements in A[jβ₯r] is greater than or equal to x.
Proof by induction:

Base case: In the beginning of the first iteration, both A[pβ₯i] and A[jβ₯r] is empty, so the claim holds.

Inductive case: In each iteration of the outer loop, Let m, n be the initial values of i, j. In the loop body, we find the fist element from the right that is less than or equal to x, and the first element from the left that is greater than or equal to x, then swap them. After swapping, we know that every element in A[m + 1β₯i] is less than or equal to x, and every element in A[j + 1β₯n] is greater than or equal to x. By induction, we know that A[pβ₯m] is less than or equal to x, and A[nβ₯r] is greater than or equal to x. So elements in A[pβ₯i] is less than or equal to x, and elements in A[jβ₯r] is greater than or equal to x at the beginning of next iteration.
If the algorithm terminates, at line 11, we have i β₯ j, and elements in A[pβ₯i  1] is less than or equal to x, and elements in A[j + 1β₯r] is greater than or equal to x. So there are two cases:
βββββββ¬ββββββ¬ββββββ¬ββββββ¬ββββββ β p β β¦ β i j β β¦ β r β βββββββΌββββββΌββββββΌββββββΌββββββ€ β β€ x β β€ x β = x β β₯ x β β₯ x β βββββββ΄ββββββ΄ββββββ΄ββββββ΄ββββββ βββββββ¬ββββββ¬ββββββ¬ββββββ¬ββββββ¬ββββββ β p β β¦ β j β i β β¦ β r β βββββββΌββββββΌββββββΌββββββΌββββββΌββββββ€ β β€ x β β€ x β β€ x β β₯ x β β₯ x β β₯ x β βββββββ΄ββββββ΄ββββββ΄ββββββ΄ββββββ΄ββββββ
In both cases, elements in A[pβ₯j] is less than or equal to x, and elements in A[j + 1β₯r] is greater than or equal to x.
e.
Solution is implemented here.
72 Quicksort with equal element values
The analysis of the expected running time of randomized quicksort in Section 7.4.2 assumes that all element values are distinct. In this problem, we examine what happens when they are not.
a. Suppose that all element values are equal. What would be randomized quicksortβs running time in this case?
b. The Partition procedure returns an index q such that each element of A[pβ₯q  1] is less than or equal to A[q] and each element of A[q + 1β₯r] is greater than A[q]. Modify the Partition procedure to produce a procedure Partitionβ²(A, p, r), which permutes the elements of A[pβ₯r] and returns two indices q and t, where p β€ q β€ t β€ r, such that
 all elements of A[qβ₯t] are equal,
 each element of A[pβ₯q  1] is less than A[q], and
 each element of A[t + 1β₯r] is greater than A[q].
Like Partition, your Partitionβ² procedure should take Ξ(r  p) time.
c. Modify the RandomizedPartition procedure to call Partitionβ², and name the new procedure RandomizedQuicksortβ². Then modify the Quicksort procedure to produce a procedure Quicksortβ²(A, p, r) that calls RandomizedPartitionβ² and recurses only on partitions of elements not known to be equal to each other.
d. Using Quicksortβ², how would you adjust the analysis in Section 7.4.2 to avoid the assumption that all elements are distinct?
a.
Ξ($n^2$).
b.
Solution is implemented here.
c.
Solution is implemented here.
d.
Skipped.
73 Alternative quicksort analysis
An alternative analysis of the running time of randomized quicksort focuses on the expected running time of each individual recursive call to RandomizedQuicksort, rather than on the number of comparisons performed.
a. Argue that, given an array of size n, the probability that any particular element is chosen as the pivot is 1 / n. Use this to define indicator random variables $X_i$ = I{ith smallest element is chosen as the pivot}. What is E[$X_i$]?
b. Let T(n) be a random variable denoting the running time of quicksort on an array of size n. Argue that
 E[T(n)] = E$\displaystyle\left[β_{q = 1}^n X_q \left(T\left(q  1\right) + T\left(n  q\right) + Ξ\left(n\right)\right)\right]$. (7.5)
c. Show that we can rewrite equation (7.5) as
 E[T(n)] = $\displaystyle\frac{2}{n} β_{q = 2}^{n  1} \operatorname{E}\left[T\left(q\right)\right] + Ξ\left(n\right)$. (7.6)
d. Show that
 $\displaystyle β_{k = 2}^{n  1} k \lg k β€ \frac{1}{2} n^2 \lg n  \frac{1}{8} n^2$. (7.7)
(Hint: Split the summation into two parts, one for k = 2, 3, β¦, βn / 2β  1 and one for k = βn / 2β, β¦, n  1.)
e. Using the bound from equation (7.7), show that the recurrence in equation (7.6) has the solution E[T(n)] = Ξ(n lg n). (Hint: Show, by substitution, that E[T(n)] β€ a n lg n for sufficiently large n and for some positive constant a.)
Skipped.
74 Stack depth for quicksort
The Quicksort algorithm of Section 7.1 contains two recursive calls to itself. After Quicksort calls Partition, it recursively sorts the left subarray and then it recursively sorts the right subarray. The second recursive call in Quicksort is not really necessary; we can avoid it by using an iterative control structure. This technique, called tail recursion, is provided automatically by good compilers. Consider the following version of quicksort, which simulates tail recursion:
TailRecursiveQuicksort(A, p, r)
 while p < r
 Β Β Β Β // Partition and sort left subarray.
 Β Β Β Β q = Partition(A, p, r)
 Β Β Β Β TailRecursiveQuicksort(A, p, q  1)
 Β Β Β Β p = q + 1
a. Argue that TailRecursiveQuicksort(A, 1, A.length) correctly sorts the array A.
Compilers usually execute recursive procedures by using a stack that contains pertinent information, including the parameter values, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. Upon calling a procedure, its information is pushed onto the stack; when it terminates, its information is popped. Since we assume that array parameters are represented by pointers, the information for each procedure call on the stack requires O(1) stack space. The stack depth is the maximum amount of stack space used at any time during a computation.
b. Describe a scenario in which TailRecursiveQuicksortβs stack depth is Ξ(n) on an nelement input array.
c. Modify the code for TailRecursiveQuicksort so that the worstcase stack depth is Ξ(lg n). Maintain the O(n lg n) expected running time of the algorithm.
a.
The loop has the following invariant:
 Let m be the initial value of p. At the beginning of each iteration of the loop, A[mβ₯p  1] is in sorted order, and no elements in A[mβ₯p  1] is more than A[p].
Proof by induction:

Base case: At the beginning of the first iteration, p = m, so A[mβ₯p  1] is empty, the invariant holds.

Inductive case: At the beginning of the nth iteration, where n β₯ 1, by induction, we know that A[mβ₯p  1] is in sorted order, and no elements in A[mβ₯p  1] is more than A[p].
After calling Partition in line 3, we know that elements in A[pβ₯q  1] is less than or equal to A[q], and elements in A[q + 1β₯r] is greater than A[q].
After calling TailRecursiveQuicksort in line 4, we know that A[pβ₯q  1] are in sorted order. Since no elements in A[mβ₯p  1] is more than A[p], A[mβ₯q] is in sorted order. After setting p = q + 1 in line 5, the next iteration begins, so the invariant still holds.
When the loop terminates, according to the loop invariant, we know that subarray A[pβ₯r] will be in sorted order.
b.
When the array is in increasing order.
c.
Solution is implemented here.
75 Medianof3 partition
One way to improve the RandomizedQuicksort procedure is to partition around a pivot that is chosen more carefully than by picking a random element from the subarray. One common approach is the medianof3 method: choose the pivot as the median (middle element) of a set of 3 elements randomly selected from the subarray. (See Exercise 7.46.) For this problem, let us assume that the elements in the input array A[1β₯n] are distinct and that n β₯ 3. We denote the sorted output array by Aβ²[1β₯n]. Using the medianof3 method to choose the pivot element x, define $p_i$ = Pr{x = Aβ²[i]}.
a. Give an exact formula for $p_i$ as a function of n and i for i = 2, 3, β¦, n  1. (Note that $p_1 = p_n = 0$.)
b. By what amount have we increased the likelihood of choosing the pivot as x = Aβ²[β(n + 1) / 2β], the median of A[1β₯n], compared with the ordinary implementation? Assume that n β β, and give the limiting ratio of these probabilities.
c. If we define a βgoodβ split to mean choosing the pivot as x = Aβ²[i], where n / 3 β€ i β€ 2 n / 3, by what amount have we increased the likelihood of getting a good split compared with the ordinary implementation? (Hint: Approximate the sum by an integral.)
d. Argue that in the Ξ©(n lg n) running time of quicksort, the medianof3 method affects only the constant factor.
Skipped.
The medianof3 quicksort is implemented here.
76 Fuzzy sorting of intervals
Consider a sorting problem in which we do not know the numbers exactly. Instead, for each number, we know an interval on the real line to which it belongs. That is, we are given n closed intervals of the form [$a_i$, $b_i$], where $a_i$ β€ $b_i$. We wish to fuzzysort these intervals, i.e., to produce a permutation β¨$i_1$, $i_2$, β¦, $i_n$β© of the intervals such that for j = 1, 2, β¦, n, there exist $c_j$ β [$a_{i_j}$, $a_{i_j}$] satisfying $c_1$ β€ $c_2$ β€ β― β€ $c_n$.
a. Design a randomized algorithm for fuzzysorting n intervals. Your algorithm should have the general structure of an algorithm that quicksorts the left endpoints (the $a_i$ values), but it should take advantage of overlapping intervals to improve the running time. (As the intervals overlap more and more, the problem of fuzzysorting the intervals becomes progressively easier. Your algorithm should take advantage of such overlapping, to the extent that it exists.)
b. Argue that your algorithm runs in expected time Ξ(n lg n) in general, but runs in expected time Ξ(n) when all of the intervals overlap (i.e., when there exists a value x such that x β [$a_i$, $b_i$] for all i). Your algorithm should not be checking for this case explicitly; rather, its performance should naturally improve as the amount of overlap increases.
a. Solution is implemented here.
b. Skipped.
8 Sorting in Linear Time
8.1 Lower bounds for sorting
8.11
What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
n  1.
Because for any element in the array to be sorted, it should be compared at lease once, otherwise we couldnβt determine its position in the sorted array. So if we must compare every element at least once, we need at least n  1 comparisons.
8.12
Obtain asymptotically tight bounds on lg(n!) without using Stirlingβs approximation. Instead, evaluate the summation $β_{k = 1}^{n} \lg k$ using techniques from Section A.2.
Skipped.
8.13
Show that there is no comparison sort whose running time is linear for at least half of the n! inputs of length n. What about a fraction of 1 / n of the inputs of length n? What about a fraction 1 / $2^n$?
Skipped.
8.14
Suppose that you are given a sequence of n elements to sort. The input sequence consists of n / k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n / k subsequences. Show an Ξ©(n lg k) lower bound on the number of comparisons needed to solve this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
Skipped.
8.2 Counting sort
8.21
Using Figure 8.2 as a model, illustrate the operation of CountingSort on the array A = β¨6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2β©.
Skipped.
8.22
Prove that CountingSort is stable.
The key is the reverse iterating of line 10.
For all elements in A that equals to k, the last one will be put at the position C[k], and then C[k] will be decremented by one, so the second last element will be put before the last element and so on. So the relative order of equal elements is kept, which means the algorithm is stable.
8.23
Suppose that we were to rewrite the for loop header in line 10 of the CountingSort as
10 for j = 1 to A.length
Show that the algorithm still works properly. Is the modified algorithm stable?
It is the same as the original algorithm except that the order of the elements with the same value is reversed. The modified algorithm is not stable.
The algorithm is implemented here.
8.24
Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range [aβ₯b] in O(1) time. Your algorithm should use Ξ(n + k) preprocessing time.
Solution is implemented here.
8.3 Radix sort
8.31
Using Figure 8.3 as a model, illustrate the operation of RadixSort on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, $T_A$B, BAR, EAR, $T_A$R, DIG, BIG, TEA, NOW, FOX.
Skipped.
8.32
Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any comparison sort stable. How much additional time and space does your scheme entail?

Insertion sort and merge sort are stable.

First, convert each element A[i] to the tuple (A[i], i), then sort the converted array. When comparing two tuples, first compare the first element. If they equal to each other, compare the second element.
Both additional time and additional space are Ξ(n).
The algorithm is implemented here.
8.33
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
The loop invariant:
 After the ith iteration, array A is sorted on the i lowestorder digits.
Proof by induction:
 Base case: After the first iteration, array A is being sorted on the first digit of its elements, so the array is sorted on the lowestorder digit.
 Indictive case: At the (i + 1)th iteration, the array is being sorted on the (i + 1)th lowestorder digit with a stable sort, which means the elements with the same (i + 1)th lowestorder digit will be grouped together in a sorted order; also, because the sort is stable, the relative order of the elements in any group is kept. By induction, we know that after the ith iteration, array A is sorted on the i lowestorder digits, so the elements in each group is sorted, which means the whole array is sorted on the (i + 1) lowestorder digits.
8.34
Show how to sort n integers in the range 0 to $n^3$  1 in O(n) time.
Represent the integers with lg n bit digits, then the running time will be:
Ξ(d / r (n + $2^r$))
=Ξ(lg $n^3$ / lg n (n + $2^{\lg n}$))
= Ξ(6 n)
= O(n).
8.35 β
In the first cardsorting algorithm in this section, exactly how many sorting passes are needed to sort ddigit decimal numbers in the worst case? How many piles of cards would an operator need to keep track of in the worst case?
 $β_{i = 0}^{d  1} 10^i$ = ($10^d  1$) / 9.
 9 d.
8.4 Bucket sort
8.41
Using Figure 8.4 as a model, illustrate the operation of BucketSort on the array A = β¨.79, .13, .16, .64, .39, .20, .89, .53, .71, .42β©.
Skipped.
8.42
Explain why the worstcase running time for bucket sort is Ξ($n^2$). What simple change to the algorithm preserves its linear averagecase running time and makes its worstcase running time O(n lg n)?
 If all elements are put into one single bucket, the running time become Ξ($n^2$).
 Use merge sort instead of insertion sort to sort elements in buckets.
8.43
Let X be a random variable that is equal to the number of heads in two flips of a fair coin. What is E[$X^2$]? What is $\operatorname{E}^2\left[X\right]$?
E[$X^2$]
= $0^2$ Γ 1 / 4 + $1^2$ Γ 1 / 2 + $2^2$ Γ 1 / 4
= 3 / 2.
$\operatorname{E}^2\left[X\right]$
= $\left(0 Γ 1 / 4 + 1 Γ 1 / 2 + 2 Γ 1 / 4\right)^2$
= 1.
8.44 β
We are given n points in the unit circle, $p_i$ = ($x_i$, $y_i$), such that 0 < $x_i^2 + y_i^2$ β€ 1 for i = 1, 2, β¦, n. Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the area of that region. Design an algorithm with an averagecase running time of Ξ(n) to sort the n points by their distances $d_i = \sqrt{x_i^2 + y_i^2}$ from the origin. (Hint: Design the bucket sizes in BucketSort to reflect the uniform distribution of the points in the unit circle.)
Question: why canβt $x_i^2 + y_i^2$ be zero?
Since the probability is proportional to the area, and the whole area is Ο, the we construct circles with area Ο / n, 2 Ο / n, β¦, (n  1) Ο / n, Ο, and use their boundaries as the bucket boundaries, that is we construct buckets with boundaries of $\sqrt{1 / n}$, $\sqrt{2 / n}$, β¦, $\sqrt{\left(n  1\right) / n}$, 1.
To implement the algorithm, we need to put point (x, y), in bucket βn ($x^2 + y^2$)β  1.
The solution is implemented here.
8.45 β
A probability distribution function P(x) for a random variable X is defined by P(x) = Pr{X β€ x}. Suppose that we draw a list of n random variables $X_1$, $X_2$, β¦, $X_n$ from a continuous probability distribution function P that is computable in O(1) time. Give an algorithm that sorts these numbers in linear averagecase time.
Using bucket sort by putting X into the bucket βn P(X)β  1.
Proof: the probability of X going into bucket i is:
Pr{βn P(X)β  1 = i}
= Pr{βn P(X)β = i + 1}
= Pr{i < n P(X) β€ i + 1}
= Pr{i / n < P(X) β€ (i + 1) / n}
= Pr{P(X) β€ (i + 1) / n}  Pr{P(X) β€ i / n}.
Since
Pr{P(X) β€ t}
= Pr{X β€ $P^{1}\left(t\right)$}
= $P\left(P^{1}\left(t\right)\right)$
= t,
Pr{P(X) β€ (i + 1) / n}  Pr{P(X) β€ i / n}
= (i + 1) / n  i / n
= 1 / n.
So the probability of X going into bucket i is 1 / n.
The solution is implemented here.
8.X Problems
81 Probabilistic lower bounds on comparison sorting
In this problem, we prove a probabilistic Ξ©(n lg n) lower bound on the running time of any deterministic or randomized comparison sort on n distinct input elements. We begin by examining a deterministic comparison sort A with decision tree $T_A$. We assume that every permutation of Aβs inputs is equally likely.
a. Suppose that each leaf of $T_A$ is labeled with the probability that it is reached given a random input. Prove that exactly n! leaves are labeled 1 / n! and that the rest are labeled 0.
b. Let D(T) denote the external path length of a decision tree T; that is, D(T) is the sum of the depths of all the leaves of T. Let T be a decision tree with k > 1 leaves, and let LT and RT be the left and right subtrees of T. Show that D(T) = D(LT) + D(RT) + k.
c. Let d(k) be the minimum value of D(T) over all decision trees T with k > 1 leaves. Show that d(k) = $\min_{1 β€ i β€ k  1} \left\lbrace d(i) + d(k  i) + k\right\rbrace$. (Hint: Consider a decision tree T with k leaves that achieves the minimum. Let $i_0$ be the number of leaves in LT and k  $i_0$ the number of leaves in RT.)
d. Prove that for a given value of k > 1 and i in the range 1 β€ i β€ k  1, the function i lg i + (k  i) lg(k  i) is minimized at i = k / 2. Conclude that d(k) = Ξ©(k lg k).
e. Prove that D($T_A$) = Ξ©(n! lg(n!)), and conclude that the averagecase time to sort n elements is Ξ©(n lg n).
Now, consider a randomized comparison sort B. We can extend the decisiontree model to handle randomization by incorporating two kinds of nodes: ordinary comparison nodes and βrandomizationβ nodes. A randomization node models a random choice of the form Random(1, r) made by algorithm B; the node has r children, each of which is equally likely to be chosen during an execution of the algorithm.
f. Show that for any randomized comparison sort B, there exists a deterministic comparison sort A whose expected number of comparisons is no more than those made by B.
Skipped.
82 Sorting in place in linear time
Suppose that we have an array of n data records to sort and that the key of each record has the value 0 or 1. An algorithm for sorting such a set of records might possess some subset of the following three desirable characteristics:
 The algorithm runs in O(n) time.
 The algorithm is stable.
 The algorithm sorts in place, using no more than a constant amount of storage space in addition to the original array.
a. Give an algorithm that satisfies criteria 1 and 2 above.
b. Give an algorithm that satisfies criteria 1 and 3 above.
c. Give an algorithm that satisfies criteria 2 and 3 above.
d. Can you use any of your sorting algorithms from parts (a)β(c) as the sorting method used in line 2 of RadixSort, so that RadixSort sorts n records with bbit keys in O(b n) time? Explain how or why not.
e. Suppose that the n records have keys in the range from 1 to k. Show how to modify counting sort so that it sorts the records in place in O(n + k) time. You may use O(k) storage outside the input array. Is your algorithm stable? (Hint: How would you do it for k = 3?)
a. Counting sort.
b. The Partition procedure used in quicksort, and use 0 as pivot.
c. Insertion sort.
d.
 (a) Counting sort: No. Because it requires Ξ©($2^b$) running time.
 (b) Partition: No. It does not sort keys with more than one bit.
 (c) Insertion sort: Yes.
e.
The algorithm is implemented here. It is unstable.
83 Sorting variablelength items
a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time.
b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time.
(Note that the desired order here is the standard alphabetical order; for example,
a
<ab
<b
.)
a. We only consider positive integers without leading zeroes. For each integer k, we put it into the bucket i if it has i digits. Then radix sort each bucket. Finally concatenate elements in each bucket.
b. Solution is implemented here.
84 Water jugs
Suppose that you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa.
Your task is to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or that they have the same volume. Assume that such a comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs.
a. Describe a deterministic algorithm that uses Ξ($n^2$) comparisons to group the jugs into pairs.
b. Prove a lower bound of Ξ©(n lg n) for the number of comparisons that an algorithm solving this problem must make.
c. Give a randomized algorithm whose expected number of comparisons is O(n lg n), and prove that this bound is correct. What is the worstcase number of comparisons for your algorithm?
a. For each red jug, we compare it with every blue jug, and find the one with the same volume.
b. It is like sorting, if our algorithm correctly groups jugs into pairs, there must be n! different grouping possible result. So the decision tree must at least have the height lg n! = Ξ©(n lg n).
c. Solution is implemented here. The worstcast running time is Ξ($n^2$).
85 Average sorting
Suppose that, instead of sorting an array, we just require that the elements increase on average. More precisely, we call an nelement array A ksorted if, for all i = 1, 2, β¦, n  k, the following holds:
$\frac{β_{j = i}^{i + k  1} A\left[j\right]}{k} β€ \frac{β_{j = i + 1}^{i + k} A\left[j\right]}{k}$.
a. What does it mean for an array to be 1sorted?
b. Give a permutation of the numbers 1, 2, β¦, 10 that is 2sorted, but not sorted.
c. Prove that an nelement array is ksorted if and only if A[i] β€ A[i + k] for all i = 1, 2, β¦, n  k.
d. Give an algorithm that ksorts an nelement array in O(n lg(n / k)) time.
We can also show a lower bound on the time to produce a ksorted array, when k is a constant.
e. Show that we can sort a ksorted array of length n in O(n lg k) time. (Hint: Use the solution to Exercise 6.59.)
f. Show that when k is a constant, ksorting an nelement array requires Ξ©(n lg n) time. (Hint: Use the solution to the previous part along with the lower bound on comparison sorts.)
a.
It means the array is sorted.
b.
β¨2, 1, 4, 3, 6, 5, 8, 7, 10, 9β©.
c.
$\frac{β_{j = i}^{i + k  1} A\left[j\right]}{k} β€ \frac{β_{j = i + 1}^{i + k} A\left[j\right]}{k}$
β $β_{j = i}^{i + k  1} A\left[j\right] β€ β_{j = i + 1}^{i + k} A\left[j\right]$
β $A\left[i\right] + β_{j = i + 1}^{i + k  1} A\left[j\right] β€ β_{j = i + 1}^{i + k  1} A\left[j\right] + A\left[i + k\right]$
β $A\left[i\right] β€ A\left[i + k\right]$.
d.
Running an O(n lg n) running time sorting algorithm on subarrays β¨A[j], A[k + j], A[2 k + j], β¦β© for j = 0, 1, β¦, k  1.
e.
A ksorted array contains at most k sorted subarrays of length n / k, we can merge k sorted arrays in O(n / k lg k) = O(n lg k) time.
f.
Proof by contradiction: If ksorting an nelement array requires o(n lg n) time, then sorting an n element will only need o(n lg n) + O(n lg k) = o(n lg n) time, which is impossible. So ksorting an nelement array requires Ξ©(n lg n) time.
86 Lower bound on merging sorted lists
The problem of merging two sorted lists arises frequently. We have seen a procedure for it as the subroutine Merge in Section 2.3.1. In this problem, we will prove a lower bound of 2 n  1 on the worstcase number of comparisons required to merge two sorted lists, each containing n items.
First we will show a lower bound of 2 n  o(n) comparisons by using a decision tree.
a. Given 2 n numbers, compute the number of possible ways to divide them into two sorted lists, each with n numbers.
b. Using a decision tree and your answer to part (a), show that any algorithm that correctly merges two sorted lists must perform at least 2 n  o(n) comparisons.
Now we will show a slightly tighter 2 n  1 bound.
c. Show that if two elements are consecutive in the sorted order and from different lists, then they must be compared.
d. Use your answer to the previous part to show a lower bound of 2 n  1 comparisons for merging two sorted lists.
a.
C(2 n, n) = $\frac{(2 n)!}{\left(n!\right)^2}$.
b.
The decision tree has at least $\frac{(2 n)!}{\left(n!\right)^2}$ nodes, so the height of the tree is at least
$\lg \frac{(2 n)!}{\left(n!\right)^2}$
= lg ((2 n)!)  2 lg(n!)
= $β_{i = 1}^{2 n} \lg i  2 β_{i = 1}^{n} \lg i$
= $β_{i = n + 1}^{2 n} \lg i  β_{i = 1}^{n} \lg i$
= $β_{i = 1}^{n} \lg \left(n + i\right)  β_{i = 1}^{n} \lg i$
= $β_{i = 1}^{n} \lg (1 + n / i)$.
Skipped.
c.
Skipped.
d.
Skipped.
87 The 01 sorting lemma and columnsort
A compareexchange operation on two array elements A[i] and A[j], where i < j, has the form
CompareExchange(A, i, j)
 if A[i] > A[j]
 Β Β Β Β exchange A[i] with A[j]
After the compareexchange operation, we know that A[i] β€ A[j].
An oblivious compareexchange algorithm operates solely by a sequence of prespecified compareexchange operations. The indices of the positions compared in the sequence must be determined in advance, and although they can depend on the number of elements being sorted, they cannot depend on the values being sorted, nor can they depend on the result of any prior compareexchange operation. For example, here is insertion sort expressed as an oblivious compareexchange algorithm:
InsertionSort(A)
 for j = 2 to A.length
 Β Β Β Β for i = j  1 downto 1
 Β Β Β Β Β Β Β Β CompareExchange(A, i, i + 1)
The 01 sorting lemma provides a powerful way to prove that an oblivious compareexchange algorithm produces a sorted result. It states that if an oblivious compareexchange algorithm correctly sorts all input sequences consisting of only 0s and 1s, then it correctly sorts all inputs containing arbitrary values.
You will prove the 01 sorting lemma by proving its contrapositive: if an oblivious compareexchange algorithm fails to sort an input containing arbitrary values, then it fails to sort some 01 input. Assume that an oblivious compareexchange algorithm X fails to correctly sort the array A[1β₯n]. Let A[p] be the smallest value in A that algorithm X puts into the wrong location, and let A[q] be the value that algorithm X moves to the location into which A[p] should have gone. Define an array B[1β₯n] of 0s and 1s as follows:
B[i] = $\begin{cases} 0 &&\text{if } A\left[i\right] β€ A\left[p\right],\\ 1 &&\text{if } A\left[i\right] > A\left[p\right]. \end{cases}$
a. Argue that A[q] > A[p], so that B[p] = 0 and B[q] = 1.
b. To complete the proof of the 01 sorting lemma, prove that algorithm X fails to sort array B correctly.
Now you will use the 01 sorting lemma to prove that a particular sorting algorithm works correctly. The algorithm, columnsort, works on a rectangular array of n elements. The array has r rows and s columns (so that n = r s), subject to three restrictions:
 r must be even,
 s must be a divisor of r, and
 r β₯ 2 $s^2$.
When columnsort completes, the array is sorted in columnmajor order: reading down the columns, from left to right, the elements monotonically increase.
Columnsort operates in eight steps, regardless of the value of n. The odd steps are all the same: sort each column individually. Each even step is a fixed permutation. Here are the steps:
 Sort each column.
 Transpose the array, but reshape it back to r rows and s columns. In other words, turn the leftmost column into the top r / s rows, in order; turn the next column into the next r / s rows, in order; and so on.
 Sort each column.
 Perform the inverse of the permutation performed in step 2.
 Sort each column.
 Shift the top half of each column into the bottom half of the same column, and shift the bottom half of each column into the top half of the next column to the right. Leave the top half of the leftmost column empty. Shift the bottom half of the last column into the top half of a new rightmost column, and leave the bottom half of this new column empty.
 Sort each column.
 Perform the inverse of the permutation performed in step 6.
Figure 8.5 shows an example of the steps of columnsort with r = 6 and s = 3. (Even though this example violates the requirement that r β₯ 2 $s^2$, it happens to work.)
10 14 5 4 1 2 4 8 10 1 3 6 1 4 11 8 7 17 8 3 5 12 16 18 2 5 7 3 8 14 12 1 6 10 7 6 1 3 7 4 8 10 6 10 17 16 9 11 12 9 11 9 14 15 9 13 15 2 9 12 4 15 2 16 14 13 2 5 6 11 14 17 5 13 16 18 3 13 18 15 17 11 13 17 12 16 18 7 15 18 (a) (b) (c) (d) (e) 1 4 11 5 10 16 4 10 16 1 7 13 2 8 12 6 13 17 5 11 17 2 8 14 3 9 14 7 15 18 6 12 18 3 9 15 5 10 16 1 4 11 1 7 13 4 10 16 6 13 17 2 8 12 2 8 14 5 11 17 7 15 18 3 9 14 3 9 15 6 12 18 (f) (g) (h) (i)
Figure 8.5 The steps of columnsort. (a) The input array with 6 rows and 3 columns. (b) After sorting each column in step 1. (c) After transposing and reshaping in step 2. (d) After sorting each column in step 3. (e) After performing step 4, which inverts the permutation from step 2. (f) After sorting each column in step 5. (g) After shifting by half a column in step 6. (h) After sorting each column in step 7. (i) After performing step 8, which inverts the permutation from step 6. The array is now sorted in columnmajor order.
c. Argue that we can treat columnsort as an oblivious compareexchange algorithm, even if we do not know what sorting method the odd steps use.
Although it might seem hard to believe that columnsort actually sorts, you will use the 01 sorting lemma to prove that it does. The 01 sorting lemma applies because we can treat columnsort as an oblivious compareexchange algorithm. A couple of definitions will help you apply the 01 sorting lemma. We say that an area of an array is clean if we know that it contains either all 0s or all 1s. Otherwise, the area might contain mixed 0s and 1s, and it is dirty. From here on, assume that the input array contains only 0s and 1s, and that we can treat it as an array with r rows and s columns.
d. Prove that after steps 1β3, the array consists of some clean rows of 0s at the top, some clean rows of 1s at the bottom, and at most s dirty rows between them.
e. Prove that after step 4, the array, read in columnmajor order, starts with a clean area of 0s, ends with a clean area of 1s, and has a dirty area of at most $s^2$ elements in the middle.
f. Prove that steps 5β8 produce a fully sorted 01 output. Conclude that columnsort correctly sorts all inputs containing arbitrary values.
g. Now suppose that s does not divide r. Prove that after steps 1β3, the array consists of some clean rows of 0s at the top, some clean rows of 1s at the bottom, and at most 2 s  1 dirty rows between them. How large must r be, compared with s, for columnsort to correctly sort when s does not divide r?
h. Suggest a simple change to step 1 that allows us to maintain the requirement that r β₯ 2 $s^2$ even when s does not divide r, and prove that with your change, columnsort correctly sorts.
Skipped.
9 Medians and Order Statistics
9.1 Minimum and maximum
9.11
Show that the second smallest of n elements can be found with n + βlg nβ  2 comparisons in the worst case. (Hint: Also find the smallest element.)
Solution is implemented here.
9.12 β
Prove the lower bound of β3 n / 2β  2 comparisons in the worst case to find both the maximum and minimum of n numbers. (Hint: Consider how many numbers are potentially either the maximum or minimum, and investigate how a comparison affects these counts.)
Skipped.
9.2 Selection in expected linear time
9.21
Show that RandomizedSelect never makes a recursive call to a 0length array.

At line 8, we know that:
i < k
β i < q  p + 1
β 1 < q  p + 1
β (q  1)  p > 1
β (q  1)  p β₯ 0.So the recursion call in line 8 is on a nonempty subarray A[pβ₯q  1].

At line 9, we know that:
i > k
β i > q  p + 1
β r  p + 1 > q  p + 1
β r  (q + 1) > 1
β r  (q + 1) β₯ 0.So the recursion call in line 8 is on a nonempty subarray A[q + 1β₯r].
9.22
Argue that the indicator random variable $X_k$ and the value T(max(k  1, n  k)) are independent.
Skipped.
9.23
Write an iterative version of RandomizedSelect.
Solution is implemented here.
9.24
Suppose we use RandomizedSelect to select the minimum element of the array A = β¨3, 2, 9, 0, 7, 5, 4, 8, 6, 1β©. Describe a sequence of partitions that results in a worstcase performance of RandomizedSelect.
On each partition, the maximum element is selected as the pivot.
9.3 Selection in worstcase linear time
9.31
In the algorithm Select, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that Select does not run in linear time if groups of 3 are used.
Assume the elements are divided into groups of k, we know that the number of elements greater than x is at least ((k + 1) / 2) (ββn / kβ / 2β  2) β₯ (k + 1) n / (4 k)  k  1. So in the worst cast, the recursive call in step 5 is on at most (3 k  1) n / (4 k) + k + 1. So for n that is large enough:
T(n)
β€ c βn / kβ + c ((3 k  1) n / (4 k) + k + 1) + a n
β€ c n / k + c + c (3 k  1) n / (4 k) + c (k + 1) + a n
= (3 / 4) c (k + 1) n / k + c (k + 2) + a n
= (3 / 4) c (k + 1) n / k + c (k + 2) + a n
= c n + ((c ((3 / 4) (k + 1) / k  1) + a) n + c (k + 2)).
Solving c ((3 / 4) (k + 1) / k  1) + a < 0, we get:
c > a / (1  (3 / 4) (k + 1) / k).
 If k = 3, c > a / (1  (3 / 4) (3 + 1) / 3) = β, so thatβs not possible.
 If k = 7, c > a / (1  (3 / 4) (7 + 1) / 7) = 7 a, so it is possible to select a c > 7 a to make T(n) linear.
9.32
Analyze Select to show that if n β₯ 140, then at least βn / 4β elements are greater than the medianofmedians x and at least βn / 4β elements are less than x.
Skipped.
9.33
Show how quicksort can be made to run in O(n lg n) time in the worst case, assuming that all elements are distinct.
When doing partition, use the Select procedure to find the median element as the pivot.
9.34 β
Suppose that an algorithm uses only comparisons to find the ith smallest element in a set of n elements. Show that it can also find the i  1 smaller elements and the n  i larger elements without performing any additional comparisons.
Skipped.
9.35
Suppose that you have a βblackboxβ worstcase lineartime median subroutine. Give a simple, lineartime algorithm that solves the selection problem for an arbitrary order statistic.
Replace the first 3 steps of Select to a step of using the lineartime median subroutine to find the pivot.
The running time becomes:
T(n) = T(n / 2) + O(n).
Using the master theorem, we have T(n) = O(n).
9.36
The kth quantiles of an nelement set are the k  1 order statistics that divide the sorted set into k equalsized sets (to within 1). Give an O(n lg k)time algorithm to list the kth quantiles of a set.
Skipped.
9.37
Describe an O(n)time algorithm that, given a set S of n distinct numbers and a positive integer k β€ n, determines the k numbers in S that are closest to the median of S.
Skipped.
9.38
Let X[1β₯n] and Y[1β₯n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)time algorithm to find the median of all 2 n elements in arrays X and Y.
Solution is implemented here.
9.39
Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. The company wants to connect a spur pipeline from each well directly to the main pipeline along a shortest route (either north or south), as shown in Figure 9.2. Given the x and ycoordinates of the wells, how should the professor pick the optimal location of the main pipeline, which would be the one that minimizes the total length of the spurs? Show how to determine the optimal location in linear time.
Well Well β β Well β Well β β β Well β βββ¬β΄βββββ΄ββββ¬ββββ΄βββββ΄βββ¬ββββ΄βββ¬ββ β β β β Well β Well β Well Well
Figure 9.2 Professor Olay needs to determine the position of the eastwest oil pipeline that minimizes the total length of the northsouth spurs.
Notice that the xcoordinates does not affect the total length of the northsouth spurs, so we only consider the ycoordinates.
First, the conclusion: we should put the pipeline anywhere between the lower median and upper median of the ycoordinates of the wells.
Proof:
If we sort the ycoordinates of the wells by into an array A[1β₯n], let k be the y coordinates of the pipeline, then total length of the spurs is:
$β_{i = 1}^n \leftA\left[i\right]  k\right$
= $β_{i = 1}^{\left\lfloor n / 2\right\rfloor} \leftA\left[i\right]  k\right + β_{i = 1}^{\left\lfloor n / 2\right\rfloor} \leftA\left[n + 1  i\right]  k\right$ + (n mod 2) A[βn / 2β]  k
= $β_{i = 1}^{\left\lfloor n / 2\right\rfloor} \left(\leftA\left[i\right]  k\right + \leftA\left[n + 1  i\right]  k\right\right)$ + (n mod 2) A[βn / 2β]  k.
If A[i] β€ k β€ A[n + 1  i], A[i]  k + A[n + 1  i]  k will have the minimal value of A[n + 1  i]  A[i], which means k should between A[i] and A[n + 1  i]. If A[βn / 2β] β€ A[k] β€ A[n + 1  βn / 2β], k is between every (A[i], A[n + 1  i]) pair of wells. If n is even, we can put the pipeline anywhere between A[n / 2] and A[n / 2 + 1]; if n is odd, we must put the pipeline at coordinate A[(n + 1) / 2].
So we only need to use the Select procedure to find the median of all ycoordinates of the wells, which takes linear time.
9.X Problems
91 Largest i numbers in sorted order
Given a set of n numbers, we wish to find the i largest in sorted order using a comparisonbased algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worstcase running time, and analyze the running times of the algorithms in terms of n and i.
a. Sort the numbers, and list the i largest.
b. Build a maxpriority queue from the numbers, and call ExtractMax i times.
c. Use an orderstatistic algorithm to find the ith largest number, partition around that number, and sort the i largest numbers.
a. Merge sort, then list the i largest. Running time is O(n lg n + i).
b. Running time is O(n + i lg n).
c. Use Select to find the ith largest number, then partition around the ith largest number, then merge sort i largest numbers. Running time is O(n + i lg i).
92 Weighted median
For n distinct elements $x_1$, $x_2$, β¦, $x_n$ with positive weights $w_1$, $w_2$, β¦, $w_n$ such that $β_{i = 1}^n w_i$ = 1, the weighted (lower) median is the element $x_k$ satisfying
$\displaystyle β_{x_i < x_k} w_i < \frac{1}{2}$
and
$\displaystyle β_{x_i > x_k} w_i β€ \frac{1}{2}$.
For example, if the elements are 0.1, 0.35, 0.05, 0.1, 0.15, 0.05, 0.2 and each element equals its weight (that is, $w_i = x_i$ for i = 1, 2, β¦, 7), then the median is 0.1, but the weighted median is 0.2.
a. Argue that the median of $x_1$, $x_2$, β¦, $x_n$ is the weighted median of the $x_i$ with weights $w_i$ = 1 / n for i = 1, 2, β¦, n.
b. Show how to compute the weighted median of n elements in O(n lg n) worstcase time using sorting.
c. Show how to compute the weighted median in Ξ(n) worstcase time using a lineartime median algorithm such as Select from Section 9.3.
The postoffice location problem is defined as follows. We are given n points $p_1$, $p_2$, β¦, $p_n$ with associated weights $w_1$, $w_2$, β¦, $w_n$. We wish to find a point p (not necessarily one of the input points) that minimizes the sum $β_{i = 1}^n w_i d\left(p, p_i\right)$, where d(a, b) is the distance between points a and b.
d. Argue that the weighted median is a best solution for the 1dimensional postoffice location problem, in which points are simply real numbers and the distance between points a and b is d(a, b) = a  b.
e. Find the best solution for the 2dimensional postoffice location problem, in which the points are (x, y) coordinate pairs and the distance between points a = ($x_1$, $y_1$) and b = ($x_2$, $y_2$) is the Manhattan distance given by d(a, b) = $x_1  x_2$ + $y_1  y_2$.
a.
4 2 5 2 6 3 7 3
There are β(n  1) / 2β elements that are less than the median, and βn / 2β elements that are greater than the median. So we have
 $β_{x_i < x_k} w_i$ = β(n  1) / 2β / n < 1 / 2,
 $β_{x_i > x_k} w_i$ = βn / 2β / n β€ 1 / 2.
That satisfies the weighted median condition.
b.
First, sort the elements by their value, then accumulate the weight in the sorted array from left to right, until the accumulated value is greater than or equal to 1 / 2. Then the weighted median is the first element that makes the accumulated value greater than or equal to 1 / 2.
c.
The solution is implemented here.
d.
Skipped.
e.
$β_{i = 1}^n w_i d\left(p, p_i\right)$
= $β_{i = 1}^n w_i \left(\leftx_1  x_2\right + \lefty_1  y_2\right\right)$
= $β_{i = 1}^n w_i \leftx_1  x_2\right + β_{i = 1}^n w_i \lefty_1  y_2\right$
So we can find the weight medians of xcoordinates and ycoordinates individually, then combine the result into a new coordinates, which should be the location of the postoffice.
93 Small order statistics
We showed that the worstcase number T(n) of comparisons used by Select to select the ith order statistic from n numbers satisfies T(n) = Ξ(n), but the constant hidden by the Ξnotation is rather large. When i is small relative to n, we can implement a different procedure that uses Select as a subroutine but makes fewer comparisons in the worst case.
a. Describe an algorithm that uses $U_i\left(n\right)$ comparisons to find the ith smallest of n elements, where
$U_i\left(n\right)\begin{cases} T\left(n\right)&\text{if }i β₯ n / 2,\\ \left\lfloor n / 2\right\rfloor + U_i\left(\left\lceil n / 2\right\rceil\right) + T\left(2 i\right)&\text{otherwise}. \end{cases}$
(Hint: Begin with βn / 2β disjoint pairwise comparisons, and recurse on the set containing the smaller element from each pair.)
b. Show that, if i < n / 2, then $U_i\left(n\right)$ = n + O(T(2 i / lg(n / i)).
c. Show that if i is a constant less than n / 2, then $U_i\left(n\right)$ = n + O(lg n).
d. Show that if i = n / k for k β₯ 2, then $U_i\left(n\right)$ = n + O(T(2 n / k) lg k).
Skipped.
94 Alternative analysis of randomized selection
In this problem, we use indicator random variables to analyze the RandomizedSelect procedure in a manner akin to our analysis of RandomizedQuicksort in Section 7.4.2.
As in the quicksort analysis, we assume that all elements are distinct, and we rename the elements of the input array A as $z_1$, $z_2$, β¦, $z_n$, where $z_i$ is the ith smallest element. Thus, the call RandomizedSelect(A, 1, n, k) returns $z_k$.
For 1 β€ i < j β€ n, let
$X_{i j k}$ = I{$z_i$ is compared with $z_j$ sometime during the execution of the algorithm to find $z_k$}.
a. Give an exact expression for E[$X_{i j k}$]. (Hint: Your expression may have different values, depending on the values of i, j, and k.)
b. Let $X_k$ denote the total number of comparisons between elements of array A when finding $z_k$. Show that
$\displaystyle \operatorname{E}\left[X_k\right] β€ 2 \left(β_{i = 1}^k β_{j = k}^n \frac{1}{j  i + 1} + β_{j = k + 1}^n \frac{j  k  1}{j  k + 1} + β_{i = 1}^{k  2} \frac{k  i  1}{k  i + 1}\right)$.
c. Show that E[$X_k$] β€ 4 n.
d. Conclude that, assuming all elements of array A are distinct, RandomizedSelect runs in expected time O(n).
Skipped.
III Data Structures
10 Elementary Data Structures
10.1 Stacks and queues
10.11
Using Figure 10.1 as a model, illustrate the result of each operation in the sequence Push(S, 4), Push(S, 1), Push(S, 3), Pop(S), Push(S, 8), and Pop(S) on an initially empty stack S stored in array S[1β₯6].
Skipped.
10.12
Explain how to implement two stacks in one array A[1β¦n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The Push and Pop operations should run in O(1) time.
Solution is implemented here.
10.13
Using Figure 10.2 as a model, illustrate the result of each operation in the sequence Enqueue(Q, 4), Enqueue(Q, 1), Enqueue(Q, 3), Dequeue(Q), Enqueue(Q, 8), and Dequeue(Q) on an initially empty queue Q stored in array Q[1β₯6].
Skipped.
10.14
Rewrite Enqueue and Dequeue to detect underflow and overflow of a queue.
 Underflow condition: Q.tail == Q.head.
 Overflow condition: (Q.tail + 1) mod Q.length + 1 == Q.head.
10.15
Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (doubleended queue) allows insertion and deletion at both ends. Write four O(1)time procedures to insert elements into and delete elements from both ends of a deque implemented by an array.
here.
10.16
Show how to implement a queue using two stacks. Analyze the running time of the queue operations.
Solution is implemented here.
Push need O(1) running time, Pop need O(1) running time on average, but has worstcase O(n) running time.
10.17
Show how to implement a stack using two queues. Analyze the running time of the stack operations.
Solution is implemented here.
Push need O(1) running time, Pop need O(n) running time.
10.2 Linked lists
10.21
Can you implement the dynamicset operation Insert on a singly linked list in O(1) time? How about Delete?
Insert can be done in O(1) time.
As for Delete, if the node to be deleted is the last node, I will have to use O(n) time to delete it, but for nodes that are not the last node, I can move the contents of the next node into the node to be deleted, which will make the linked list look like the node is deleted. This method takes O(1) time.
Solution is implemented here.
10.22
Implement a stack using a singly linked list L. The operations Push and Pop should still take O(1) time.
Solution is implemented here.
10.23
Implement a queue by a singly linked list L. The operations Enqueue and Dequeue should still take O(1) time.
Solution is implemented here.
10.24
As written, each loop iteration in the ListSearchβ² procedure requires two tests: one for x β L.nil and one for x.key β k. Show how to eliminate the test for x β L.nil in each iteration.
Set the value of x.nil.key to k, so that if every test fails for k, we will get x.nil as the result, which is exactly what we wanted.
10.25
Implement the dictionary operations Insert, Delete, and Search using singly linked, circular lists. What are the running times of your procedures?
Skipped.
10.26
The dynamicset operation Union takes two disjoint sets $S_1$ and $S_2$ as input, and it returns a set S = $S_1 βͺ S_2$ consisting of all the elements of $S_1$ and $S_2$. The sets $S_1$ and $S_2$ are usually destroyed by the operation. Show how to support Union in O(1) time using a suitable list data structure.
Both singly and doubly linked list are fine, just stitch the tail of the first list onto the head of the second list and you are done.
10.27
Give a Ξ(n)time nonrecursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for the list itself.
Remember that we have implemented a stack using singly linked list in exercise 10.22? To reverse a singly linked list, just treat the list as a stack, and pop their elements to construct a new list, the newly constructed list will be the reversion of the original list.
10.28 β
Explain how to implement doubly linked lists using only one pointer value x.np per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as kbit integers, and define x.np to be x.np = x.next XOR x.prev, the kbit βexclusiveorβ of x.next and x.prev. (The value nil is represented by 0.) Be sure to describe what information you need to access the head of the list. Show how to implement the Search, Insert, and Delete operations on such a list. Also show how to reverse such a list in O(1) time.
Skipped.
10.3 Implementing pointers and objects
10.31
Draw a picture of the sequence β¨13, 4, 8, 19, 5, 11β© stored as a doubly linked list using the multiplearray representation. Do the same for the singlearray representation.
Skipped.
10.32
Write the procedures AllocateObject and FreeObject for a homogeneous collection of objects implemented by the singlearray representation.
Solution is implemented here.
10.33
Why donβt we need to set or reset the prev attributes of objects in the implementation of the AllocateObject and FreeObject procedures?
We treat the free list as a singly linked list, which only uses the next attribute, we donβt care for attributes other than prev.
10.34
It is often desirable to keep all elements of a doubly linked list compact in storage, using, for example, the first m index locations in the multiplearray representation. (This is the case in a paged, virtualmemory computing environment.) Explain how to implement the procedures AllocateObject and FreeObject so that the representation is compact. Assume that there are no pointers to elements of the linked list outside the list itself. (Hint: Use the array implementation of a stack.)
Skipped.
10.35
Let L be a doubly linked list of length n stored in arrays key, prev, and next of length m. Suppose that these arrays are managed by AllocateObject and FreeObject procedures that keep a doubly linked free list F. Suppose further that of the m items, exactly n are on list L and m  n are on the free list. Write a procedure CompactifyList(L, F) that, given the list L and the free list F, moves the items in L so that they occupy array positions 1, 2, β¦, n and adjusts the free list F so that it remains correct, occupying array positions n + 1; n + 2, β¦, m. The running time of your procedure should be Ξ(n), and it should use only a constant amount of extra space. Argue that your procedure is correct.
Solution is implemented here.
10.4 Representing rooted trees
10.41
Draw the binary tree rooted at index 6 that is represented by the following attributes:
index key left right 1 12 7 3 2 15 8 nil 3 4 10 nil 4 10 5 9 5 2 nil nil 6 18 1 4 7 7 nil nil 8 14 6 2 9 21 nil nil 10 5 nil nil
Skipped.
10.42
Write an O(n)time recursive procedure that, given an nnode binary tree, prints out the key of each node in the tree.
Solution is implemented here.
10.43
Write an O(n)time nonrecursive procedure that, given an nnode binary tree, prints out the key of each node in the tree. Use a stack as an auxiliary data structure.
Solution is implemented here.
10.44
Write an O(n)time procedure that prints all the keys of an arbitrary rooted tree with n nodes, where the tree is stored using the leftchild, rightsibling representation.
Solution is implemented here.
Notice that the solution is exactly the same as exercise 10.42, because the structure of an unbounded branching tree with leftchild, rightsibling representation is the same as a binary tree, but the children of nodes has different meaning, so we can iterate through the tree with the same method used for iterating binary trees.
10.45 β
Write an O(n)time nonrecursive procedure that, given an nnode binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.
Solution is implemented here.
10.46 β
The leftchild, rightsibling representation of an arbitrary rooted tree uses three pointers in each node: leftchild, rightsibling, and parent. From any node, its parent can be reached and identified in constant time and all its children can be reached and identified in time linear in the number of children. Show how to use only two pointers and one boolean value in each node so that the parent of a node or all of its children can be reached and identified in time linear in the number of children.
Let the three members be leftchild, rightsiblingorparent and islastchild.
 If the node is the last child of its parent, store pointer to left child in leftchild, pointer to parent in rightsiblingorparent, and true in islastchild.
 Otherwise store pointer to left child in leftchild, pointer to right sibling in rightsiblingorparent, and true in islastchild.
10.X Problems
101 Comparisons among lists
For each of the four types of lists in the following table, what is the asymptotic worstcase running time for each dynamicset operation listed?
unsorted, singly linked sorted, singly linked unsorted, doubly linked sorted, doubly linked Search(L, k) Insert(L, x) Delete(L, x) Successor(L, x) Predecessor(L, x) Minimum(L) Maximum(L)
unsorted, singly linked  sorted, singly linked  unsorted, doubly linked  sorted, doubly linked  

Search(L, k)  O(n)  O(n)  O(n)  O(n) 
Insert(L, x)  O(1)  O(n)  O(1)  O(n) 
Delete(L, x)  O(n)  O(n)  O(1)  O(1) 
Successor(L, x)  O(1)  O(1)  O(1)  O(1) 
Predecessor(L, x)  O(n)  O(n)  O(1)  O(1) 
Minimum(L)  O(n)  O(1)  O(n)  O(1) 
Maximum(L)  O(n)  O(n)  O(n)  O(n) 
102 Mergeable heaps using linked lists
A mergeable heap supports the following operations: MakeHeap (which creates an empty mergeable heap), Insert, Minimum, ExtractMin, and Union. Show how to implement mergeable heaps using linked lists in each of the following cases. Try to make each operation as efficient as possible. Analyze the running time of each operation in terms of the size of the dynamic set(s) being operated on.
 a. Lists are sorted.
 b. Lists are unsorted.
 c. Lists are unsorted, and dynamic sets to be merged are disjoint.
Skipped.
103 Searching a sorted compact list
Exercise 10.34 asked how we might maintain an nelement list compactly in the first n positions of an array. We shall assume that all keys are distinct and that the compact list is also sorted, that is, key[i] < key[next[i]] for all i = 1, 2, β¦, n such that next[i] β nil. We will also assume that we have a variable L that contains the index of the first element on the list. Under these assumptions, you will show that we can use the following randomized algorithm to search the list in O($\sqrt{n}$) expected time.
CompactListSearch(L, n, k)
 i = L
 while i β nil and key[i] < k
 Β Β Β Β j = Random(1, n)
 Β Β Β Β if key[i] < key[j] and key[j] β€ k
 Β Β Β Β Β Β Β Β i = j
 Β Β Β Β Β Β Β Β if key[i] == k
 Β Β Β Β Β Β Β Β Β Β Β Β return i
 Β Β Β Β i = next[i]
 if i == nil or key[i] > k
 Β Β Β Β return nil
 else return i
If we ignore lines 3β7 of the procedure, we have an ordinary algorithm for searching a sorted linked list, in which index i points to each position of the list in turn. The search terminates once the index i βfalls offβ the end of the list or once key[i] β₯ k. In the latter case, if key[i] = k, clearly we have found a key with the value k. If, however, key[i] > k, then we will never find a key with the value k, and so terminating the search was the right thing to do.
Lines 3β7 attempt to skip ahead to a randomly chosen position j. Such a skip benefits us if key[j] is larger than key[i] and no larger than k; in such a case, j marks a position in the list that i would have to reach during an ordinary list search. Because the list is compact, we know that any choice of j between 1 and n indexes some object in the list rather than a slot on the free list.
Instead of analyzing the performance of CompactListSearch directly, we shall analyze a related algorithm, CompactListSearchβ², which executes two separate loops. This algorithm takes an additional parameter t which determines an upper bound on the number of iterations of the first loop.
CompactListSearchβ²(L, n, k, t)
 i = L
 for q = 1 to t
 Β Β Β Β j = Random(1, n)
 Β Β Β Β if key[i] < key[j] and key[j] β€ k
 Β Β Β Β Β Β Β Β i = j
 Β Β Β Β Β Β Β Β if key[i] == k
 Β Β Β Β Β Β Β Β Β Β Β Β return i
 while i β nil and key[i] < k
 Β Β Β Β i = next[i]
 if i == nil or key[i] > k
 Β Β Β Β return nil
 else return i
To compare the execution of the algorithms CompactListSearch(L, n, k) and CompactListSearchβ²(L, n, k, t), assume that the sequence of integers returned by the calls of Random(1, n) is the same for both algorithms.
 a. Suppose that CompactListSearch(L, n, k) takes t iterations of the while loop of lines 2β8. Argue that CompactListSearchβ²(L, n, k, t) returns the same answer and that the total number of iterations of both the for and while loops within CompactListSearchβ² is at least t.
In the call CompactListSearchβ²(L, n, k, t), let $X_t$ be the random variable that describes the distance in the linked list (that is, through the chain of next pointers) from position i to the desired key k after t iterations of the for loop of lines 2β7 have occurred.
 b. Argue that the expected running time of CompactListSearchβ²(L, n, k, t) is O(t + E[$X_t$]).
 c. Show that E[$X_t$] β€ $β_{r = 1}^n \left(1  r / n\right)^t$. (Hint: Use equation (C.25).)
 d. Show that $β_{r = 0}^{n  1} r^t β€ n^{t + 1} / \left(t + 1\right)$.
 e. Prove that E[$X_t$] β€ n / (t + 1).
 f. Show that CompactListSearchβ²(L, n, k, t) runs in O(t + n / t) expected time.
 g. Conclude that CompactListSearch runs in O($\sqrt{n}$) expected time.
 h. Why do we assume that all keys are distinct in CompactListSearch? Argue that random skips do not necessarily help asymptotically when the list contains repeated key values.
Skipped.
11 Hash Tables
11.1 Directaddress tables
11.11
Suppose that a dynamic set S is represented by a directaddress table T of length m. Describe a procedure that finds the maximum element of S. What is the worstcase performance of your procedure?
Ξ(m).
11.12
A bit vector is simply an array of bits (0s and 1s). A bit vector of length m takes much less space than an array of m pointers. Describe how to use a bit vector to represent a dynamic set of distinct elements with no satellite data. Dictionary operations should run in O(1) time.
We use the value of ith bit to indicate whether the key i exists, then the implementation is trivial.
11.13
Suggest how to implement a directaddress table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictionary operations (Insert, Delete, and Search) should run in O(1) time. (Donβt forget that Delete takes as an argument a pointer to an object to be deleted, not a key.)
For all elements with key k, store them in a doubly linked list, then store the doubly linked list in position i of the directaddress table.
11.14 β
We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a directaddress dictionary on a huge array. Each stored object should use O(1) space; the operations Search, Insert, and Delete should take O(1) time each; and initializing the data structure should take O(1) time. (Hint: Use an additional array, treated somewhat like a stack whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)
Solution is implemented here.
11.2 Hash tables
11.21
Suppose we use a hash function h to hash n distinct keys into an array T of length m. Assuming simple uniform hashing, what is the expected number of collisions? More precisely, what is the expected cardinality of {{k, l} : k β l and h(k) = h(l)}?
Let $X_i$ be the random variable that represents the number of elements in the ith position, then the expected number of collisions is:
E[$β_{i = 1}^m X_i \left(X_i  1\right) / 2$]
= $β_{i = 1}^m \operatorname{E} \left[X_i \left(X_i  1\right) / 2\right]$
= m E[$X_1 \left(X_1  1\right) / 2$]
= m (E[$X_1^2$]  E[$X_1$]) / 2
= m (E[$X_1^2$]  n / m) / 2
= m ($\operatorname{E}^2 \left[X_i\right]$ + Var[$X_i$]  n / m) / 2
= m ($\left(n / m\right)^2$ + n (1 / m) (m  1) / m  n / m) / 2
= n (n  1) / (2 m).
That is way too complicated.
Another way:
Let $X_i$ be the ith key, then the expected number of collisions is:
E[$β_{i = 1}^{n  1} β_{j = i + 1}^n \Pr\left\lbrace h\left(X_i\right) = h\left(X_j\right) \right\rbrace$]
= E[$β_{i = 1}^{n  1} β_{j = i + 1}^n 1 / m$]
= $β_{i = 1}^{n  1} β_{j = i + 1}^n 1 / m$
= n (n  1) / (2 m).
11.22
Demonstrate what happens when we insert the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash function be h(k) = k mod 9.
Skipped.
11.23
Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professorβs modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?
 Successful searches: Worst case running time decreases to Ξ(lg n).
 Unsuccessful searches: Worst case running time decreases to Ξ(lg n).
 Insertions: Worst case running time increases to Ξ(n).
 Deletions: Unaffected.
11.24
Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All dictionary and freelist operations should run in O(1) expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?
Solution is implemented here.
11.25
Suppose that we are storing a set of n keys into a hash table of size m. Show that if the keys are drawn from a universe U with U > n m, then U has a subset of size n consisting of keys that all hash to the same slot, so that the worstcase searching time for hashing with chaining is Ξ(n).
This is like putting n m balls into m buckets, there must be at least one bucket contains more than or equal to n balls.
11.26
Suppose we have stored n keys in a hash table of size m, with collisions resolved by chaining, and that we know the length of each chain, including the length L of the longest chain. Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time O(L β (1 + 1 / Ξ±)).
First, randomly generate an integer i within [1, m], then generate an random integer j within [1, L], if the length of the ith chain is less than or equal to j, return the jth element of the ith chain as the result, otherwise repeat the process.
Rationalization:
j
β
L β β
β β β β
β ββ β β β
ββββ ββ β β β β β β
ββββ βββ β βββ βββββ ββ
βββΌββββββββββββββββββββββββ i
0 β m
Time complexity analysis:
The process is a sequence of Bernoulli trials with a probability p = n / (m L). So the number of iterations needed to find an element follows geometric distribution, so the expected number of iterations for finding the position of an element is 1 / p = m L / n = L / Ξ±. But it is not done, we still need to get the value of the selected element in a linked list, which takes O(L) time. So the total expected running time is Ξ(L / Ξ±) + O(L) = O (L β (1 + 1 / Ξ±)).
11.3 Hash functions
11.31
Suppose we wish to search a linked list of length n, where each element contains a key k along with a hash value h(k). Each key is a long character string. How might we take advantage of the hash values when searching the list for an element with a given key?
Precompute the hash value of the given key. Then when searching the linked list, first compare the hash value, only if the hash values are equal, we compare the actual string.
11.32
Suppose that we hash a string of r characters into m slots by treating it as a radix128 number and then using the division method. We can easily represent the number m as a 32bit computer word, but the string of r characters, treated as a radix128 number, takes many words. How can we apply the division method to compute the hash value of the character string without using more than a constant number of words of storage outside the string itself?
Solution is implemented here.
11.33
Consider a version of the division method in which h(k) = k mod m, where m = $2^p$  1 and k is a character string interpreted in radix $2^p$. Show that if we can derive string x from string y by permuting its characters, then x and y hash to the same value. Give an example of an application in which this property would be undesirable in a hash function.
According to the solution to exercise 11.32, we can calculate the hash value using a loop whose body is:
result = (result Γ $2^p$ + S[i]) mod m.
If m = $2^p$  1, the body become:
result
= (result Γ $2^p$ + S[i]) mod ($2^p$  1)
= ((result mod ($2^p$  1)) Γ ($2^p$ mod ($2^p$  1)) + S[i] mod ($2^p$  1)) mod ($2^p$  1)
= ((result mod ($2^p$  1)) Γ 1 + S[i] mod ($2^p$  1)) mod ($2^p$  1)
= ((result mod ($2^p$  1)) + S[i] mod ($2^p$  1)) mod ($2^p$  1)
= (result + S[i] mod ($2^p$  1)) mod ($2^p$  1).
Where S[i] is the ith element of the string.
So the final result is just $\left(β_{i = 1}^n S[i] \bmod m\right) \bmod m$. Notice that the order of S[i] does not matter in calculating the hash value.
As for the example, consider storing the anagrams of a word in a hash table.
11.34
Consider a hash table of size m = 1000 and a corresponding hash function h(k) = βm (k A mod 1)β for A = ($\sqrt{5}$  1) / 2. Compute the locations to which the keys 61, 62, 63, 64, and 65 are mapped.
Skipped.
11.35 β
Define a family β of hash functions from a finite set U to a finite set B to be Ο΅universal if for all pairs of distinct elements k and l in U,
Pr{h(k) = h(l)} β€ Ο΅,
where the probability is over the choice of the hash function h drawn at random from the family β. Show that an Ο΅universal family of hash functions must have
Ο΅ β₯ $\displaystyle \frac{1}{\leftB\right}  \frac{1}{\leftU\right}$.
Skipped.
11.36 β
Let U be the set of ntuples of values drawn from $β€_p$, and let B = $β€_p$, where p is prime. Define the hash function $h_b$: U β B for b β $β€_p$ on an input ntuple β¨$a_0$, $a_1$, β¦, $a_{n  1}$β© from U as
$h_b\left(β¨a_0, a_1, β¦, a_{n  1}β©\right) = \left(\displaystyle β_{j = 0}^{n = 1} a_j b^j\right) \bmod p$.
and let β = {$h_b$ : b β $β€_p$}. Argue that β is ((n  1) / p)universal according to the definition of Ο΅universal in Exercise 11.35. (Hint: See Exercise 31.44.)
Skipped.
11.4 Open addressing
11.41
Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of length m = 11 using open addressing with the auxiliary hash function hβ²(k) = k. Illustrate the result of inserting these keys using linear probing, using quadratic probing with $c_1$ = 1 and $c_2$ = 3, and using double hashing with $h_1$(k) = k and $h_2$(k) = 1 + (k mod (m  1)).
Skipped.
11.42
Write pseudocode for HashDelete as outlined in the text, and modify HashInsert to handle the special value deleted.
Skipped.
11.43
Consider an openaddress hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when the load factor is 3 / 4 and when it is 7 / 8.
Skipped.
11.44 β
Suppose that we use double hashing to resolve collisionsβthat is, we use the hash function h(k, i) = ($h_1$(k) + i $h_2$(k)) mod m. Show that if m and $h_2$(k) have greatest common divisor d β₯ 1 for some key k, then an unsuccessful search for key k examines (1 / d)th of the hash table before returning to slot h_1(k). Thus, when d = 1, so that m and $h_2$(k) are relatively prime, the search may examine the entire hash table. (Hint: See Chapter 31.)
Skipped.
11.45 β
Consider an openaddress hash table with a load factor Ξ±. Find the nonzero value Ξ± for which the expected number of probes in an unsuccessful search equals twice the expected number of probes in a successful search. Use the upper bounds given by Theorems 11.6 and 11.8 for these expected numbers of probes.
Skipped.
11.5 Perfect hashing β
11.51 β
Suppose that we insert n keys into a hash table of size m using open addressing and uniform hashing. Let p(n, m) be the probability that no collisions occur. Show that p(n, m) β€ $e^{n \left(n  1\right) / 2 m}$. (Hint: See equation (3.12).) Argue that when n exceeds $\sqrt{m}$, the probability of avoiding collisions goes rapidly to zero.
p(n, m)
= $\frac{P\left(m, n\right)}{m^n}$
Skipped.
11.X Problems
111 Longestprobe bound for hashing
Suppose that we use an openaddressed hash table of size m to store n β€ m / 2 items.
a. Assuming uniform hashing, show that for i = 1, 2, β¦, n, the probability is at most $2^{k}$ that the ith insertion requires strictly more than k probes.
b. Show that for i = 1, 2, β¦, n, the probability is O(1 / $n^2$) that the ith insertion requires more than 2 lg n probes.
Let the random variable $X_i$ denote the number of probes required by the ith insertion. You have shown in part (b) that Pr{$X_i$ > 2 lg n} = O(1 / $n^2$). Let the random variable X = $\max_{1 β€ i β€ n} X_i$ denote the maximum number of probes required by any of the n insertions.
c. Show that Pr{X > 2 lg n} = O(1 / n).
d. Show that the expected length E[X] of the longest probe sequence is O(lg n).
Skipped.
112 Slotsize bound for chaining
Suppose that we have a hash table with n slots, with collisions resolved by chaining, and suppose that n keys are inserted into the table. Each key is equally likely to be hashed to each slot. Let M be the maximum number of keys in any slot after all the keys have been inserted. Your mission is to prove an O(lg n / lg lg n) upper bound on E[M], the expected value of M.
a. Argue that the probability $Q_k$ that exactly k keys hash to a particular slot is given by $\displaystyle Q_k = \left(\frac{1}{n}\right)^k \left(1  \frac{1}{n}\right)^{n  k} \binom{n}{k}$.
b. Let $P_k$ be the probability that M = k, that is, the probability that the slot containing the most keys contains k keys. Show that $P_k$ β€ n $Q_k$.
c. Use Stirlingβs approximation, equation (3.18), to show that $Q_k < e^k / k^k$.
d. Show that there exists a constant c > 1 such that $Q_{k_0}$ < 1 / $n^3$ for $k_0$ = c lg n / lg lg n. Conclude that $P_k$ < 1 / $n^2$ for k β₯ $k_0$ = c lg n / lg lg n.
e. Argue that
$\displaystyle \operatorname{E}\left[M\right] β€ \Pr\left\lbrace M > \frac{c \lg n}{\lg \lg n} \right\rbrace β n + \Pr\left\lbrace M β€ \frac{c \lg n}{\lg \lg n} \right\rbrace β \frac{c \lg n}{\lg \lg n}$.
Conclude that E[M] = O(lg n / lg lg n).
Skipped.
113 Quadratic probing
Suppose that we are given a key k to search for in a hash table with positions 0, 1, β¦, m  1, and suppose that we have a hash function h mapping the key space into the set {0, 1, β¦, m  1}. The search scheme is as follows:
 Compute the value j = h(k), and set i = 0.
 Probe in position j for the desired key k. If you find it, or if this position is empty, terminate the search.
 Set i = i + 1. If i now equals m, the table is full, so terminate the search. Otherwise, set j = (i + j) / mod m, and return to step 2.
Assume that m is a power of 2.
a. Show that this scheme is an instance of the general βquadratic probingβ scheme by exhibiting the appropriate constants $c_1$ and $c_2$ for equation (11.5).
b. Prove that this algorithm examines every table position in the worst case.
Skipped.
114 Hashing and authentication
Let β be a class of hash functions in which each hash function h β β maps the universe U of keys to {0, 1, β¦, m  1}. We say that β is kuniversal if, for every fixed sequence of k distinct keys $β¨x^{(1)}, x^{(2)}, β¦, x^{(k)}β©$ and for any h chosen at random from β, the sequence $β¨h(x^{(1)}), h(x^{(2)}), β¦, h(x^{(k)})β©$ is equally likely to be any of the $m^k$ sequences of length k with elements drawn from {0, 1, β¦, m  1}.
a. Show that if the family β of hash functions is 2universal, then it is universal.
b. Suppose that the universe U is the set of ntuples of values drawn from $β€_p$ = {0, 1, β¦, p  1}, where p is prime. Consider an element x = $β¨x_0, x_1, β¦, x_{n  1}β©$ β U. For any ntuple a = $β¨a_0, a_1, β¦, a_{n  1}β©$ β U, define the hash function $h_a$ by
$\displaystyle h_a(x) = \left(β_{j = 0}^{n  1} a_j x_j\right) \bmod p$.
Let β = {$h_a$}. Show that β is universal, but not 2universal. (Hint: Find a key for which all hash functions in β produce the same value.)
c. Suppose that we modify β slightly from part (b): for any a β U and for any b β $β€_p$, define
$\displaystyle h'_{a b}(x) = \left(β_{j = 0}^{n  1} a_j x_j + b\right) \bmod p$
and ββ² = {$h'_{a b}$}. Argue that ββ² is 2universal. (Hint: Consider fixed ntuples x β U and y β U, with $x_i$ β $y_i$ for some i. What happens to $h'_{a b}(x)$ and $h'_{a b}(y)$ as $a_i$ and b range over $β€_p$?)
d. Suppose that Alice and Bob secretly agree on a hash function h from a 2universal family β of hash functions. Each h β β maps from a universe of keys U to $β€_p$, where p is prime. Later, Alice sends a message m to Bob over the Internet, where m β U. She authenticates this message to Bob by also sending an authentication tag t = h(m), and Bob checks that the pair (m, t) he receives indeed satisfies t = h(m). Suppose that an adversary intercepts (m, t) en route and tries to fool Bob by replacing the pair (m, t) with a different pair (mβ², tβ²). Argue that the probability that the adversary succeeds in fooling Bob into accepting (mβ², tβ²) is at most 1 / p, no matter how much computing power the adversary has, and even if the adversary knows the family β of hash functions used.
Skipped.
12 Binary Search Trees
12.1 What is a binary search tree?
12.11
For the set of {1, 4, 5, 10, 16, 17, 21} of keys, draw binary search trees of heights 2, 3, 4, 5, and 6.
Skipped.
12.12
What is the difference between the binarysearchtree property and the minheap property (see page 153)? Can the minheap property be used to print out the keys of an nnode tree in sorted order in O(n) time? Show how, or explain why not.
Binarysearchtree property requires nodes in left subtree of every node being less than or equal to a node, but minheap property requires nodes in left subtree of every node being greater than or equal to the node.
We can not print out the keys of an nnode tree with minheap property in sorted order in O(n) time. Remember heapsort? If we can do that, we can get a comparison sorting algorithm runs in O(n) time, which is impossible.
12.13
Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant, solution uses no stack but assumes that we can test two pointers for equality.)
Solution is implemented here.
12.14
Give recursive algorithms that perform preorder and postorder tree walks in Ξ(n) time on a tree of n nodes.
Solution is implemented here.
12.15
Argue that since sorting n elements takes Ξ©(n lg n) time in the worst case in the comparison model, any comparisonbased algorithm for constructing a binary search tree from an arbitrary list of n elements takes Ξ©(n lg n) time in the worst case.
Like exercise 12.12, If we can construct a binary search tree within o(n lg n) time, we can get a comparison sorting algorithm that takes o(n lg n) time, which is impossible.
12.2 Querying a binary search tree
12.21
Suppose that we have numbers between 1 and 1000 in a binary search tree, and we want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined?
 a. 2, 252, 401, 398, 330, 344, 397, 363.
 b. 924, 220, 911, 244, 898, 258, 362, 363.
 c. 925, 202, 911, 240, 912, 245, 363.
 d. 2, 399, 387, 219, 266, 382, 381, 278, 363.
 e. 935, 278, 347, 621, 299, 392, 358, 363.
c and e are not valid sequences.
Here is an algorithm for detecting valid sequences.
12.22
Write recursive versions of TreeMinimum and TreeMaximum.
Solution is implemented here.
12.23
Write the TreePredecessor procedure.
Solution is implemented here.
12.24
Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key k in a binary search tree ends up in a leaf. Consider three sets: A, the keys to the left of the search path; B, the keys on the search path; and C, the keys to the right of the search path. Professor Bunyan claims that any three keys a β A, b β B, and c β C must satisfy a β€ b β€ c. Give a smallest possible counterexample to the professorβs claim.
βββββ
β 1 β
βββ¬ββ
βββββ΄ββββ
ββββ΄βββ βββ΄ββ
β nil β β 3 β
βββββββ βββ¬ββ
ββββ΄ββββ
βββ΄ββ βββ΄ββ
β 2 β β 4 β
βββββ βββββ
Searching for 4, we have 2 β A and 1 β B.
12.25
Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.
If a node has left child then its predecessor is the right most node of the left child, if the right most node has right child, then it is not the right most child, by contradiction, we know the predecessor has no right child.
The same applies to the successor.
12.26
Consider a binary search tree T whose keys are distinct. Show that if the right subtree of a node x in T is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x. (Recall that every node is its own ancestor.)
Skipped.
12.27
An alternative method of performing an inorder tree walk of an nnode binary search tree finds the minimum element in the tree by calling TreeMinimum and then making n  1 calls to TreeSuccessor. Prove that this algorithm runs in Ξ(n) time.
Skipped.
12.28
Prove that no matter what node we start at in a heighth binary search tree, k successive calls to TreeSuccessor take O(k + h) time.
Skipped.
12.29
Let T be a binary search tree whose keys are distinct, let x be a leaf node, and let y be its parent. Show that y.key is either the smallest key in T larger than x.key or the largest key in T smaller than x.key.
By the definition of Successor, we know that:
 If x is the left child of y, then y is the successor of x, so y.key is the smallest key in T larger than x.key.
 Otherwise, x is the right child of y, then x is the successor of y, so y.key is the largest key in T smaller than x.key.
12.3 Insertion and deletion
12.31
Give a recursive version of the TreeInsert procedure.
Solution is implemented here.
12.32
Suppose that we construct a binary search tree by repeatedly inserting distinct values into the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted into the tree.
Note that the new value is only inserted to the leaf position, so inserting a new value does not affect the relative positions of the old values, which means once a node is inserted into the tree, it stays at its position all the time.
The number of nodes to be examined when the node was inserted into the tree equals to the number of ancestors except the node itself, and searching examines all the nodeβs ancestors. So the claim is true.
12.33
We can sort a given set of n numbers by first building a binary search tree containing these numbers (using TreeInsert repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worstcase and bestcase running times for this sorting algorithm?
Worstcase running time is Ξ($n^2$) when the numbers are already sorted.
Bestcase running time is Ξ(n log n) when the tree is a complete binary tree.
12.34
Is the operation of deletion βcommutativeβ in the sense that deleting x and then y from a binary search tree leaves the same tree as deleting y and then x? Argue why it is or give a counterexample.
Deletion is not βcommutativeβ.
Counterexample: deleting 1 and 2 from the following tree:
βββββ
β 2 β
βββ¬ββ
ββββ΄ββββ
βββ΄ββ βββ΄ββ
β 1 β β 4 β
βββββ βββ¬ββ
βββββ΄ββββ
βββ΄ββ ββββ΄βββ
β 3 β β nil β
βββββ βββββββ
Delete 1 first, then delete 2, we will get the following tree:
βββββ
β 4 β
βββ¬ββ
βββββ΄ββββ
βββ΄ββ ββββ΄βββ
β 3 β β nil β
βββββ βββββββ
Delete 2 first, then delete 1, we will get the following tree:
βββββ
β 3 β
βββ¬ββ
βββββ΄ββββ
ββββ΄βββ βββ΄ββ
β nil β β 4 β
βββββββ βββββ
12.35
Suppose that instead of each node x keeping the attribute x.p, pointing to xβs parent, it keeps x.succ, pointing to xβs successor. Give pseudocode for Search, Insert, and Delete on a binary search tree T using this representation. These procedures should operate in time O(h), where h is the height of the tree T. (Hint: You may wish to implement a subroutine that returns the parent of a node.)
Skipped.
12.36
When node z in TreeDelete has two children, we could choose node y as its predecessor rather than its successor. What other changes to TreeDelete would be necessary if we did so? Some have argued that a fair strategy, giving equal priority to predecessor and successor, yields better empirical performance. How might TreeDelete be changed to implement such a fair strategy?
Skipped.
12.4 Randomly built binary search trees β
12.41
Prove equation (12.3).
Proof by induction:

Base case: If n = 1,
$β_{i = 0}^{n  1} \binom{i + 3}{3}$ = $β_{i = 0}^{0} \binom{i + 3}{3}$ = $\binom{3}{3}$ = 1.
$\binom{n + 3}{4}$ = $\binom{4}{4}$ = 1.
So the claim holds.

Inductive cases: If n > 1,
$β_{i = 0}^{n  1} \binom{i + 3}{3}$
= $β_{i = 0}^{n  2} \binom{i + 3}{3} + \binom{n + 2}{3}$
= $\binom{n + 2}{4} + \binom{n + 2}{3}$
= $\frac{\left(n + 2\right)!}{4! \left(n  2\right)!} + \frac{\left(n + 2\right)!}{3! \left(n  1\right)!}$
= $\frac{\left(n + 2\right)!}{\left(n  1\right)!} \left(\frac{n  1}{4!} + \frac{1}{3!}\right)$
= $\frac{\left(n + 2\right)!}{\left(n  1\right)!} \frac{n + 3}{4!}$
= $\frac{\left(n + 3\right)!}{\left(n  1\right)! 4!}$
= $\binom{n + 3}{4}$.
12.42
Describe a binary search tree on n nodes such that the average depth of a node in the tree is Ξ(lg n) but the height of the tree is Ο(lg n). Give an asymptotic upper bound on the height of an nnode binary search tree in which the average depth of a node is Ξ(lg n).
Skipped.
12.43
Show that the notion of a randomly chosen binary search tree on n keys, where each binary search tree of n keys is equally likely to be chosen, is different from the notion of a randomly built binary search tree given in this section. (Hint: List the possibilities when n = 3.)
Skipped.
12.44
Show that the function f(x) = $2^x$ is convex.
Skipped.
12.45 β
Consider RandomizedQuicksort operating on a sequence of n distinct input numbers. Prove that for any constant k > 0, all but O(1 / $n^k$) of the n! input permutations yield an O(n lg n) running time.
Skipped.
12.X Problems
121 Binary search trees with equal keys
Equal keys pose a problem for the implementation of binary search trees.
 a. What is the asymptotic performance of TreeInsert when used to insert n items with identical keys into an initially empty binary search tree?
We propose to improve TreeInsert by testing before line 5 to determine whether z.key = x.key and by testing before line 11 to determine whether z.key = y.key.
If equality holds, we implement one of the following strategies. For each strategy, find the asymptotic performance of inserting n items with identical keys into an initially empty binary search tree. (The strategies are described for line 5, in which we compare the keys of z and x. Substitute y for x to arrive at the strategies for line 11.)
 b. Keep a boolean flag x.b at node x, and set x to either x.left or x.right based on the value of x.b, which alternates between false and true each time we visit x while inserting a node with the same key as x.
 c. Keep a list of nodes with equal keys at x, and insert z into the list.
 d. Randomly set x to either x.left or x.right. (Give the worstcase performance and informally derive the expected running time.)
 a. Ξ($n^2$).
 b. Ξ(n lg n).
 c. Ξ(n lg n).
 d. Ξ(n).
 d. Worstcase running time is Ξ($n^2$), expected running time is Ξ(n lg n).
122 Radix trees
Given two strings a = $a_0 a_1 β¦ a_p$ and b = $b_0 b_1 β¦ b_q$, where each $a_i$ and each $b_j$ is in some ordered set of characters, we say that string $a$ is lexicographically less than string $b$ if either
 there exists an integer j, where 0 β€ j β€ min(p, q), such that $a_i$ = $b_i$ for all i = 0, 1, β¦, j  1 and $a_j$ < $b_j$, or
 p < q and $a_i$ = $b_i$ for all i = 0, 1, β¦, p.
For example, if a and b are bit strings, then 10100 < 10110 by rule 1 (letting j = 3) and 10100 < 101000 by rule 2. This ordering is similar to that used in Englishlanguage dictionaries.
The radix tree data structure shown in Figure 12.5 stores the bit strings 1011, 10, 011, 100, and 0. When searching for a key a = $a_0 a_1 β¦ a_p$, we go left at a node of depth i if $a_i$ = 0 and right if $a_i$ = 1. Let S be a set of distinct bit strings whose lengths sum to n. Show how to use a radix tree to sort S lexicographically in Ξ(n) time. For the example in Figure 12.5, the output of the sort should be the sequence 0, 011, 10, 100, 1011.
ββββ β//β ββ¬ββ ββββββββββββ΄βββββββββββ 0 1 βββ΄ββ ββ΄ββ β 0 β β//β βββ¬ββ ββ¬ββ ββββ ββββ 1 0 ββ΄ββ βββ΄βββ β//β β 10 β ββ¬ββ βββ¬βββ βββββ ββββ΄ββββ 1 0 1 ββββ΄βββ ββββ΄βββ ββ΄ββ β 011 β β 100 β β//β βββββββ βββββββ ββ¬ββ βββββ 1 ββββ΄ββββ β 1011 β ββββββββ
Figure 12.5 A radix tree storing the bit strings 1011, 10, 011, 100, and 0. We can determine each nodeβs key by traversing the simple path from the root to that node. There is no need, therefore, to store the keys in the nodes; the keys appear here for illustrative purposes only. Nodes are heavily shaded if the keys corresponding to them are not in the tree; such nodes are present only to establish a path to other nodes.
Solution is implemented here.
123 Average node depth in a randomly built binary search tree
In this problem, we prove that the average depth of a node in a randomly built binary search tree with n nodes is O(lg n). Although this result is weaker than that of Theorem 12.4, the technique we shall use reveals a surprising similarity between the building of a binary search tree and the execution of RandomizedQuicksort from Section 7.3.
We define the total path length P(T) of a binary tree T as the sum, over all nodes x in T, of the depth of node x, which we denote by d(x, T).
a. Argue that the average depth of a node in T is
$\displaystyle \frac{1}{n} β_{x β T} d(x, T) = \frac{1}{n} P(T)$.
Thus, we wish to show that the expected value of P(T) is O(n lg n).
b. Let $T_L$ and $T_R$ denote the left and right subtrees of tree T, respectively. Argue that if T has n nodes, then
P(T) = P($T_L$) + P($T_R$) + n  1.
c. Let P(n) denote the average total path length of a randomly built binary search tree with n nodes. Show that
$\displaystyle P(n) = \frac{1}{n} β_{i = 0}^{n  1}(P(i) + P(n  i  1) + n  1)$.
d. Show how to rewrite P(n) as
$\displaystyle P(n) = \frac{2}{n} β_{k = 1}^{n  1} P(k) + Ξ(n)$.
e. Recalling the alternative analysis of the randomized version of quicksort given in Problem 73, conclude that P(n) = O(n lg n).
At each recursive invocation of quicksort, we choose a random pivot element to partition the set of elements being sorted. Each node of a binary search tree partitions the set of elements that fall into the subtree rooted at that node.
 f. Describe an implementation of quicksort in which the comparisons to sort a set of elements are exactly the same as the comparisons to insert the elements into a binary search tree. (The order in which comparisons are made may differ, but the same comparisons must occur.)
Skipped.
124 Number of different binary trees
Let $b_n$ denote the number of different binary trees with n nodes. In this problem, you will find a formula for $b_n$, as well as an asymptotic estimate.
a. Show that $b_0$ = 1 and that, for n β₯ 1,
$\displaystyle b_n = β_{k = 0}^{n  1} b_k b_{n  1  k}$.
b. Referring to Problem 44 for the definition of a generating function, let B(x) be the generating function
B(x) = $\displaystyle β_{n = 0}^β b_n x^n$.
Show that B(x) = x $B(x)^2$ + 1, and hence one way to express B(x) in closed form is
B(x) = $\dfrac{1}{2 x} \left(1  \sqrt{1  4 x}\right)$.
The Taylor expansion of f(x) around the point x = a is given by
f(x) = $\displaystyle β_{k = 0}^β \frac{f^{(k)}(a)}{k!}(x  a)^k$.
where $f^{(k)}(x)$ is the kth derivative of f evaluated at x.
c. Show that
$\displaystyle b_n = \frac{1}{n + 1} \binom{2 n}{n}$
(the nth Catalan number) by using the Taylor expansion of $\sqrt{1  4 x}$ around x = 0. (If you wish, instead of using the Taylor expansion, you may use the generalization of the binomial expansion (C.4) to nonintegral exponents n, where for any real number n and for any integer k, we interpret $\binom{n}{k}$ to be n (n  1) β― (n  k + 1) / k! if k β₯ 0, and 0 otherwise.)
d. Show that
$b_n = \dfrac{4^n}{\sqrt{Ο} n^{3 / 2}}$ (1 + O(1 / n)).

a
 There is only one type of binary tree of zero nodes, that is, no tree, so $b_0$ = 1.
 For n > 0, if the left child of the root has k nodes, then the right child has n  1  k nodes, for this situation, there can be $b_k b_{n  1  k}$ different kinds of trees. Since k must be in range [0, n  1], the total number of kinds of binary trees is $β_{k = 0}^{n  1} b_k b_{n  1  k}$.

b
Skipped.

c
Skipped.

d
Skipped.
13 RedBlack Trees
13.1 Properties of redblack trees
13.11
In the style of Figure 13.1(a), draw the complete binary search tree of height 3 on the keys {1, 2, β¦, 15}. Add the nil leaves and color the nodes in three different ways such that the blackheights of the resulting redblack trees are 2, 3, and 4.
There you go:
βββββββ
β [8] β
ββββ¬βββ
βββββββββββββββ΄βββββββββββββββ
βββ΄ββ βββ΄βββ
β 4 β β 12 β
βββ¬ββ βββ¬βββ
ββββββββ΄βββββββ βββββββββ΄ββββββββ
ββββ΄βββ ββββ΄βββ ββββ΄ββββ ββββ΄ββββ
β [2] β β [6] β β [10] β β [14] β
ββββ¬βββ ββββ¬βββ ββββ¬ββββ ββββ¬ββββ
ββββ΄ββββ ββββ΄ββββ ββββ΄ββββ βββββ΄ββββ
βββ΄ββ βββ΄ββ βββ΄ββ βββ΄ββ βββ΄ββ βββ΄βββ βββ΄βββ βββ΄βββ
β 1 β β 3 β β 5 β β 7 β β 9 β β 11 β β 13 β β 15 β
βββββ βββββ βββββ βββββ βββββ ββββββ ββββββ ββββββ
βββββββ
β [8] β
ββββ¬βββ
βββββββββββββββ΄βββββββββββββββ
ββββ΄βββ ββββ΄ββββ
β [4] β β [12] β
ββββ¬βββ ββββ¬ββββ
ββββββββ΄βββββββ βββββββββ΄ββββββββ
ββββ΄βββ ββββ΄βββ ββββ΄ββββ ββββ΄ββββ
β [2] β β [6] β β [10] β β [14] β
ββββ¬βββ ββββ¬βββ ββββ¬ββββ ββββ¬ββββ
ββββ΄ββββ ββββ΄ββββ ββββ΄ββββ βββββ΄ββββ
βββ΄ββ βββ΄ββ βββ΄ββ βββ΄ββ βββ΄ββ βββ΄βββ βββ΄βββ βββ΄βββ
β 1 β β 3 β β 5 β β 7 β β 9 β β 11 β β 13 β β 15 β
βββββ βββββ βββββ βββββ βββββ ββββββ ββββββ ββββββ
βββββββ
β [8] β
ββββ¬βββ
βββββββββββββββββββ΄βββββββββββββββββββ
ββββ΄βββ ββββ΄ββββ
β [4] β β [12] β
ββββ¬βββ ββββ¬ββββ
ββββββββββ΄βββββββββ βββββββββββ΄ββββββββββ
ββββ΄βββ ββββ΄βββ ββββ΄ββββ ββββ΄ββββ
β [2] β β [6] β β [10] β β [14] β
ββββ¬βββ ββββ¬βββ ββββ¬ββββ ββββ¬ββββ
βββββ΄βββββ βββββ΄βββββ βββββ΄βββββ ββββββ΄βββββ
ββββ΄βββ ββββ΄βββ ββββ΄βββ ββββ΄βββ ββββ΄βββ ββββ΄ββββ ββββ΄ββββ ββββ΄ββββ
β [1] β β [3] β β [5] β β [7] β β [9] β β [11] β β [13] β β [15] β
βββββββ βββββββ βββββββ βββββββ βββββββ ββββββββ ββββββββ ββββββββ
13.12
Draw the redblack tree that results after TreeInsert is called on the tree in Figure 13.1 with key 36. If the inserted node is colored red, is the resulting tree a redblack tree? What if it is colored black?
Skipped.
13.13
Let us define a relaxed redblack tree as a binary search tree that satisfies redblack properties 1, 3, 4, and 5. In other words, the root may be either red or black. Consider a relaxed redblack tree T whose root is red. If we color the root of T black but make no other changes to T, is the resulting tree a redblack tree?
Yes.
13.14
Suppose that we βabsorbβ every red node in a redblack tree into its black parent, so that the children of the red node become children of the black parent. (Ignore what happens to the keys.) What are the possible degrees of a black node after all its red children are absorbed? What can you say about the depths of the leaves of the resulting tree?
Skipped.
13.15
Show that the longest simple path from a node x in a redblack tree to a descendant leaf has length at most twice that of the shortest simple path from node x to a descendant leaf.
Since all simple paths has the same number of black nodes and the children of a red node must be black, the shortest path will contain no red nodes, and the longest path will interleave between black and red nodes, it is obvious that the longest path has length at most twice that of the shortest path.
13.16
What is the largest possible number of internal nodes in a redblack tree with blackheight k? What is the smallest possible number?
The largest number of internal nodes is $2^{2 k}$  1, the smallest possible number is $2^k$  1.
13.17
Describe a redblack tree on n keys that realizes the largest possible ratio of red internal nodes to black internal nodes. What is this ratio? What tree has the smallest possible ratio, and what is the ratio?
Skipped.
13.2 Rotations
13.21
Write pseudocode for RightRotate.
Iβll do you one better: Write real code for RightRotate.
13.22
Argue that in every nnode binary search tree, there are exactly n  1 possible rotations.
If a node is the left child of another node, we can do a right rotation on its parent; if a node is the right child of another node, we can do a left rotation on its parent. Since there are n  1 nodes with a parent, we can do n  1 possible rotations.
13.23
Let a, b, and c be arbitrary nodes in subtrees Ξ±, Ξ², and Ξ³, respectively, in the right tree of Figure 13.2. How do the depths of a, b, and c change when a left rotation is performed on node x in the figure?
βββββ β 7 β βββ¬ββ ββββββββ΄ββββββββ βββ΄ββ βββββ΄βββββ β 4 β β 11 (x) β βββ¬ββ βββββ¬βββββ ββββ΄ββββ βββββ΄βββββ βββ΄ββ βββ΄ββ βββ΄ββ βββββ΄βββββ β 3 β β 6 β β 9 β β 18 (y) β βββ¬ββ βββββ βββββ βββββ¬βββββ ββββ ββββββββ΄βββββββ βββ΄ββ βββ΄βββ βββ΄βββ β 2 β β 14 β β 19 β βββββ βββ¬βββ βββ¬βββ βββββ΄ββββ βββββ βββ΄βββ βββ΄βββ βββ΄βββ β 12 β β 17 β β 22 β ββββββ ββββββ βββ¬βββ ββββ β βββ΄βββ β β 20 β LeftRotate(T, X) β ββββββ β β β£ βββββ β 7 β βββ¬ββ βββββββββββ΄ββββββββββ βββ΄ββ βββββ΄βββββ β 4 β β 18 (y) β βββ¬ββ βββββ¬βββββ ββββ΄ββββ ββββββββ΄ββββββββ βββ΄ββ βββ΄ββ βββββ΄βββββ βββ΄βββ β 3 β β 6 β β 11 (x) β β 19 β βββ¬ββ βββββ βββββ¬βββββ βββ¬βββ ββββ ββββ΄ββββ βββββ βββ΄ββ βββ΄ββ βββ΄βββ βββ΄βββ β 2 β β 9 β β 14 β β 22 β βββββ βββββ βββ¬βββ βββ¬βββ βββββ΄ββββ ββββ βββ΄βββ βββ΄βββ βββ΄βββ β 12 β β 17 β β 20 β ββββββ ββββββ ββββββ
Figure 13.3 An example of how the procedure LeftRotate(T, x) modifies a binary search tree. Inorder tree walks of the input tree and the modified tree produce the same listing of key values.
 a increases by 1.
 b stays the same.
 c decreases by 1.
13.24
Show that any arbitrary nnode binary search tree can be transformed into any other arbitrary nnode binary search tree using O(n) rotations. (Hint: First show that at most n  1 right rotations suffice to transform the tree into a rightgoing chain.)
One right rotation operation decrease the total number of left child by exactly one and increase the total number of right child by exactly one. So n  1 right rotations suffice to transform the tree into a tree with at least n  1 right child, which can only be a rightgoing chain. This step takes O(n  1) time.
Since the left rotation and right rotation are symmetric, we can recover the original tree structure from a right going chain using left rotations in a reversed order, which takes O(n  1) time.
So to transform one tree A to another tree B, we can first transform it into a right going chain, then recover the struct of tree B. Both steps takes O(n  1) time, so the total running time is O(n).
13.25 β
We say that a binary search tree $T_1$ can be rightconverted to binary search tree $T_2$ if it is possible to obtain $T_2$ from $T_1$ via a series of calls to RightRotate. Give an example of two trees $T_1$ and $T_2$ such that $T_1$ cannot be rightconverted to $T_2$. Then, show that if a tree $T_1$ can be rightconverted to $T_2$, it can be rightconverted using O($n^2$) calls to RightRotate.
If A is a right going chain and B is a left going chain, A cannot be rightconverted into B since A doesnβt have left child nodes.
Skipped.
13.3 Insertion
13.31
In line 16 of RBInsert, we set the color of the newly inserted node z to red. Observe that if we had chosen to set zβs color to black, then property 4 of a redblack tree would not be violated. Why didnβt we choose to set zβs color to black?
For any valid redblack tree, property 4 is not violated, then after inserting a black node, red nodes are not affected, so property 4 will still be valid.
But setting zβs color to black will violate property 5, which seems harder to fix than property 4.
13.32
Show the redblack trees that result after successively inserting the keys 41, 38, 31, 12, 19, 8 into an initially empty redblack tree.
Skipped.
13.33
Suppose that the blackheight of each of the subtrees Ξ±, Ξ², Ξ³, Ξ΄, Ξ΅ in Figures 13.5 and 13.6 is k. Label each node in each figure with its blackheight to verify that the indicated transformation preserves property 5.
Skipped.
13.34
Professor Teach is concerned that RBInsertFixup might set T.nil.color to red, in which case the test in line 1 would not cause the loop to terminate when z is the root. Show that the professorβs concern is unfounded by arguing that RBInsertFixup never sets T.nil.color to red.
The only possible setting nodesβ color to red is line 7 and line 13, and in both cases, we are sure that z are z.p.pβs grandchild, so z.p.p canβt be T.nil. So RBInsertFixup never sets T.nil.color to red.
13.35
Consider a redblack tree formed by inserting n nodes with RBInsert. Argue that if n > 1, the tree has at least one red node.
Since n > 1, the tree will have a root, so the newly inserted node will have a parent.
If the newly inserted node is a child of a black node, the tree will not need any fixups. Since the newly inserted node is a red node, the tree has at least one red node.
If the newly inserted node is a child of a red node, we will have to do fixup operations on all three cases.
For case 1 of the fixup, one red node will be left on a branch of the new z of next iteration.
For case 2 and 3 of the fixup, after one iteration of this case, two red nodes will be left in the tree.
13.36
Suggest how to implement RBInsert efficiently if the representation for redblack trees includes no storage for parent pointers.
I can do it recursively.
List of common symbols:
ΓΞΞΞ©Ξ±Ξ²Ξ³Ξ΄Ξ΅ΟΟΟΟ΅ββββββ₯β¦β²ββββ€β±βββββ£βββ βββββ§β¨β©βͺβ β€β₯ββ β―βββββββββββββ€β¬β΄βΌββ β¨β©
VIII Appendix: Mathematical Background
C Counting and Probability
C.2 Probability
C.21
Professor Rosencrantz flips a fair coin once. Professor Guildenstern flips a fair coin twice. What is the probability that Professor Rosencrantz obtains more heads than Professor Guildenstern?
S = { (H, HH), (H, HT), (H, TH), (H, TT), (T, HH), (T, HT), (T, TH), (T, TT) }.
A = { (H, TT) }.
Pr{A} = 1 / 8.
C.22
Prove Booleβs inequality: For any finite or countably infinite sequence of events $A_1$, $A_2$, β¦,
Pr {$A_1$ βͺ $A_2$ βͺ β―} β€ Pr{$A_1$} + Pr{$A_2$} + β―. (C.19)
Proof by induction:
Base case: Pr{$A_1$} β€ Pr{$A_1$}.
Inductive case:
$\Pr\left\lbrace\left(\bigcup_{i = 1}^j A_i\right) βͺ A_{i + 1}\right\rbrace$
β€ $\Pr\left\lbrace\bigcup_{i = 1}^j A_i\right\rbrace + \Pr\left\lbrace A_{i + 1}\right\rbrace$
β€ $β_{i = 1}^j \Pr\left\lbrace A_i\right\rbrace + \Pr\left\lbrace A_{i + 1}\right\rbrace$ (By induction)
= $β_{i = 1}^{j + 1} \Pr\left\lbrace A_i\right\rbrace$.
C.23
Suppose we shuffle a deck of 10 cards, each bearing a distinct number from 1 to 10, to mix the cards thoroughly. We then remove three cards, one at a time, from the deck. What is the probability that we select the three cards in sorted (increasing) order?
The order of the selected cards is independent of the number of cards, so the probability is 1 / 3! = 1 / 6.
C.24
Prove that Pr{A  B} + Pr{$\bar{A}$  B} = 1.
Pr{A  B} + Pr{$\bar{A}$  B}
= Pr{A β© B} / Pr{B} + Pr{$\bar{A}$ β© B} / Pr{B}
= (Pr{A β© B} + Pr{$\bar{A}$ β© B}) / Pr{B}
= Pr{(A β© B) βͺ ($\bar{A}$ β© B)} / Pr{B} (Since A and $\bar{A}$ are mutually exclusive)
= Pr{B} / Pr{B}
= 1.
C.25
Prove that for any collection of events $A_1$, $A_2$, β¦, $A_n$,
$\begin{aligned} \Pr\left\lbrace A_1 \cap A_2 \cap β― \cap A_n\right\rbrace = &\Pr\left\lbrace A_1\right\rbrace β \Pr\left\lbrace A_2 \middle A_1\right\rbrace β \Pr\left\lbrace A_3 \middle A_1 \cap A_2\right\rbrace β―\ &\Pr\left\lbrace A_n \middle A_1 \cap A_2 \cap β― \cap A_{n  1}\right\rbrace\text{.} \end{aligned}$
Proof by induction:
Base case: $\Pr\left\lbrace A_1\right\rbrace = \Pr\left\lbrace A_1\right\rbrace$.
Inductive case: By induction, we have:
$\Pr\left\lbrace β_{i = 1}^n A_i\right\rbrace = β_{i = 1}^n \Pr\left\lbrace A_i \middle β_{j = 1}^{i  1} A_j \right\rbrace$.
So
$\Pr\left\lbrace β_{i = 1}^{n + 1} A_i\right\rbrace$
= $\Pr\left\lbrace\left(β_{i = 1}^n A_i\right) \cap A_{n + 1}\right\rbrace$
= $\Pr\left\lbrace β_{i = 1}^n A_i\right\rbrace β
\Pr\left\lbrace A_{n + 1} \middle β_{i = 1}^n A_i\right\rbrace$
= $\left(β_{i = 1}^n \Pr\left\lbrace A_i \middle β_{j = 1}^{i  1} A_j \right\rbrace\right) β
\Pr\left\lbrace A_{n + 1} \middle β_{i = 1}^n A_i\right\rbrace$
= $β_{i = 1}^{n + 1} \Pr\left\lbrace A_i \middle β_{j = 1}^{i  1} A_j \right\rbrace$.
C.26 β
Describe a procedure that takes as input two integers a and b such that 0 < a < b and, using fair coin flips, produces as output heads with probability a / b and tails with probability (b  a) / b. Give a bound on the expected number of coin flips, which should be O(1). (Hint: Represent a / b in binary.)
Solution is implemented here.
The expected number of coin flips is 2.
C.27 β
Show how to construct a set of n events that are pairwise independent but such that no subset of k > 2 of them is mutually independent.
Skipped.
C.28 β
Two events A and B are conditionally independent, given C, if
Pr{A β© B  C} = Pr{A  C} β Pr{B  C}.
Give a simple but nontrivial example of two events that are not independent but are conditionally independent given a third event.
Skipped.
C.29 β
You are a contestant in a game show in which a prize is hidden behind one of three curtains. You will win the prize if you select the correct curtain. After you have picked one curtain but before the curtain is lifted, the emcee lifts one of the other curtains, knowing that it will reveal an empty stage, and asks if you would like to switch from your current selection to the remaining curtain. How would your chances change if you switch? (This question is the celebrated Monty Hall problem, named after a gameshow host who often presented contestants with just this dilemma.)
The winning chance changes from 1 / 3 to 2 / 3.
C.210 β
A prison warden has randomly picked one prisoner among three to go free. The other two will be executed. The guard knows which one will go free but is forbidden to give any prisoner information regarding his status. Let us call the prisoners X, Y, and Z. Prisoner X asks the guard privately which of Y or Z will be executed, arguing that since he already knows that at least one of them must die, the guard wonβt be revealing any information about his own status. The guard tells X that Y is to be executed. Prisoner X feels happier now, since he figures that either he or prisoner Z will go free, which means that his probability of going free is now 1 / 2. Is he right, or are his chances still 1 / 3? Explain.
Still 1 / 3. Like the previous exercise, the chance of prisoner Z will go free is 2 / 3 after the guard says Y will be executed.
C.3 Discrete random variables
C.31
Suppose we roll two ordinary, 6sided dice. What is the expectation of the sum of the two values showing? What is the expectation of the maximum of the two values showing?
E[X + Y] = E[X] + E[Y] = 7 / 2 + 7 / 2 = 7.
According to equation C.25:
E[max(X, Y)]
= $β_{i = 1}^β \Pr\left\lbrace \max\left(X, Y\right) β₯ i\right\rbrace$
= $β_{i = 1}^6 \Pr\left\lbrace \max\left(X, Y\right) β₯ i\right\rbrace$
= $β_{i = 1}^6 \Pr\left\lbrace X β₯ i β¨ Y β₯ i\right\rbrace$
= $β_{i = 1}^6 \Pr\left\lbrace X β₯ i\right\rbrace + \Pr\left\lbrace Y β₯ i\right\rbrace  \Pr\left\lbrace X β₯ i β§ Y β₯ i\right\rbrace$
= $β_{i = 1}^6 (7  i) / 6 + (7  i) / 6  (7  i)^2 / 36$
= 161 / 36.
C.32
An array A[1β₯n] contains n distinct numbers that are randomly ordered, with each permutation of the n numbers being equally likely. What is the expectation of the index of the maximum element in the array? What is the expectation of the index of the minimum element in the array?
E[arg max(A)] = (1 + n) / 2.
E[arg min(A)] = (1 + n) / 2.
C.33
A carnival game consists of three dice in a cage. A player can bet a dollar on any of the numbers 1 through 6. The cage is shaken, and the payoff is as follows. If the playerβs number doesnβt appear on any of the dice, he loses his dollar. Otherwise, if his number appears on exactly k of the three dice, for k = 1, 2, 3, he keeps his dollar and wins k more dollars. What is his expected gain from playing the carnival game once?
E
=  Pr{k = 0} + $β_{i = 1}^3 i \Pr\left\lbrace k = i\right\rbrace$
=  125 / 216 + $β_{i = 1}^3 i \binom{3}{i} \left(1 / 6\right) ^ i \left(5 / 6\right) ^ {3  i}$
=  125 / 216 + 1 Γ 3 Γ 1 / 6 Γ 25 / 36 + 2 Γ 3 Γ 1 / 36 Γ 5 / 6 + 3 Γ 1 Γ 1 / 216 Γ 1
=  17 / 216.
So, do not gamble.
C.34
Argue that if X and Y are nonnegative random variables, then
E[max(X, Y)] β€ E[X] + E[Y].
Since X and Y are nonnegative, E[max(X, Y)] β€ E[X + Y] = E[X] + E[Y].
C.35 β
Let X and Y be independent random variables. Prove that f(X) and g(Y) are independent for any choice of functions f and g.
Skipped.
C.36 β
Let X be a nonnegative random variable, and suppose that E[X] is well defined. Prove Markovβs inequality:
Pr{X β₯ t} β€ E[X] / t (C.30)
for all t > 0.
Skipped.
C.37 β
Let S be a sample space, and let X and Xβ² be random variables such that X(s) β₯ Xβ²(s) for all s β S. Prove that for any real constant t,
Pr{X β₯ t} β₯ Pr{Xβ² β₯ t}.
Skipped.
C.38
Which is larger: the expectation of the square of a random variable, or the square of its expectation?
E[$X^2$]  $\operatorname{E}^2\left[Y\right]$
= E[$X^2$]  $\operatorname{E}^2\left[X\right]$
= Var[X]
β₯ 0
C.39
Show that for any random variable X that takes on only the values 0 and 1, we have Var[X] = E[X] E[1  X].
Since X takes on only the values 0 and 1, we have $X^2$ = X.
Var[X]
= E[$X^2$]  $\operatorname{E}^2\left[X\right]$
= E[X]  $\operatorname{E}^2\left[X\right]$
= E[X](1  E[X])
= E[X]E[1  X]
C.310
Prove that Var[a X] = $a^2$ Var[X] from the definition (C.27) of variance.
Var[a X]
= E[$a^2 X^2$]  $\operatorname{E}^2\left[a X\right]$
= $a^2$ E[$X^2$]  $a^2 \operatorname{E}^2\left[X\right]$
= $a^2$(E[$X^2$]  $\operatorname{E}^2\left[X\right]$)
= $a^2$ Var[X].