Recursion

Exercises

Tower of Hanoi

1.

Prove that the original recursive Tower of Hanoi algorithm performs exactly the same sequence of moves, the same disks, to and from the same pegs, in the same order, as each of the following non-recursive algorithms. The pegs are labeled 0, 1, and 2, and our problem is to move a stack of n disks from peg 0 to peg 2.

(a) If n is even, swap pegs 1 and 2. At the ith step, make the only legal move that avoids peg i mod 3. If there is no legal move, then all disks are on peg i mod 3, and the puzzle is solved.

(b) For the first move, move disk 1 to peg 1 if n is even and to peg 2 if n is odd. Then repeatedly make the only legal move that involves a different disk from the previous move. If no such move exists, the puzzle is solved.

(c) Pretend that disks n + 1, n + 2, and n + 3 are at the bottom of pegs 0, 1, and 2, respectively. Repeatedly make the only legal move that satisfies the following constraints, until no such move is possible.

Do not place an odd disk directly on top of another odd disk.
Do not place an even disk directly on top of another even disk.
Do not undo the previous move.

(d) Let $ρ (n)$ denote the smallest integer $k$ such that $n / 2^{k}$ is not an integer. For example, $ρ (42) = 2$ , because $42/ 2^{1}$ is an integer but $42/ 2^{2}$ is not. Equivalently, $ρ (n)$ is one more than the position of the least significant 1 in the binary representation of $n$ . Because its behavior resembles the marks on a ruler, $ρ (n)$ is sometimes called the ruler function.

RulerHanoi(n):
    i <- 1
    while rho(i) <= n
        if n - i is even
            move disk rho(i) forward
        else
            move disk rho(i) backward
        i <- i + 1

Here forward means 0 -> 1 -> 2 -> 0, and backward means 0 -> 2 -> 1 -> 0.

2.

The Tower of Hanoi is a relatively recent descendant of a much older mechanical puzzle known as the Chinese linked rings, Baguenaudier, Cardan’s Rings, Meleda, Patience, Tiring Irons, Prisoner’s Lock, Spin-Out, and many other names.

The Baguenaudier puzzle has many physical forms, but one of the most common consists of a long metal loop and several rings, which are connected to a solid base by movable rods. More abstractly, we can model the puzzle as a sequence of bits, one for each ring, where the $i$ th bit is 1 if the loop passes through the $i$ th ring and 0 otherwise. Here we index the rings from right to left.

The puzzle allows two legal moves:

You can always flip the 1st (rightmost) bit.
If the bit string ends with exactly $z$ 0s, you can flip the $(z + 2)$ th bit.

The goal of the puzzle is to transform a string of n 1s into a string of n 0s.

For example, the following sequence of 21 moves solves the 5-ring puzzle:

11111 -> 11110 -> 11010 -> 11011 -> 11001 -> 11000
      -> 01000 -> 01001 -> 01011 -> 01010 -> 01110
      -> 01111 -> 01101 -> 01100 -> 00100 -> 00101
      -> 00111 -> 00110 -> 00010 -> 00011 -> 00001 -> 00000

with moves

1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1

(a) Call a sequence of moves reduced if no move is the inverse of the previous move. Prove that for any non-negative integer $n$ , there is exactly one reduced sequence of moves that solves the $n$ -ring Baguenaudier puzzle.

(b) Describe an algorithm to solve the Baguenaudier puzzle. Your input is the number of rings n; your algorithm should print a reduced sequence of moves that solves the puzzle. For example, given the integer 5 as input, your algorithm should print the sequence 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1.

3.

Describe an algorithm to transfer a stack of $n$ disks from one vertical needle to the other vertical needle in the Towers of Pisa variant, using the smallest possible number of moves. Exactly how many moves does your algorithm perform?

In this variant, any number of disks on the leaning needle can be moved together to another needle in a single move. It is still forbidden to place a larger disk on top of a smaller disk, and disks must be moved one at a time onto the leaning needle or between the two vertical needles.

4.

Consider the following restricted variants of the Tower of Hanoi puzzle. In each problem, the pegs are numbered 0, 1, and 2, and your task is to move a stack of n disks from peg 0 to peg 2.

(a) Suppose you are forbidden to move any disk directly between peg 1 and peg 2; every move must involve peg 0. Describe an algorithm to solve this version of the puzzle in as few moves as possible. Exactly how many moves does your algorithm make?

(b) Suppose you are only allowed to move disks from peg 0 to peg 2, from peg 2 to peg 1, or from peg 1 to peg 0. Equivalently, suppose the pegs are arranged in a circle and numbered in clockwise order, and you are only allowed to move disks counterclockwise. Describe an algorithm to solve this version of the puzzle in as few moves as possible. How many moves does your algorithm make?

(c) Finally, suppose your only restriction is that you may never move a disk directly from peg 0 to peg 2. Describe an algorithm to solve this version of the puzzle in as few moves as possible. How many moves does your algorithm make? [Hint: Matrices! This variant is considerably harder to analyze than the other two.]

5.

