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.1-1

Give a real-world example that requires sorting or a real-world example that requires computing a convex hull.

Skipped.

1.1-2

Other than speed, what other measures of efficiency might one use in a real-world setting?

Memory consumption.

1.1-3

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.1-4

How are the shortest-path and traveling-salesman problems given above similar? How are they different?

They both need to minimize the total distance for travelling. But shortest-path is to find the shortest path between only two locations, while traveling-salesman is to find the shortest path containing all given locations.

1.1-5

Come up with a real-world 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.2-1

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.2-2

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.2-3

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

1-1 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

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.1-1

Using Figure 2.2 as a model, illustrate the operation of Insertion-Sort on the array A = ⟨31, 41, 59, 26, 41, 58⟩.

Skipped.

2.1-2

Rewrite the Insertion-Sort procedure to sort into nonincreasing instead of nondecreasing order.

Just change A[i] > key to A[i] < key in the original code.

2.1-3

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.

Linear-Search(A, v)

1. for i = 1 to A.length
2.     if A[i] == v
3.         return i
4. 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.1-4

Consider the problem of adding two n-bit binary integers, stored in two n-element 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:

Add-Binary(A, B, C)

1. carry = 0
2. for i = 1 to A.length
3.     sum = A[n - i] + B[n - i] + carry
4.     C[n + 1 - i] = sum mod 2
5.     carry = sum / 2
6. C[0] = carry

2.2 Analyzing algorithms

2.2-1

Express the function \(n^3\) / 1000 - 100 \(n^2\) - 100 n + 3 in terms of Θ-notation.

Θ(\(n^3\)).

2.2-2

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 best-case and worst-case 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.

Best-case and worst-case running times are both Θ(\(n^2\)).

2.2-3

Consider linear search again (see Exercise 2.1-3). 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 average-case and worst-case 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.2-4

How can we modify almost any algorithm to have a good best-case 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.3-1

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.3-2

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.3-3

Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence

T(n) = \(\begin{cases} 2 &\text{if $n = 2$,} \\ 2 T(n / 2) + n &\text{if $n = 2^k$, for $k > 1$} \end{cases}\)

is T(n) = n lg n.

• Base case: If n = 2, T(n) = 2. Since n lg n = 2 lg 2 = 2, T(n) = n lg n, so the claim holds.
• Inductive case: If n > 2, T(n) = 2 T(n / 2) + n, by induction, we know that T(n / 2) = (n / 2) lg (n / 2), so T(n) = 2 (n / 2) lg (n / 2) + n = n lg (n / 2) + n = n (lg n - 1) + n = n lg n, The claim holds.

2.3-4

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 worst-case running time of this recursive version of insertion sort.

See here for implementation.

\[T(n) = \begin{cases} 1 &\text{if $n < 2$} \\ T(n - 1) + Θ(n) &\text{if $n >= 2$)} \end{cases}\]

2.3-5

Referring back to the searching problem (see Exercise 2.1-3), 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 worst-case running time of binary search is Θ(lg n).

See here for implementation.

Binary-Search(A, v)

1. left = 1
2. right = A.length + 1
3. while left < right
4.     middle = ⌊(left + right) / 2⌋
5.     if A[middle] < v
6.         left = middle + 1
7.     else
8.         right = middle
9. if left ≤ A.length and A[left] == v
10.     return left
11. else
12.     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.3-6

Observe that the while loop of lines 5–7 of the Insertion-Sort 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.3-5) instead to improve the overall worst-case 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 worst-case scenario, which takes Θ(n) time.

2.3-7 ★

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

2-1 Insertion sort on small arrays in merge sort

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

1. Show that insertion sort can sort the n / k sublists, each of length k, in Θ(n k) worst-case time.
2. Show how to merge the sublists in Θ(n lg (n / k)) worst-case time.
3. Given that the modified algorithm runs in Θ(n k + n lg (n / k)) worst-case time, what is the largest value of k as a function of n for which the modified algorithm has the same running time as standard merge sort, in terms of Θ-notation?
4. How should we choose k in practice?

1. Sort a sublist of length k takes \(k^2\) time, so sorting n / k sublists takes (n / k) Θ(\(k^2\)) = Θ((n / k) \(k^2\)) = Θ(n k) time.
2. Assume merging n sublists takes T(n) time, we have T(n) = 2 T(n) + \(c_1\) n, if n > 1. Also, T(n) = \(c_2\), if n = 1. Notice this is the same as equation 2.1 and 2.2. So we have T(n) = Θ(n lg n). So merging n / k sublists takes T(n / k) = Θ((n / k) lg (n / k)) = Θ(n lg (n / k)).
3. We need to solve the equation n k + n lg (n / k) < c n lg (n). We can get k - lg k < (c - 1) lg n from it. I think k < Θ(lg n), but I can’t prove it.
4. With benchmarks and profiling.

2-2 Correctness of bubblesort

Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order.

Bubblesort(A)

1. for i = 1 to A.length - 1
2.     for j = A.length downto i + 1
3.         if A[j] < A[j - 1]
4.             exchange A[j] with A[j - 1]

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).

2. 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.

3. 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.

4. What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?

1. We also need to prove that the elements in A is the same as in A′.

2. 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].

3. 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.

4. Worst-case running time is Θ(\(n^2\)), it is the same as insertion sort. But insertion sort have a best-case running time which is Θ(n), while the best-case running time of bubble sort is still Θ(\(n^2\)).

2-3 Correctness of Horner’s rule

The following code fragment implements Horner’s rule for evaluating a polynomial

\(\begin{aligned} P(x) &= ∑_{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:

1. y = 0
2. for i = n downto 0
3.     y = \(a_i\) + x ⋅ y

1. In terms of Θ-notation, what is the running time of this code fragment for Horner’s rule?

2. Write pseudocode to implement the naive polynomial-evaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare to Horner’s rule?

3. Consider the following loop invariant:

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

   y = \(\displaystyle ∑_{k = 0}^{n - (i + 1)} 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\).

4. 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.

1. Θ(n).

2. The pseudocode:

   1. y = 0
   2. for i = 0 to n
   3.     p = \(a_i\)
   4.     for j = 0 to i
   5.         p = p ⋅ x
   6.     y = y + p

   The running time of this algorithm is Θ(\(n^2\)). It takes more time than Horner’s rule.

3. Proof:

   • Initialization: Before the first iteration, i = n, y = \(∑_{k = 0}^{n - (i + 1)} 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 - (i + 1)} a_{k + i + 1} x^k\right) = a_i ⋅ x^0 + ∑_{k = 0}^{n - (i + 1)} 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 - ((-1) + 1)} a_{k + (-1) + 1} x^k = ∑_{k = 0}^n a_k x^k\).

4. I thought I have proved it at step 3.

2-4 Inversions

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

1. List the five inversions of the array ⟨2, 3, 8, 6, 1⟩.
2. What array with elements from the set {1, 2, …, n} has the most inversions? How many does it have?
3. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
4. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ(n lg n) worst-case time. (Hint: Modify merge sort.)

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

2. The array ⟨n, …, 2, 1⟩ has the most inversions. It has n × (n - 1) / 2 inversions.

3. 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 = Θ(k)\).

4. See here for implementation.

3 Growth of Functions

3.1 Asymptotic notation

3.1-1

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.1-2

Show that for any real constants a and b, where b > 0,

\((n + a)^b\) = Θ(\(n^b\)). (3.2)

We want to find constant \(c_1\), \(c_2\) and \(n_0\) so that if n > \(n_0\), \(c_1 n^b ≤ (n + a)^b ≤ c_2 n^b\).

\(c_1 n^b ≤ (n + a)^b ≤ c_2 n^b\)
⇔ \(\left({c_1}^{1 / b}\right)^b n^b ≤ (n + a)^b ≤ \left({c_2}^{1 / b}\right)^b n^b\)
⇔ \(\left({c_1}^{1 / b} n\right)^b ≤ (n + a)^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(-2 a, a). So \(n_0\) can be max(-2 a, a).

Formally, for any n > max(-2 a, a), \(\left(\frac{1}{2}\right)^b n^b ≤ (n + a)^b ≤ 2^b n^b\), \(n + a)^b = Θ(n^b)\).

3.1-3

Explain why the statement, “The running time of algorithm A is at least O(\(n^2\)),” is meaningless.

It is like saying x is at least less than or equal to 10.

3.1-4

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.1-5

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.1-6

Prove that the running time of an algorithm is Θ(g(n)) if and only if its worst-case running time is O(g(n)) and its best-case 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 worst-case running time is bounded by c2 g(n), and the best-case running time is bounded by c1 g(n). So the worst-case running time is O(g(n)), and the best-case running time is Ω(g(n)).

If the worst-case 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 best-case 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 worst-cast running time and the best-case running time, the running time is bounded by c1 g(n) c2 g(n), so the running time is Θ(g(n)).

3.1-7

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.1-8

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.2-1

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.

1. m ≤ n ⇒ (f(m) ≤ f(n)) ∧ (g(m) ≤ g(n)) ⇒ f(m) + g(m) ≤ f(n) + g(n).
2. m ≤ n ⇒ g(m) ≤ g(n) ⇒ f(g(m)) ≤ f(g(n)).
3. (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.2-2

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.2-3

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 \pi n} \left(\frac{n}{e}\right)^n \left(1 + \frac{c_1}{n}\right) ≤ n! ≤ \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n \left(1 + \frac{c_2}{n}\right)\)

So

\(\ln \left(\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n \left(1 + \frac{c_1}{n}\right)\right) ≤ \ln (n!) ≤ \ln \left(\sqrt{2 \pi 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 \pi n} \left(1 + \frac{c_1}{n}\right)\right) ≤ \ln (n!) ≤ \ln \left(\left(\frac{n}{e}\right)^n\right) + \ln \left(\sqrt{2 \pi n} \left(1 + \frac{c_2}{n}\right)\right)\)
⇒ \(n \ln \left(\frac{n}{e}\right) + \ln \left(\sqrt{2 \pi n} \left(1 + \frac{c_1}{n}\right)\right) ≤ \ln (n!) ≤ n \ln \left(\frac{n}{e}\right) + \ln \left(\sqrt{2 \pi n} \left(1 + \frac{c_2}{n}\right)\right)\)
⇒ \(n \left(\ln n - 1\right) + \ln \left(\sqrt{2 \pi n} \left(1 + \frac{c_1}{n}\right)\right) ≤ \ln (n!) ≤ n \left(\ln n - 1\right) + \ln \left(\sqrt{2 \pi n} \left(1 + \frac{c_2}{n}\right)\right)\)
⇒ \(n \ln n - n + \ln \left(\sqrt{2 \pi n} \left(1 + \frac{c_1}{n}\right)\right) ≤ \ln (n!) ≤ n \ln n - n + \ln \left(\sqrt{2 \pi n} \left(1 + \frac{c_2}{n}\right)\right)\)
⇒ \(n \ln n - n + \frac{1}{2} \ln {(2 \pi n)} + \ln {\left(1 + \frac{c_1}{n}\right)} ≤ \ln (n!) ≤ n \ln n - n + \frac{1}{2} \ln {(2 \pi n)} + \ln {\left(1 + \frac{c_2}{n}\right)}\).