Consider the following more complex variant of the Tower of Hanoi puzzle. The puzzle has a row of $k$ pegs, numbered from 1 to k. In a single turn, you are allowed to move the smallest disk on peg i to either peg i - 1 or peg i + 1, for any index i; as usual, you are not allowed to place a bigger disk on a smaller disk. Your mission is to move a stack of n disks from peg 1 to peg k.

(a) Describe a recursive algorithm for the case k = 3. Exactly how many moves does your algorithm make? This is exactly the same as problem 4(a).

(b) Describe a recursive algorithm for the case k = n + 1 that requires at most $O (n^{3})$ moves. [Hint: Use part (a)]

(c) Describe a recursive algorithm for the case k = n + 1 that requires at most $O (n^{2})$ moves. [Hint: Don’t use part (a)]

(d) Describe a recursive algorithm for the case k = n that requires at most a polynomial number of moves. Which polynomial?

(e) Describe and analyze a recursive algorithm for arbitrary n and k. How small must k be as a function of n so that the number of moves is bounded by a polynomial in n?

Recursion Trees

6.

Use recursion trees to solve each of the following recurrences:

$A (n) = 2 A (n /4) + n$
$B (n) = 2 B (n /4) + n$
$C (n) = 2 C (n /4) + n^{2}$
$D (n) = 3 D (n /3) + n$
$E (n) = 3 E (n /3) + n$
$F (n) = 3 F (n /3) + n^{2}$
$G (n) = 4 G (n /2) + n$
$H (n) = 4 H (n /2) + n$
$I (n) = 4 I (n /2) + n^{2}$

7.

Use recursion trees to solve each of the following recurrences:

$(j)$ $J (n) = J (n /2) + J (n /3) + J (n /6) + n$
$(k)$ $K (n) = K (n /2) + 2 K (n /3) + 3 K (n /4) + n^{2}$
$(l)$ $L (n) = L (n /15) + L (n /10) + 2 L (n /6) + n$

8.

Use recursion trees to solve each of the following recurrences:

$(m)$ $M (n) = 2 M (n /2) + O (n lo g n)$
$(n)$ $N (n) = 2 N (n /2) + O (n / lo g n)$
$(p)$ $P (n) = n P (n) + n$
$(q)$ $Q (n) = 2 n Q (2 n) + n$

Sorting

9.

Suppose you are given a stack of n pancakes of different sizes. You want to sort the pancakes so that smaller pancakes are on top of larger pancakes. The only operation you can perform is a flip: insert a spatula under the top k pancakes, for some integer k between 1 and n, and flip them all over.

(a) Describe an algorithm to sort an arbitrary stack of n pancakes using $O (n)$ flips. Exactly how many flips does your algorithm perform in the worst case? The exact worst-case optimal number of flips required to sort n pancakes is a long-standing open problem; just do the best you can.

(b) For every positive integer n, describe a stack of n pancakes that requires $Ω (n)$ flips to sort.

(c) Now suppose one side of each pancake is burned. Describe an algorithm to sort an arbitrary stack of n pancakes, so that the burned side of every pancake is facing down, using $O (n)$ flips. Exactly how many flips does your algorithm perform in the worst case?

10.

Recall that the median-of-three heuristic examines the first, last, and middle element of the array, and uses the median of those three elements as a quicksort pivot. Prove that quicksort with the median-of-three heuristic requires $Ω (n^{2})$ time to sort an array of size n in the worst case. Specifically, for any integer n, describe a permutation of the integers 1 through n, such that in every recursive call to median-of-three-quicksort, the pivot is always the second smallest element of the array. Designing this permutation requires intimate knowledge of the Partition subroutine.

(a) As a warm-up exercise, assume that the Partition subroutine is stable, meaning it preserves the existing order of all elements smaller than the pivot, and it preserves the existing order of all elements larger than the pivot.

(b) Assume that the Partition subroutine uses the specific algorithm listed on page 29, which is not stable.

11.

(a) Hey, Moe! Hey, Larry! Prove that the following algorithm actually sorts its input!

StoogeSort(A[0 .. n - 1]):
    if n = 2 and A[0] > A[1]
        swap A[0] <-> A[1]
    else if n > 2
        m = ceil(2n/3)
        StoogeSort(A[0 .. m - 1])
        StoogeSort(A[n - m .. n - 1])
        StoogeSort(A[0 .. m - 1])

(b) Would StoogeSort still sort correctly if we replaced m = ceil(2n/3) with m = floor(2n/3)? Justify your answer.

(d) Solve the recurrence, and prove that your solution is correct. [Hint: Ignore the ceiling.]

(e) Prove that the number of swaps executed by StoogeSort is at most $(2 n)$ .

12.

The following cruel and unusual sorting algorithm was proposed by Gary Miller:

Cruel(A[1 .. n]):
    if n > 1
        Cruel(A[1 .. n/2])
        Cruel(A[n/2 + 1 .. n])
        Unusual(A[1 .. n])
 
Unusual(A[1 .. n]):
    if n = 2
        if A[1] > A[2]
            swap A[1] <-> A[2]
    else
        for i <- 1 to n/4
            swap A[i + n/4] <-> A[i + n/2]
        Unusual(A[1 .. n/2])
        Unusual(A[n/2 + 1 .. n])
        Unusual(A[n/4 + 1 .. 3n/4])