So we have ln(n!) = Ω(n ln n), and ln(n!) = O(n ln n), so ln(n!) = Θ(n ln n).

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.2-4 ★

Is the function ⌈lg n⌉! polynomially bounded? Is the function ⌈lg lg n⌉! polynomially bounded?

Skipped.

3.2-5 ★

Which is asymptotically larger: lg(\(\lg^* n\)) 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.2-6

Show that the golden ratio ϕ and its conjugate \(\hat{\phi}\) both satisfy the equation \(x^2 = x + 1\).

\(\phi^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 = \phi + 1\).

\(\hat{\phi}^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{\phi} + 1\).

3.2-7

Prove by induction that the ith Fibonacci number satisfies the equality

\(F_i = \dfrac{\phi^i - \hat{\phi}^i}{\sqrt{5}}\),

where ϕ is the golden ratio and \(\hat{\phi}\) is its conjugate.

Base cases:

• If i = 0, \(\frac{\phi^i - \hat{\phi}^i}{\sqrt{5}} = \frac{1 - 1}{\sqrt{5}} = 0\), the claim holds.
• If i = 1, \(\frac{\phi^i - \hat{\phi}^i}{\sqrt{5}} = \frac{\phi - \hat{\phi}}{\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{\phi^{i - 2} - \hat{\phi}^{i - 2}}{\sqrt{5}}\) and \(F_{i - 1} = \frac{\phi^{i - 1} - \hat{\phi}^{i - 1}}{\sqrt{5}}\). So \(F_i = F_{i - 2} + F_{i - 1} = \frac{\phi^{i - 2} - \hat{\phi}^{i - 2}}{\sqrt{5}} + \frac{\phi^{i - 1} - \hat{\phi}^{i - 1}}{\sqrt{5}} = \frac{\phi^{i - 2} (1 + \phi) - \hat{\phi}^{i - 2} \left(1 + \hat{\phi}\right)}{\sqrt{5}}\). Base on the conclusion of exercise 3.2-6, we have \(1 + \phi = \phi^2\) and \(1 + \hat{\phi} = \hat{\phi}^2\), so \(F_i = \frac{\phi^{i - 2} \phi^2 - \hat{\phi}^{i - 2} \hat{\phi}^2}{\sqrt{5}} = \frac{\phi^i - \hat{\phi}^i}{\sqrt{5}}\), the claim holds.

3.2-8

Show that k ln k = Θ(n) implies k = Θ(n / ln n).

Skipped.

3.X Problems

3-1 Asymptotic behavior of polynomials

Let

p(n) = \(\displaystyle ∑_{i=0}^d a_i n^i\),

where \(a_d\) > 0, be a degree-d polynomial in n, and let k be a constant. Use the definitions of the asymptotic notations to prove the following properties.

1. If k ≥ d, then p(n) = O(\(n^k\)).
2. If k ≤ d, then p(n) = Ω(\(n^k\)).
3. If k = d, then p(n) = Θ(\(n^k\)).
4. If k > d, then p(n) = o(\(n^k\)).
5. If k < d, then p(n) = ω(\(n^k\)).

Skipped.

3-2 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(n!)	\(\lg\left(n^n\right)\)

3-3 Ordering by asymptotic growth rates

1. 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\) = Ω(\(g_2\)), \(g_2\) = Ω(\(g_3\)), …, \(g_{29}\) = Ω(\(g_{30}\)). Partition your list into equivalence classes such that functions f(n) and g(n) are in the same class if and only if f(n) = Θ(g(n)).

   \(\lg\left(\lg^* n\right)\)	\(2^{\lg^* n}\)	\(\left(\sqrt{2}\right)^{\lg n}\)	\(n^2\)	n!	lg n!
   \(\left(\frac{3}{2}\right)^n\)	\(n^3\)	\(\lg^2 n\)	lg(n!)	\(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}\)	(n + 1)!	\(\sqrt{\lg n}\)
   \(\lg^*\left(\lg n\right)\)	\(2^{\sqrt{2 \lg n}}\)	n	\(2^n\)	n lg n	\(2^{2^{n + 1}}\)

2. Give an example of a single nonnegative function f(n) such that for all functions \(g_i(n)\) in part (a), f(n) is neither \(O\left(g_i(n)\right)\) nor \(Ω\left(g_i(n)\right)\).

Skipped.

3-4 Asymptotic notation properties

Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.

1. f(n) = O(g(n)) implies g(n) = O(f(n)).
2. f(n) + g(n) = Θ(min(f(n), g(n))).
3. 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.
4. f(n) = O(g(n)) implies \(2^{f(n)} = O\left(2^{g(n)}\right)\).
5. f(n) = O(\((f(n))^2\)).
6. f(n) = O(g(n)) implies g(n) = Ω(f(n)).
7. f(n) = Θ(f(n / 2)).
8. f(n) + o(f(n)) = Θ(f(n)).

Too lazy to prove. Just list my guessing here.

1. False.
2. False.
3. Not sure.
4. Not sure.
5. Not sure.
6. True.
7. False.
8. True.

3-5 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(n) = \(\overset{∞}{Ω}\)(g(n)) if there exists a positive constant c such that f(n) ≥ c g(n) ≥ 0 for infinitely many integers n.

1. Show that for any two functions f(n) and g(n) that are asymptotically nonnegative, either f(n) = O(g(n)) or f(n) = \(\overset{∞}{Ω}\)(g(n)) or both, whereas this is not true if we use Ω in place of \(\overset{∞}{Ω}\).
2. 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(n) = O′(g(n)) if and only if |f(n)| = O(g(n)).

1. 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 “soft-oh”) to mean O with logarithmic factors ignored:

\(\widetilde{O}(g(n))\) = {f(n) : there exist positive constants c, k, and \(n_0\) such that \(0 ≤ f (n) ≤ c g(n) \lg^k(n)\) for all \(n ≥ n_0\)}.

1. Define \(\widetilde{Ω}\) and \(\widetilde{Θ}\) in a similar manner. Prove the corresponding analog to Theorem 3.1.

Skipped.

3-6 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^*(n) = \min \lbrace i ≥ 0 : f^{(i)}(n) ≤ c \rbrace\),

which need not be well defined in all cases. In other words, the quantity \(f_c^*(n)\) 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^*(n)\).

4 Divide-and-Conquer

4.1 The maximum-subarray problem

4.1-1

What does Find-Maximum-Subarray return when all elements of A are negative?

An array containing the single maximum element of the original array.

4.1-2

Write pseudocode for the brute-force method of solving the maximum-subarray problem. Your procedure should run in Θ(\(n^2\)) time.

Find-Maximum-Subarray-Brute-Force(A)

1. max-left = 0
2. max-right = 0
3. max-sum = -∞
4. for i = 1 to A.Length
5.     sum = 0
6.     for j = i to A.Length
7.         sum = sum + A[j]
8.         if sum > max-sum
9.             max-left = i
10.             max-right = j
11.             max-sum = sum
12. return (max-left, max-right, max-sum)

4.1-3

Implement both the brute-force and recursive algorithms for the maximum-subarray problem on your own computer. What problem size \(n_0\) gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than \(n_0\). Does that change the crossover point?

See here for recursive implementation.

See here for brute-force implementation.

Skipped crossover point test for now.

4.1-4

Suppose we change the definition of the maximum-subarray 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.1-5

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray 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.2-1

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.2-2

Write pseudocode for Strassen’s algorithm.

Skipped.

4.2-3

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.2-4

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.2-5

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 divide-and-conquer matrix-multiplication algorithm? How does it compare to Strassen’s algorithm?

Skipped.

4.2-6

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.2-7

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.3-1

Show that the solution of T(n) = T(n - 1) + n is O(\(n^2\)).