The comparisons performed by this algorithm do not depend at all on the values in the input array; such a sorting algorithm is called oblivious. Assume for this problem that the input size n is always a power of 2.

(a) Prove by induction that Cruel correctly sorts any input array. [Hint: Consider an array that contains n/4 1s, n/4 2s, n/4 3s, and n/4 4s. Why is this special case enough?]

(b) Prove that Cruel would not correctly sort if we removed the for-loop from Unusual.

(d) What is the running time of Unusual? Justify your answer.

(e) What is the running time of Cruel? Justify your answer.

13.

An inversion in an array A[1 .. n] is a pair of indices (i, j) such that i < j and A[i] > A[j]. The number of inversions in an n-element array is between 0 if the array is sorted and $(2 n)$ if the array is sorted backward. Describe and analyze an algorithm to count the number of inversions in an n-element array in $O (n lo g n)$ time. [Hint: Modify mergesort.]

14.

(a) Suppose you are given two sets of n points, one set ${p_{1}, p_{2}, \dots, p_{n}}$ on the line y = 0 and the other set ${q_{1}, q_{2}, \dots, q_{n}}$ on the line y = 1. Create a set of n line segments by connecting each point $p_{i}$ to the corresponding point $q_{i}$ . Describe and analyze a divide-and-conquer algorithm to determine how many pairs of these line segments intersect, in $O (n lo g n)$ time. [Hint: See the previous problem.]

(b) Now suppose you are given two sets ${p_{1}, p_{2}, \dots, p_{n}}$ and ${q_{1}, q_{2}, \dots, q_{n}}$ of n points on the unit circle. Connect each point $p_{i}$ to the corresponding point $q_{i}$ . Describe and analyze a divide-and-conquer algorithm to determine how many pairs of these line segments intersect in $O (n lo g^{2} n)$ time. [Hint: Use your solution to part (a)]

15.

(a) Describe an algorithm that sorts an input array A[1 .. n] by calling a subroutine SqrtSort(k), which sorts the subarray A[k + 1 .. k + sqrt(n)] in place, given an arbitrary integer k between 0 and n - sqrt(n) as input. To simplify the problem, assume that $n$ is an integer. Your algorithm is only allowed to inspect or modify the input array by calling SqrtSort; in particular, your algorithm must not directly compare, move, or copy array elements. How many times does your algorithm call SqrtSort in the worst case?

(b) Prove that your algorithm from part (a) is optimal up to constant factors. In other words, if $f (n)$ is the number of times your algorithm calls SqrtSort, prove that no algorithm can sort using $o (f (n))$ calls to SqrtSort.

(c) Now suppose SqrtSort is implemented recursively, by calling your sorting algorithm from part (a). For example, at the second level of recursion, the algorithm is sorting arrays roughly of size $n^{1/4}$ . What is the worst-case running time of the resulting sorting algorithm? To simplify the analysis, assume that the array size n has the form $2^{2^{k}}$ , so that repeated square roots are always integers.

Selection

16.

Suppose we are given a set S of n items, each with a value and a weight. For any element $x \in S$ , we define two subsets:

$S_{< x}$ is the set of elements of S whose value is less than the value of $x$ .
$S_{> x}$ is the set of elements of S whose value is more than the value of $x$ .

For any subset $R \subseteq S$ , let $w (R)$ denote the sum of the weights of elements in $R$ . The weighted median of $R$ is any element $x$ such that $w (S_{< x}) \leq w (S) /2$ and $w (S_{> x}) \leq w (S) /2$ .

Describe and analyze an algorithm to compute the weighted median of a given weighted set in $O (n)$ time. Your input consists of two unsorted arrays S[1 .. n] and W[1 .. n], where for each index i, the ith element has value S[i] and weight W[i]. You may assume that all values are distinct and all weights are positive.

17.

(a) Describe an algorithm to determine in $O (n)$ time whether an arbitrary array A[1 .. n] contains more than n/4 copies of any value.

(b) Describe and analyze an algorithm to determine, given an arbitrary array A[1 .. n] and an integer k, whether A contains more than k copies of any value. Express the running time of your algorithm as a function of both n and k.

Do not use hashing, or radix sort, or any other method that depends on the precise input values, as opposed to their order.

18.

Describe an algorithm to compute the median of an array A[1 .. 5] of distinct numbers using at most 6 comparisons. Instead of writing pseudocode, describe your algorithm using a decision tree: a binary tree where each internal node contains a comparison of the form A[i] ≷ A[j]? and each leaf contains an index into the array.

19.

Consider the generalization of the Blum-Floyd-Pratt-Rivest-Tarjan MomSelect algorithm shown below, which partitions the input array into ceil(n/b) blocks of size b, instead of ceil(n/5) blocks of size 5, but is otherwise identical.