T(n)
= T(n - 1) + n
≤ c \((n - 1)^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.3-2

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.3-3

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.3-4

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.3-5

Show that Θ(n lg n) is the solution to the “exact” recurrence (4.3) for merge sort.

Skipped.

4.3-6

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.3-7

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 lower-order 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 \((n / 3)^{\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.3-8

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 lower-order term to make a substitution proof work.

Suppose T(n) = c \(n^2\) - n, we have

T(n)
= 4 (c \((n / 2)^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.3-9

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 recursion-tree method for solving recurrences

4.4-1

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 \((n / 2)^{\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.4-2

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) \((n / 2)^2\) + \(n^2\)
= c + (1 / 3) \(n^2\) + \(n^2\)
= c + (4 / 3) \(n^2\).

4.4-3

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 \((n / 2 + 2)^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.4-4

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.4-5

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.4-6

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.4-7

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.4-8

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)) \((n - a)^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.4-9

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.4-6, 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.5-1

Use the master method to give tight asymptotic bounds for the following recurrences.

1. T(n) = 2 T(n / 4) + 1.
2. T(n) = 2 T(n / 4) + \(\sqrt{n}\).
3. T(n) = 2 T(n / 4) + n.
4. T(n) = 2 T(n / 4) + \(n^2\).

1. T(n) = Θ(\(\sqrt{n}\)).
2. T(n) = Θ(\(\sqrt{n}\) lg n).
3. T(n) = Θ(n).
4. T(n) = Θ(\(n^2\)).

4.5-2

Professor Caesar wishes to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen’s algorithm. His algorithm will use the divide-and-conquer 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.5-3

Use the master method to show that the solution to the binary-search recurrence T(n) = T(n / 2) + Θ(1) is T(n) = Θ(lg n). (See Exercise 2.3-5 for a description of binary search.)

Since Θ(1) = Θ(\(n^{\log_2 1}\)), T(n) = Θ(\(n^{\log_2 1}\) lg n) = Θ(lg n).

4.5-4

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.5-5 ★

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.6-1 ★

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 ⌊f(⌊x⌋)⌋ + 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.6-2 ★

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.6-3 ★

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) Ω(\((n / b)^{\log_b a - \log_b c}\))
= (a / c) Ω(\(n^{\log_b a - \log_b c} / (a / c)\))
= Ω(\(n^{\log_b a - \log_b c}\)).

4.X Problems

4-1 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.

1. T(n) = 2 T(n / 2) + \(n^4\).
2. T(n) = T(7 n / 10) + n.
3. T(n) = 16 T(n / 4) + \(n^2\).
4. T(n) = 7 T(n / 3) + \(n^2\).
5. T(n) = 7 T(n / 2) + \(n^2\).
6. T(n) = 2 T(n / 4) + \(\sqrt{n}\)
7. T(n) = T(n - 2) + \(n^2\).

1. T(n) = c n + (8 / 7) \(n^4\).
2. T(n) = (10 / 3) n + c.
3. T(n) = \(n^2 \log_4 n\) + c \(n^2\).
4. T(n) = (9 / 2) \(n^2\) + c \(n^{\log_3 7}\).
5. T(n) = c \(n^{\lg 7}\) - (4 / 3) \(n^2\).
6. T(n) = \(\sqrt{n} \log_4 n\) + c \(\sqrt{n}\).
7. T(n) = \(n^3\) / 6 + \(n^2\) / 2 + n / 3 + c.

4-2 Parameter-passing costs

Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an N-element 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 parameter-passing strategies:

1. An array is passed by pointer. Time = Θ(1).
2. An array is passed by copying. Time = Θ(N), where N is the size of the array.
3. 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.

1. Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 2.3-5). Give recurrences for the worst-case 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.
2. Redo part (a) for the Merge-Sort algorithm from Section 2.3.1.

1. Binary search algorithm

   1. By pointer: T(n) = T(n / 2) + Θ(1).

      T(N) = Θ(lg N).

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

      T(N) = Θ(N lg N).

   3. By copying subrange: T(n) = T(n / 2) + Θ(n).

      T(N) = Θ(N).

2. Merge sort algorithm

   1. By pointer: T(n) = 2 T(n / 2) + Θ(n).

      T(N) = Θ(N lg N).

   2. 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\)).

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

4-3 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.

1. T(n) = 4 T(n / 3) + n lg n.
2. T(n) = 3 T(n / 3) + n / lg n.
3. T(n) = 4 T(n / 2) + \(n^2 \sqrt{n}\).
4. T(n) = 3 T(n / 3 - 2) + n / 2.
5. T(n) = 2 T(n / 2) + n / lg n.
6. T(n) = T(n / 2) + T(n / 4) + T(n / 8) + n.
7. T(n) = T(n - 1) + 1 / n.
8. T(n) = T(n - 1) + lg n.
9. T(n) = T(n - 2) + 1 / lg n.
10. T(n) = \(\sqrt{n}\) T(\(\sqrt{n}\)) + n

1. T(n) = c \(n^{\log_3 4}\) - 3 n lg n - 12 n lg 3.
2. T(n) = Θ(n), according to exercise 4.6-2.
3. T(n) = (2 + \(\sqrt{2}\)) \(n^{5 / 2}\) + c \(n^2\).
4. T(n) = (1 / 2) n \(\log_3 (n + 3)\) + c n + (3 / 2) \(\log_3 (n + 3)\) + 3 c + 3 / 4.
5. T(n) = Θ(n), according to exercise 4.6-2.
6. T(n) = 8 n.
7. T(n) = c + \(∑_{j = 2}^n (1 / j)\) = Θ(lg n).
8. T(n) = c + \(∑_{j = 2}^n \lg n\) = c + \(\lg ∏_{j = 2}^n n\) = c + lg n! = Θ(n lg n).
9. Skipped.
10. T(n) = n lg lg n + c n.

4-4 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} ℱ(z) &= \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.

1. Show that ℱ(z) = z + z ℱ(z) + \(z^2\) ℱ(z).

2. Show that

   \(\begin{aligned} ℱ(z) &= \frac{z}{1 - z - z^2}\\ &= \frac{z}{(1 - \phi z)\left(1 - \hat{\phi} z\right)}\\ &= \frac{1}{\sqrt{5}}\left(\frac{1}{1 - \phi z} - \frac{1}{1 - \hat{\phi} z}\right), \end{aligned}\)

   where

   ϕ = \(\dfrac{1 + \sqrt{5}}{2}\) = 1.61803…

   and

   \(\hat{\phi}\) = \(\dfrac{1 - \sqrt{5}}{2}\) = -1.61803….

3. Show that

   ℱ(z) = \(\displaystyle ∑_{i = 0}^∞ \frac{1}{\sqrt{5}}\left(\phi^i - \hat{\phi}^i\right) z^i\).

4. Use part (c) to prove that \(F_i = \phi^i / \sqrt{5}\) for i > 0, rounded to the nearest integer. (Hint: Observe that |\(\hat{\phi}\)| < 1.)

1. By definition:

   \(\begin{aligned} z + z ℱ(z) + z^2 ℱ(z) &= 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\\ &= ℱ(z). \end{aligned}\)

2. ℱ(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{\phi}\) z))
   = z / (1 - (ϕ + \(\hat{\phi}\)) z + ϕ \(\hat{\phi} z^2\))
   = z / (1 - z - \(z^2\))
   = ℱ(z).

   \(\frac{1}{\sqrt{5}} \left(\frac{1}{1 - \phi z} - \frac{1}{1 - \hat{\phi} z}\right)\)
   = \(\frac{1}{\sqrt{5}} \frac{\left(1 - \hat{\phi} z\right) - (1 - \phi z)}{(1 - \phi z) \left(1 - \hat{\phi} z\right)}\)
   = \(\frac{1}{\sqrt{5}} \frac{\left(\phi - \hat{\phi}\right) z}{(1 - \phi z) \left(1 - \hat{\phi} z\right)}\)
   = \(\frac{1}{\sqrt{5}} \frac{\sqrt{5} z}{(1 - \phi z) \left(1 - \hat{\phi} z\right)}\)
   = \(\frac{z}{(1 - \phi z) \left(1 - \hat{\phi} 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: \(ℱ(1) = ∑_{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?

3. \(∑_{i = 0}^∞ \frac{1}{\sqrt{5}}\left(\phi^i - \hat{\phi}^i\right) z^i\)
   = \(\frac{1}{\sqrt{5}} ∑_{i = 0}^∞ \left(\phi^i - \hat{\phi}^i\right) z^i\)
   = \(\frac{1}{\sqrt{5}} \left(∑_{i = 0}^∞ (\phi z)^i - ∑_{i = 0}^∞ \left(\hat{\phi} z\right)^i\right)\)
   = \(\frac{1}{\sqrt{5}} \left(\frac{1}{1 - \phi z} - \frac{1}{1 - \hat{\phi} z}\right)\)
   = ℱ(z).

4. \(F_i = \frac{1}{\sqrt{5}}\left(\phi^i - \hat{\phi}^i\right) = \phi^i / \sqrt{5} - \hat{\phi}^i / \sqrt{5}\)
   ⇒ \(F_i - \phi^i / \sqrt{5} = - \hat{\phi}^i / \sqrt{5}\).

   Since \(\left|- \hat{\phi}^i / \sqrt{5}\right|\) < 0.5, and \(F_i\) is an integer, \(F_i = \phi^i / \sqrt{5}\), rounded to the nearest integer.

4-5 Chip testing

Professor Diogenes has n supposedly identical integrated-circuit 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

1. 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.
2. 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.
3. 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.

1. 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.

2. 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.

3. 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.

4-6 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 upper-left and lower-right elements is less than or equal to the sum of the lower-left and upper-right 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

1. 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.)

2. 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

3. 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.

4. Here is a description of a divide-and-conquer 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 even-numbered rows of A. Recursively determine the leftmost minimum for each row of A′. Then compute the leftmost minimum in the odd-numbered rows of A.

   Explain how to compute the leftmost minimum in the odd-numbered rows of A (given that the leftmost minimum of the even-numbered rows is known) in O(m + n) time.

5. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is O(m + n log m).

1. 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]

2. Result:

   37	23	24	32
   21	6	7	10
   53	34	30	31
   32	13	9	6
   43	21	15	8

3. 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.

4. 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} (f(2 i + 2) - f(2 i) + 1)\))
     = Θ(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}^{(m - 3) / 2} (f(2 i + 2) - f(2 i) + 1)\) + (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 odd-numbered rows is O(m + n).

5. 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} (1 / 2)^i + ∑_{i=0}^{\lg m - 1} n\))
   = Θ(1) + O(m (1 - \((1 / 2)^{\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.1-1

Show that the assumption that we are always able to determine which candidate is best, in line 4 of procedure Hire-Assistant, 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.1-2 ★

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 (b - a + 1)\right\rceil}\) / (b - a + 1).
⇒ T(a, b) = Θ(n \(2^{\left\lceil\lg (b - a + 1)\right\rceil}\) / (b - a + 1)).
⇒ T(a, b) = Θ(n \(2^{\lg (b - a + 1)}\) / (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.1-3 ★

Suppose that you want to output 0 with probability 1 / 2 and 1 with probability 1 / 2. At your disposal is a procedure Biased-Random, 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 Biased-Random 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.2-1

In Hire-Assistant, 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.2-2

In Hire-Assistant, 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.2-3

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}[X]\) = 7 n / 2.

5.2-4

Use indicator random variables to solve the following problem, which is known as the hat-check problem. Each of n customers gives a hat to a hat-check person at a restaurant. The hat-check 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.2-5

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 2-4 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} (n - i) / 2\)
= n (n - 1) / 4.