Mom_b_Select(A[1 .. n], k):
    if n <= b^2
        use brute force
    else
        m <- ceil(n / b)
        for i <- 1 to m
            M[i] <- MedianOfB(A[b(i - 1) + 1 .. bi])
        mom_b <- Mom_b_Select(M[1 .. m], floor(m / 2))
        r <- Partition(A[1 .. n], mom_b)
        if k < r
            return Mom_b_Select(A[1 .. r - 1], k)
        else if k > r
            return Mom_b_Select(A[r + 1 .. n], k - r)
        else
            return mom_b

(a) State a recurrence for the running time of Mom_b_Select, assuming that b is a constant, so the subroutine MedianOfB runs in $O (1)$ time. In particular, how do the sizes of the recursive subproblems depend on the constant b? Consider even b and odd b separately.

(b) What is the worst-case running time of Mom1Select? [Hint: This is a trick question.]

(d) What is the worst-case running time of Mom3Select? Finding an upper bound on the running time is straightforward; the hard part is showing that this analysis is actually tight. [Hint: See problem 10.]

(e) What is the worst-case running time of Mom4Select? Again, the hard part is showing that the analysis cannot be improved.

(f) For any constants b >= 5, the algorithm Mom_b_Select runs in $O (n)$ time, but different values of b lead to different constant factors. Let $M (b)$ denote the minimum number of comparisons required to find the median of b numbers. The exact value of $M (b)$ is known only for b <= 13:

b:     1  2  3  4  5  6  7  8  9 10 11 12 13
M(b):  0  1  3  4  6  8 10 12 14 16 18 20 23

For each b between 5 and 13, find an upper bound on the running time of Mom_b_Select of the form $T (n) \leq α_{b} n$ for some explicit constant $α_{b}$ . For example, on page 39 we showed that $α_{5} \leq 16$ .

(g) Which value of b yields the smallest constant $α_{b}$ ? [Hint: This is a trick question!]

20.

Prove that the variant of the Blum-Floyd-Pratt-Rivest-Tarjan Select algorithm shown below, which uses an extra layer of small medians to choose the main pivot, runs in $O (n)$ time.

MomomSelect(A[1 .. n], k):
    if n <= 81
        use brute force
    else
        m <- ceil(n / 3)
        for i <- 1 to m
            M[i] <- MedianOf3(A[3i - 2 .. 3i])
        mm <- ceil(m / 3)
        for j <- 1 to mm
            Mom[j] <- MedianOf3(M[3j - 2 .. 3j])
        momom <- MomomSelect(Mom[1 .. mm], floor(mm / 2))
        r <- Partition(A[1 .. n], momom)
        if k < r
            return MomomSelect(A[1 .. r - 1], k)
        else if k > r
            return MomomSelect(A[r + 1 .. n], k - r)
        else
            return momom

21.

(a) Suppose we are given two sorted arrays A[1 .. n] and B[1 .. n]. Describe an algorithm to find the median element in the union of A and B in $Θ (lo g n)$ time. You can assume that the arrays contain no duplicate elements.

(b) Suppose we are given two sorted arrays A[1 .. m] and B[1 .. n] and an integer k. Describe an algorithm to find the kth smallest element in A ∪ B in $Θ (lo g (m + n))$ time. For example, if k = 1, your algorithm should return the smallest element of A ∪ B. [Hint: Use your solution to part (a)]

(c) Now suppose we are given three sorted arrays A[1 .. n], B[1 .. n], and C[1 .. n], and an integer k. Describe an algorithm to find the kth smallest element in A ∪ B ∪ C in $O (lo g n)$ time.

(d) Finally, suppose we are given a two-dimensional array A[1 .. m, 1 .. n] in which every row A[i, ·] is sorted, and an integer k. Describe an algorithm to find the kth smallest element in A as quickly as possible. How does the running time of your algorithm depend on m? [Hint: Solve problem 16 first.]

Arithmetic

22.

In 1854, archaeologists discovered Sumerian clay tablets, carved around 2000 BCE, that list the squares of integers up to 59. This discovery led some scholars to conjecture that ancient Sumerians performed multiplication by reduction to squaring, using an identity like

x \cdot y = \frac{x ^{2} + y ^{2} - ( x - y ) ^{2}}{2} .

Describe recursive squaring algorithms:

(a) Describe a variant of Karatsuba’s algorithm that squares any n-digit number in $O (n^{l g 3})$ time, by reducing to squaring three ceil(n/2)-digit numbers. Karatsuba actually did this in 1960.

(b) Describe a recursive algorithm that squares any n-digit number in $O (n^{l o g_{3} 6})$ time, by reducing to squaring six ceil(n/3)-digit numbers.

(c) Describe a recursive algorithm that squares any n-digit number in $O (n^{l o g_{3} 5})$ time, by reducing to squaring only five (n/3 + O(1))-digit numbers. [Hint: What is $(a + b + c)^{2} + (a - b + c)^{2}$ ?]

23.

(a) Describe and analyze a variant of Karatsuba’s algorithm that multiplies any m-digit number and any n-digit number, for any n >= m, in $O (n m^{l g 3 - 1})$ time.

(b) Describe an algorithm to compute the decimal representation of $2^{n}$ in $O (n^{l g 3})$ time, using the algorithm from part (a) as a subroutine. The standard algorithm that computes one digit at a time requires $Θ (n^{2})$ time.