5.3-1

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 0-permutations. Therefore, the probability that an empty subarray contains a 0-permutation should be 0, thus invalidating the loop invariant prior to the first iteration. Rewrite the procedure Randomize-In-Place 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.3-2

Professor Kelp decides to write a procedure that produces at random any permutation besides the identity permutation. He proposes the following procedure:

Permute-Without-Identity(A)

1. n = A.length
2. for i = 1 to n - 1
3.     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.3-3

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:

Permute-With-All(A)

1. n = A.length
2. for i = 1 to n
3.     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.3-4

Professor Armstrong suggests the following procedure for generating a uniform random permutation:

Permute-By-Cyclic(A)

1. n = A.length
2. let B[1‥n] be a new array
3. offset = Random(1, n)
4. for i = 1 to n
5.     dest = i + offset
6.     if dest > n
7.         dest = dest - n
8.     B[dest] = A[i]
9. 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 Permute-By-Cyclic, while the uniform distribution requires n! different results. So the result permutation can not be uniformly random.

5.3-5 ★

Prove that in the array P in procedure Permute-By-Sorting, 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.3-6

Explain how to implement the algorithm Permute-By-Sorting 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.3-7

Suppose we want to create a random sample of the set {1, 2, 3, …, n}, that is, an m-element subset S, where 0 ≤ m ≤ n, such that each m-subset is equally likely to be created. One way would be to set A[i] = i for i = 1, 2, 3, …, n, call Randomize-In-Place(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 m-subset S of {1, 2, 3, …, n}, in which each m-subset is equally likely, while making only m calls to Random:

Random-Sample(m, n)

1. if m == 0
2.     return ∅
3. else S = Random-Sample(m - 1, n - 1)
4.     i = Random(1, n)
5.     if i ∈ S
6.         S = S ∪ {n}
7.     else S = S ∪ {i}
8.     return S

The algorithm is implemented here.

Like exercise 5.3-4, it is not enough by just proving ∀ i ∈ ℕ and 1 ≤ i ≤ n, the probability of i ∈ Random-Sample(m, n) is m / n.

Lemma: Random-Sample(m, n) generates any m-subset with the probability of 1 / C(n, m).

Proof by induction on m:

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

• Inductive cases:

  • For a certain m-subset 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 m-subset 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 m-subset 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 m-subset does not contain n, let the last element being added to S can be k, then k can be any element in the m-subset.

    So the probability of generating a certain m-subset does not contain n is \(∑_{j = 1}^{m} (1 / C(n - 1, m - 1)) (1 / n)\) = (1 / C(n - 1, m - 1)) (m / n) = 1 / C(n, m).

  So all m-subsets 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.4-1

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?

1. 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.

2. 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.4-2

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(b, k - 1) / b^{k - 1}\right) ((k - 1) / b) k\)