(c) Describe a divide-and-conquer algorithm to compute the decimal representation of an arbitrary n-bit binary number in $O (n^{l g 3})$ time. [Hint: Watch out for an extra log factor in the running time.]

(d) Suppose we can multiply two n-digit numbers in $O (M (n))$ time. Describe an algorithm to compute the decimal representation of an arbitrary n-bit binary number in $O (M (n) lo g n)$ time. [Hint: The analysis is the hard part; use a domain transformation.]

24.

Consider the following classical recursive algorithm for computing the factorial $n!$ of a non-negative integer n:

Factorial(n):
    if n = 0
        return 1
    else
        return n * Factorial(n - 1)

(a) How many multiplications does this algorithm perform?

(b) How many bits are required to write $n!$ in binary? Express your answer in the form $Θ (f (n))$ , for some familiar function $f (n)$ . [Hint: $(n /2)^{n /2} < n! < n^{n}$ .]

(c) Your answer to part (b) should convince you that the number of multiplications is not a good estimate of the actual running time of Factorial. We can multiply any k-digit number and any l-digit number in $O (k \cdot l)$ time using either the lattice algorithm or duplation and mediation. What is the running time of Factorial if we use this multiplication algorithm as a subroutine?

(d) The following recursive algorithm also computes the factorial function, but using a different grouping of the multiplications:

Falling(n, m):    // Compute n! / (n - m)!
    if m = 0
        return 1
    else if m = 1
        return n
    else
        return Falling(n, floor(m/2)) * Falling(n - floor(m/2), ceil(m/2))

What is the running time of Falling(n, n) if we use grade-school multiplication? [Hint: As usual, ignore the floors and ceilings.]

(e) Describe and analyze a variant of Karatsuba’s algorithm that multiplies any k-digit number and any l-digit number, for any k >= l, in

O (k \cdot l^{l g 3 - 1}) = O (k \cdot l^{0.585}) .

(f) What are the running times of Factorial(n) and Falling(n, n) if we use the modified Karatsuba multiplication from part (e)?

25.

The greatest common divisor of two positive integers x and y, denoted $g cd (x, y)$ , is the largest integer d such that both x/d and y/d are integers. Euclid’s Elements, written around 300 BCE, describes the following recursive algorithm to compute $g cd (x, y)$ :

EuclidGCD(x, y):
    if x = y
        return x
    else if x > y
        return EuclidGCD(x - y, y)
    else
        return EuclidGCD(x, y - x)

(a) Prove that EuclidGCD correctly computes $g cd (x, y)$ . Specifically:

Prove that EuclidGCD(x, y) divides both x and y.
Prove that every divisor of x and y is a divisor of EuclidGCD(x, y).

(b) What is the worst-case running time of EuclidGCD(x, y), as a function of x and y? Assume that computing x - y requires $O (lo g x + lo g y)$ time.

FastEuclidGCD(x, y):
    if y = 0
        return x
    else if x > y
        return FastEuclidGCD(y, x mod y)
    else
        return FastEuclidGCD(x, y mod x)

(d) What is the worst-case running time of FastEuclidGCD(x, y), as a function of x and y? Assume that computing x mod y takes $O (lo g x \cdot lo g y)$ time.

(e) Prove that the following algorithm also computes $g cd (x, y)$ :

BinaryGCD(x, y):
    if x = y
        return x
    else if x and y are both even
        return 2 * BinaryGCD(x/2, y/2)
    else if x is even
        return BinaryGCD(x/2, y)
    else if y is even
        return BinaryGCD(x, y/2)
    else if x > y
        return BinaryGCD((x - y)/2, y)
    else
        return BinaryGCD(x, (y - x)/2)

(f) What is the worst-case running time of BinaryGCD(x, y), as a function of x and y? Assume that computing x - y takes $O (lo g x + lo g y)$ time, and computing z/2 requires $O (lo g z)$ time.

Arrays

26.

Suppose you are given a $2^{n} \times 2^{n}$ checkerboard with one arbitrarily chosen square removed. Describe and analyze an algorithm to compute a tiling of the board without gaps or overlaps by L-shaped tiles, each composed of 3 squares. Your input is the integer n and two n-bit integers representing the row and column of the missing square. The output is a list of the positions and orientations of $(4^{n} - 1) /3$ tiles. Your algorithm should run in $O (4^{n})$ time. [Hint: First prove that such a tiling always exists.]

27.

You are a visitor at a political convention, or perhaps a faculty meeting, with n delegates; each delegate is a member of exactly one political party. It is impossible to tell which political party any delegate belongs to; in particular, you will be summarily ejected from the convention if you ask. However, you can determine whether any pair of delegates belong to the same party by introducing them to each other. Members of the same political party always greet each other with smiles and friendly handshakes; members of different parties always greet each other with angry stares and insults.

(a) Suppose more than half of the delegates belong to the same political party. Describe an efficient algorithm that identifies all members of this majority party.

(b) Now suppose there are more than two parties, but one party has a plurality: more people belong to that party than to any other party. Present a practical procedure to precisely pick the people from the plurality political party as parsimoniously as possible, presuming the plurality party is composed of at least p people. Pretty please.

28.

Smullyan Island has three types of inhabitants: knights always speak the truth; knaves always lie; and normals sometimes speak the truth and sometimes don’t. Everyone on the island knows everyone else’s name and type. You want to learn the type of every inhabitant.

You can ask any inhabitant to tell you the type of any other inhabitant. Specifically, if you ask Hey X, what is Y's type? then X will respond as follows:

If X is a knight, then X will respond with Y’s correct type.
If X is a knave, then X could respond with either of the types that Y is not.
If X is a normal, then X could respond with any of the three types.

The inhabitants will ignore any questions not of this precise form; in particular, you may not ask an inhabitant about their own type. Asking the same inhabitant the same question multiple times always yields the same answer, so there’s no point in asking any question more than once.

(a) Suppose you know that a strict majority of inhabitants are knights. Describe an efficient algorithm to identify the type of every inhabitant.

(b) Prove that if at most half the inhabitants are knights, it is impossible to determine the type of every inhabitant.

29.

Most graphics hardware includes support for a low-level operation called blit, or block transfer, which quickly copies a rectangular chunk of a pixel map, a two-dimensional array of pixel values, from one location to another. This is a two-dimensional version of memcpy().

Suppose we want to rotate an n x n pixel map 90 degrees clockwise. One way to do this, at least when n is a power of two, is to split the pixel map into four n/2 x n/2 blocks, move each block to its proper position using a sequence of five blits, and then recursively rotate each block. Alternately, we could first recursively rotate the blocks and then blit them into place.

(a) Prove that both versions of the algorithm are correct when n is a power of 2.

(b) Exactly how many blits does the algorithm perform when n is a power of 2?

(c) Describe how to modify the algorithm so that it works for arbitrary n, not just powers of 2. How many blits does your modified algorithm perform?

(d) What is your algorithm’s running time if a k x k blit takes $O (k^{2})$ time?

(e) What if a k x k blit takes only $O (k)$ time?

30.

An array A[0 .. n - 1] of n distinct numbers is bitonic if there are unique indices i and j such that

A [(i - 1) mod n] < A [i] > A [(i + 1) mod n]

and

A [(j - 1) mod n] > A [j] < A [(j + 1) mod n] .

In other words, a bitonic sequence either consists of an increasing sequence followed by a decreasing sequence, or can be circularly shifted to become so. For example,

4 6 9 8 7 5 1 2 3

is bitonic, but

3 6 9 8 7 5 1 2 4

is not bitonic.

Describe and analyze an algorithm to find the smallest element in an n-element bitonic array in $O (lo g n)$ time. You may assume that the numbers in the input array are distinct.

31.

Suppose we are given an array A[1 .. n] of n distinct integers, which could be positive, negative, or zero, sorted in increasing order so that

A [1] < A [2] < \dots < A [n] .

(a) Describe a fast algorithm that either computes an index i such that A[i] = i or correctly reports that no such index exists.

(b) Suppose we know in advance that A[1] > 0. Describe an even faster algorithm that either computes an index i such that A[i] = i or correctly reports that no such index exists. [Hint: This is really easy.]

32.

Suppose we are given an array A[1 .. n] with the special property that A[1] >= A[2] and A[n - 1] <= A[n]. We say that an element A[x] is a local minimum if it is less than or equal to both its neighbors, or more formally, if A[x - 1] >= A[x] and A[x] <= A[x + 1].

We can obviously find a local minimum in $O (n)$ time by scanning through the array. Describe and analyze an algorithm that finds a local minimum in $O (lo g n)$ time. [Hint: With the given boundary conditions, the array must have at least one local minimum. Why?]

33.

Suppose you are given a sorted array of n distinct numbers that has been rotated k steps, for some unknown integer k between 1 and n - 1. That is, you are given an array A[1 .. n] such that some prefix A[1 .. k] is sorted in increasing order, the corresponding suffix A[k + 1 .. n] is sorted in increasing order, and A[n] < A[1].

For example:

9 13 16 18 19 23 28 31 37 42 1 3 4 5 7 8

with k = 10.

(a) Describe and analyze an algorithm to compute the unknown integer k.

(b) Describe and analyze an algorithm to determine if the given array contains a given number x.

34.

At the end of the second act of the action blockbuster Fast and Impossible XIII 3/4: The Last Guardians of Expendable Justice Reloaded, the villainous Dr. Metaphor hypnotizes the entire Hero League/Force/Squad, arranges them in a long line at the edge of a cliff, and instructs each hero to shoot the closest taller heroes to their left and right, at a prearranged signal.

Suppose we are given the heights of all n heroes, in order from left to right, in an array Ht[1 .. n]. No two heroes have the same height. Then we can compute the left and right targets of each hero in $O (n^{2})$ time using the following brute-force algorithm.