5.4-3 ★

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.4-4 ★

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.4-5 ★

What is the probability that a k-string over a set of size n forms a k-permutation? 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.4-6 ★

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) \((1 / n)^k (1 - 1 / n)^{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(n, k) (1 / n)^k (1 - 1 / n)^{n - k}\)
= n C(n, k) \((1 / n)^k (1 - 1 / n)^{n - k}\).

So the expected number of bins with exactly 0 ball is:

n C(n, 0) \((1 / n)^0 (1 - 1 / n)^{n - 0}\)
= n \((1 - 1 / n)^n\).

So the expected number of bins with exactly 1 ball is:

n C(n, 1) \((1 / n)^1 (1 - 1 / n)^{n - 1}\)
= n \((1 - 1 / n)^{n - 1}\).

5.4-7 ★

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

5-1 Probabilistic counting

With a b-bit 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.

1. Show that the expected value represented by the counter after n Increment operations have been performed is exactly n.
2. 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.

1. For any counter value \(n_i\), the expected value increased by one increment operation is:

   \((n_{i + 1} - n_i) (1 / (n_{i + 1} - n_i)) + 0 (1 / (n_{i + 1} - n_i))\) = 1.

   Let \(X_i\) be the random variable in which the counter values increased by the i-th 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.

2. Skipped.

5-2 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 Random-Search 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 Random-Search 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 Random-Search 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 Random-Search terminates?

Now consider a deterministic linear search algorithm, which we refer to as Deterministic-Search. 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 average-case running time of Deterministic-Search? What is the worst-case running time of Deterministic-Search?

f. Generalizing your solution to part (e), suppose that there are k ≥ 1 indices i such that A[i] = x. What is the average-case running time of Deterministic-Search? What is the worst-case running time of Deterministic-Search? 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 average-case running time of Deterministic-Search? What is the worst-case running time of Deterministic-Search?

Finally, consider a randomized algorithm Scramble-Search 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 worst-case and expected running times of Scramble-Search 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.

Scramble-Search(A, v)

1. V = an array with A.length False values
2. c = 0
3. while c < A.length
4.     i = Random(1, n)
5.     if not V[i]
6.         if A[i] == v
7.             return i
8.         V[i] = True
9.         c = c + 1
10. 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. Average-case running time is Θ((1 + n) / 2), Worst-case running time is Θ(n).

f. The expected number of indices to pick is:

\(∑_{i = 1}^{n - k + 1} i P(n - k, i - 1) k P(n - i, n - i) / P(n, n)\) = (n + 1) / (k + 1). (By WolframAlpha)

Worst-case running time is Θ(n - k + 1).

g. They are both Θ(n).

h. The worst-case, expected running time are all Θ(n).

i. I will use Deterministic-Search, it is superior in every way.

II Sorting and Order Statistics

6 Heapsort

6.1 Heaps

6.1-1

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.1-2

Show that an n-element heap has height ⌊lg n⌋.

According to exercise 6.1-1, 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 n-element heap must have height ⌊lg n⌋.

6.1-3

Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.

Proof by induction:

Base case: if a max-heap has one element, then the only subtree is the one-element tree, the root contains the largest value, since it is the only value the tree has.

Inductive case: if a max-heap 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.1-4

Where in a max-heap 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.1-5

Is an array that is in sorted order a min-heap?

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 min-heap property.

6.1-6

Is the array with values ⟨23, 17, 14, 6, 13, 10, 1, 5, 7, 12⟩ a max-heap?

Nope.

6.1-7

Show that, with the array representation for storing an n-element 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.2-1

Using Figure 6.2 as a model, illustrate the operation of Max-Heapify(A, 3) on the array A = ⟨27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0⟩.

Skipped.

6.2-2

Starting with the procedure Max-Heapify, write pseudocode for the procedure Min-Heapify(A, i), which performs the corresponding manipulation on a min-heap. How does the running time of Min-Heapify compare to that of Max-Heapify?

Solution is implemented here.

The running time of Min-Heapify is the same as Max-Heapify.

6.2-3

What is the effect of calling Max-Heapify(A, i) when the element A[i] is larger than its children?

Nothing happens.

6.2-4

What is the effect of calling Max-Heapify(A, i) for i > A.heap-size / 2?

Nothing happens.

6.2-5

The code for Max-Heapify 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 Max-Heapify that uses an iterative control construct (a loop) instead of recursion.

The solution is implemented here.

6.2-6

Show that the worst-case running time of Max-Heapify on a heap of size n is Ω(lg n). (Hint: For a heap with n nodes, give node values that cause Max-Heapify 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 Max-Heapify 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 worst-case running time is Ω(lg n).

6.3 Building a heap

6.3-1

Using Figure 6.3 as a model, illustrate the operation of Build-Max-Heap on the array A = ⟨5, 3, 17, 10, 84, 19, 6, 22, 9⟩.

Skipped.

6.3-2

Why do we want the loop index i in line 2 of Build-Max-Heap to decrease from ⌊A.length / 2⌋ to 1 rather than increase from 1 to ⌊A.length / 2⌋?

Because Max-Heapify requires that its child subtree being a heap, so we have to do this bottom-up style.

6.3-3

Show that there are at most ⌈n / \(2^{h + 1}\)⌉ nodes of height h in any n-element heap.

Proof by induction:

Base case: the nodes of height 0 are leaf nodes. according to exercise 6.1-7, 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.4-1

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.4-2

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 max-heap 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.4-3

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.4-4

Show that the worst-case running time of Heapsort is Ω(n lg n).

Skipped.

6.4-5 ★

Show that when all elements are distinct, the best-case running time of Heapsort is Ω(n lg n).

Skipped.

6.5 Priority queues

6.5-1

Illustrate the operation of Heap-Extract-Max on the heap A = ⟨15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1⟩.

Skipped.

6.5-2

Illustrate the operation of Max-Heap-Insert(A, 10) on the heap A = ⟨15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1⟩.

Skipped.

6.5-3

Write pseudocode for the procedures Heap-Minimum, Heap-Extract-Min, Heap-Decrease-Key, and Min-Heap-Insert that implement a min-priority queue with a min-heap.

Solution is implemented here.

6.5-4

Why do we bother setting the key of the inserted node to -∞ in line 2 of Max-Heap-Insert when the next thing we do is increase its key to the desired value?

We must ensure that when calling Heap-Increase-Key, the value of key must be equal to or greater than A[i], so we use -∞ to do this.

6.5-5

Argue the correctness of Heap-Increase-Key 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.heap-size] satisfies the max-heap 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.heap-size] satisfies the max-heap property at the time Heap-Increase-Key is called.