WhoTargetsWhom(Ht[1 .. n]):
    for j <- 1 to n
        // Find the left target L[j] for hero j
        L[j] <- None
        for i <- 1 to j - 1
            if Ht[i] > Ht[j]
                L[j] <- i
 
        // Find the right target R[j] for hero j
        R[j] <- None
        for k <- n down to j + 1
            if Ht[k] > Ht[j]
                R[j] <- k
 
    return L[1 .. n], R[1 .. n]

(a) Describe a divide-and-conquer algorithm that computes the output of WhoTargetsWhom in $O (n lo g n)$ time.

(b) Prove that at least floor(n/2) of the n heroes are targets. That is, prove that the output arrays R[0 .. n - 1] and L[0 .. n - 1] contain at least floor(n/2) distinct values other than None.

(c) Alas, Dr. Metaphor’s diabolical plan is successful. At the prearranged signal, all the heroes simultaneously shoot their targets, and all targets fall over the cliff, apparently dead. Metaphor repeats his dastardly experiment over and over; after each massacre, he forces the remaining heroes to choose new targets, following the same algorithm, and then shoot their targets at the next signal. Eventually, only the shortest member of the Hero Crew/Alliance/Posse is left alive.

Describe and analyze an algorithm to compute the number of rounds before Dr. Metaphor’s deadly process finally ends. For full credit, your algorithm should run in $O (n)$ time.

35.

You are a contestant on the hit game show Beat Your Neighbors! You are presented with an m x n grid of boxes, each containing a unique number. It costs $100 to open a box. Your goal is to find a box whose number is larger than its neighbors in the grid, above, below, left, and right. If you spend less money than any of your opponents, you win a week-long trip for two to Las Vegas and a year’s supply of Rice-A-Roni, to which you are hopelessly addicted.

(a) Suppose m = 1. Describe an algorithm that finds a number that is bigger than either of its neighbors. How many boxes does your algorithm open in the worst case?

(b) Suppose m = n. Describe an algorithm that finds a number that is bigger than any of its neighbors. How many boxes does your algorithm open in the worst case?

36.

(a) Let n = 2^l - 1 for some positive integer l. Suppose someone claims to hold an unsorted array A[1 .. n] of distinct l-bit strings; thus, exactly one l-bit string does not appear in A. Suppose further that the only way we can access A is by calling the function FetchBit(i, j), which returns the jth bit of the string A[i] in $O (1)$ time. Describe an algorithm to find the missing string in A using only $O (n)$ calls to FetchBit.

(b) Now suppose n = 2^l - k for some positive integers k and l, and again we are given an array A[1 .. n] of distinct l-bit strings. Describe an algorithm to find the k strings that are missing from A using only $O (n lo g k)$ calls to FetchBit.

Trees

37.

For this problem, a subtree of a binary tree means any connected subgraph. A binary tree is complete if every internal node has two children, and every leaf has exactly the same depth. Describe and analyze a recursive algorithm to compute the largest complete subtree of a given binary tree. Your algorithm should return both the root and the depth of this subtree.

38.

Let T be a binary tree with n vertices. Deleting any vertex v splits T into at most three subtrees, containing the left child of v if any, the right child of v if any, and the parent of v if any. We call v a central vertex if each of these smaller trees has at most n/2 vertices.

Describe and analyze an algorithm to find a central vertex in an arbitrary given binary tree. [Hint: First prove that every tree has a central vertex.]

39.

(a) Professor George O’Jungle has a 27-node binary tree, in which every node is labeled with a unique letter of the Roman alphabet or the character &. Preorder and postorder traversals of the tree visit the nodes in the following order:

Preorder: I Q J H L E M V O T S B R G Y Z K C A & F P N U D W X
Postorder: H E M L J V Q S G Y R Z B T C P U D N F W & X A K O I

Draw George’s binary tree.

(b) Recall that a binary tree is full if every non-leaf node has exactly two children.

Describe and analyze a recursive algorithm to reconstruct an arbitrary full binary tree, given its preorder and postorder node sequences as input.
Prove that there is no algorithm to reconstruct an arbitrary binary tree from its preorder and postorder node sequences.

(c) Describe and analyze a recursive algorithm to reconstruct an arbitrary binary tree, given its preorder and inorder node sequences as input.

(d) Describe and analyze a recursive algorithm to reconstruct an arbitrary binary search tree, given only its preorder node sequence.

(e) Describe and analyze a recursive algorithm to reconstruct an arbitrary binary search tree, given only its preorder node sequence, in $O (n)$ time.

In parts (b) through (e), assume that all keys are distinct and that the input is consistent with at least one binary tree.

40.

Suppose we have n points scattered inside a two-dimensional box. A kd-tree recursively subdivides the points as follows. If the box contains no points in its interior, we are done. Otherwise, we split the box into two smaller boxes with a vertical line, through a median point inside the box, not on its boundary, partitioning the points as evenly as possible. Then we recursively build a kd-tree for the points in each of the two smaller boxes, after rotating them 90 degrees. Thus, we alternate between splitting vertically and splitting horizontally at each level of recursion. The final empty boxes are called cells.

(a) How many cells are there, as a function of n? Prove your answer is correct.

(b) In the worst case, exactly how many cells can a horizontal line cross, as a function of n? Prove your answer is correct. Assume that n = 2^k - 1 for some integer k. [Hint: There is more than one function $f$ such that $f (16) = 4$ .]

(c) Suppose we are given n points stored in a kd-tree. Describe and analyze an algorithm that counts the number of points above a horizontal line as quickly as possible. [Hint: Use part (b)]

(d) Describe and analyze an efficient algorithm that counts, given a kd-tree containing n points, the number of points that lie inside a rectangle R with horizontal and vertical sides. [Hint: Use part (c)]

41.

Bob Ratenbur, a new student in CS 225, is trying to write code to perform preorder, inorder, and postorder traversals of binary trees. Bob sort-of understands the basic idea behind the traversal algorithms, but whenever he actually tries to implement them, he keeps mixing up the recursive calls. Five minutes before the deadline, Bob frantically submits code with the following structure:

PreOrder(v):
    if v = Null
        return
    else
        print label(v)
        Order(left(v))
        Order(right(v))
 
InOrder(v):
    if v = Null
        return
    else
        Order(left(v))
        print label(v)
        Order(right(v))
 
PostOrder(v):
    if v = Null
        return
    else
        Order(left(v))
        Order(right(v))
        print label(v)

Each Order in this pseudocode hides one of the prefixes Pre, In, or Post. Moreover, each of the following function calls appears exactly once in Bob’s submitted code:

PreOrder(left(v))      PreOrder(right(v))
InOrder(left(v))       InOrder(right(v))
PostOrder(left(v))     PostOrder(right(v))

Thus, there are precisely 36 possibilities for Bob’s code. Unfortunately, Bob accidentally deleted his source code after submitting the executable, so neither you nor he knows which functions were called where.

Now suppose you are given the output of Bob’s traversal algorithms, executed on some unknown binary tree T. Bob’s output has been helpfully parsed into three arrays Pre[1 .. n], In[1 .. n], and Post[1 .. n]. You may assume that these traversal sequences are consistent with exactly one binary tree T; in particular, the vertex labels of the unknown tree T are distinct, and every internal node in T has exactly two children.

(a) Describe an algorithm to reconstruct the unknown tree T from the given traversal sequences.

(b) Describe an algorithm that either reconstructs Bob’s code from the given traversal sequences, or correctly reports that the traversal sequences are consistent with more than one set of algorithms.

For example, given the input

Pre[1 .. n]  = [H A E C B I F G D]
In[1 .. n]   = [A H D C E I F B G]
Post[1 .. n] = [A E I B F C D G H]

your first algorithm should return the following tree:

    H
   / \
  A   D
     / \
    C   G
   / \  /
  E  B I
     /
    F

and your second algorithm should reconstruct the following code:

PreOrder(v):
    if v = Null
        return
    else
        print label(v)
        PreOrder(left(v))
        PostOrder(right(v))
 
InOrder(v):
    if v = Null
        return
    else
        PostOrder(left(v))
        print label(v)
        PreOrder(right(v))
 
PostOrder(v):
    if v = Null
        return
    else
        InOrder(left(v))
        InOrder(right(v))
        print label(v)

42.

Let T be a binary tree whose nodes store distinct numerical values. Recall that T is a binary search tree if and only if either T is empty, or T satisfies the following recursive conditions:

The left subtree of T is a binary search tree.
All values in the left subtree are smaller than the value at the root.
The right subtree of T is a binary search tree.
All values in the right subtree are larger than the value at the root.

Consider the following pair of operations on binary trees:

Rotate an arbitrary node upward.
Swap the left and right subtrees of an arbitrary node.

(a) Describe an algorithm to transform an arbitrary n-node binary tree with distinct node values into a binary search tree, using at most $O (n^{2})$ rotations and swaps.

Your algorithm is not allowed to directly modify parent or child pointers, create new nodes, or delete old nodes; the only way to modify the tree is through rotations and swaps.

On the other hand, you may compute anything you like for free, as long as that computation does not modify the tree; the running time of your algorithm is defined to be the number of rotations and swaps that it performs.

(b) Describe an algorithm to transform an arbitrary n-node binary tree into a binary search tree, using at most $O (n lo g n)$ rotations and swaps.

(c) Prove that any n-node binary search tree can be transformed into any other binary search tree with the same node values, using only $O (n)$ rotations and no swaps.

(d) Open problem: Either describe an algorithm to transform an arbitrary n-node binary tree into a binary search tree using only $O (n)$ rotations and swaps, or prove that no such algorithm is possible. [Hint: I don’t think it’s possible.]

Prev: Introduction Next: Backtracking

Takashi's Notes

Explorer

Recursion

Recursion

Exercises

Tower of Hanoi

1.

2.

3.

4.

5.

Recursion Trees

6.

7.

8.

Sorting

9.

10.

11.

12.

13.

14.

15.

Selection

16.

17.

18.

19.

20.

21.

Arithmetic

22.

23.

24.

25.

Arrays

26.

27.

28.

29.

30.

31.

32.

33.

34.

35.

36.

Trees

37.

38.

39.

40.

41.

42.

Graph View

Table of Contents

Backlinks