Skipped.

6.5-6

Each exchange operation on line 5 of Heap-Increase-Key typically requires three assignments. Show how to use the idea of the inner loop of Insertion-Sort to reduce the three assignments down to just one assignment.

Solution is implemented here.

6.5-7

Show how to implement a first-in, first-out 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.5-8

The operation Heap-Delete(A, i) deletes the item in node i from heap A. Give an implementation of Heap-Delete that runs in O(lg n) time for an n-element max-heap.

Solution is implemented here.

6.5-9

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 min-heap for k-way merging.)

Solution is implemented here.

6.X Problems

6-1 Building a heap using insertion

We can build a heap by repeatedly calling Max-Heap-Insert to insert the elements into the heap. Consider the following variation on the Build-Max-Heap procedure:

Build-Max-Heap′(A)

1. A.heap-size = 1
2. for i = 2 to A.length
3.     Build-Max-Heap′(A, A[i])

a. Do the procedures Build-Max-Heap and Build-Max-Heap′ 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, Build-Max-Heap′ requires Θ(n lg n) time to build an n-element heap.

a. No. For array ⟨0, 1, 2, 3⟩, Build-Max-Heap produces ⟨3, 1, 2, 0⟩, while Build-Max-Heap′ 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).

6-2 Analysis of d-ary heaps

A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.

a. How would you represent a d-ary heap in an array?

b. What is the height of a d-ary heap of n elements in terms of n and d?

c. Give an efficient implementation of Extract-Max in a d-ary max-heap. Analyze its running time in terms of d and n.

d. Give an efficient implementation of Insert in a d-ary max-heap. Analyze its running time in terms of d and n.

e. Give an efficient implementation of Increase-Key(A, i, k), which flags an error if k < A[i], but otherwise sets A[i] = k and then updates the d-ary max-heap 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((d - 1) n + 1) ≤ h < \log_d((d - 1) n + 1) + 1\). Since h is an integer, we have h = \(\left\lceil\log_d((d - 1) n + 1)\right\rceil\) = Θ(\(\log_d n\)).

c. The solution is implemented here. The worst-case 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 worst-case 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\)).

6-3 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 Extract-Min 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 Max-Heapify.) Define T(p), where p = m + n, to be the maximum running time of Extract-Min 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.

b.

1. 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.
2. 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 Extract-Min 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.1-1

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.1-2

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.

1. Partition returns r when all elements have the same value.
2. Solution is implemented here.

7.1-3

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.1-4

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.2-1

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(n) ≤ 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) (n - 1)^2 + \left(c_1 / 2\right) (n - 1) + c_3 + c_1 n\)
= \(\left(c_1 / 2\right) n^2 - c_1 n + c_1 / 2 + \left(c_1 / 2\right) (n - 1) + 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.2-2

What is the running time of Quicksort when all elements of array A have the same value?

Θ(\(n^2\)).

7.2-3

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.2-4