Introduction

Next: Recursion

Exercises

0.

Describe and analyze an efficient algorithm that determines, given a legal arrangement of standard pieces on a standard chess board, which player will win at chess from the given starting position if both players play perfectly.
[Hint: There is a trivial one-line solution!]

1.

(a) Identify (or write) a song that requires $\Theta (n^3)$ time to sing the first $n$ verses.

(b) Identify (or write) a song that requires $\Theta (n\log n)$ time to sing the first $n$ verses.

(c) Identify (or write) a song that requires some other weird amount of time to sing the first $n$ verses.

2.

Careful readers might complain that our analysis of songs like ”$n$ Bottles of Beer on the Wall” or “The $n$ Days of Christmas” is overly simplistic, because larger numbers take longer to sing than shorter numbers. More generally, because there are only so many words of a given length, larger sets of words necessarily contain longer words. We can more accurately estimate singing time by counting the number of syllables sung, rather than the number of words.

(a) How long does it take to sing the integer $n$?

(b) How long does it take to sing ”$n$ Bottles of Beer on the Wall”?

(c) How long does it take to sing “The $n$ Days of Christmas”?

As usual, express your answers in the form $O(f(n))$ for some function $f$.

3.

The cumulative drinking song “The Barley Mow” has been sung throughout the British Isles for centuries. The song has many variants; Figure 0.6 contains pseudolyrics for one version traditionally sung in Devon and Cornwall, where vessel[i] is the name of a vessel that holds $2^i$ ounces of beer.

BarleyMow(n):
    "Here's a health to the barley-mow, my brave boys,"
    "Here's a health to the barley-mow!"
    "We'll drink it out of the jolly brown bowl,"
    "Here's a health to the barley-mow!"
    "Here's a health to the barley-mow, my brave boys,"
    "Here's a health to the barley-mow!"
 
    for i <- 1 to n
        "We'll drink it out of the vessel[i], boys,"
        "Here's a health to the barley-mow!"
 
        for j <- i downto 1
            "The vessel[j],"
            "And the jolly brown bowl!"
            "Here's a health to the barley-mow!"
    "Here's a health to the barley-mow, my brave boys,"
    "Here's a health to the barley-mow!"

(a) Suppose each name vessel[i] is a single word, and you can sing four words a second. How long would it take you to sing BarleyMow(n)? (Give a tight asymptotic bound.)

(b) If you want to sing this song for arbitrarily large values of $n$, you’ll have to make up your own vessel names. To avoid repetition, these names must become progressively longer as $n$ increases. Suppose vessel[n] has $\Theta (\log n)$ syllables, and you can sing six syllables per second. Now how long would it take you to sing BarleyMow(n)? (Give a tight asymptotic bound.)

(c) Suppose each time you mention the name of a vessel, you actually drink the corresponding amount of beer: one ounce for the jolly brown bowl, and $2^i$ ounces for each vessel[i]. Assuming for purposes of this problem that you are at least 21 years old, exactly how many ounces of beer would you drink if you sang BarleyMow(n)? (Give an exact answer, not just an asymptotic bound.)

4.

Recall that the input to the Huntington-Hill algorithm ApportionCongress is an array Pop[1..n], where Pop[i] is the population of the $i$th state, and an integer R, the total number of representatives to be allotted. The output is an array Rep[1..n], where Rep[i] is the number of representatives allotted to the $i$th state by the algorithm.

The Huntington-Hill algorithm is sometimes described in a way that avoids the use of priority queues entirely. The top-level algorithm “guesses” a positive real number $D$, called the divisor, and then runs the following subroutine to compute an apportionment. The variable $q$ is the ideal quota of representatives allocated to a state for the given divisor $D$; the actual number of representatives allocated is always either $\lceil q\rceil$ or $\lfloor q\rfloor$.

HHGuess(Pop[1..n], R, D):
    reps <- 0
    for i <- 1 to n
        q <- Pop[i] / D
        if q * q < ceil(q) * floor(q)
            Rep[i] <- floor(q)
        else
            Rep[i] <- ceil(q)
        reps <- reps + Rep[i]
    return reps

There are three possibilities for the final return value reps. If reps < R, we did not allocate enough representatives, which (at least intuitively) means our divisor $D$ was too small. If reps > R, we allocated too many representatives, which (at least intuitively) means our divisor $D$ was too large. Finally, if reps = R, we can return the array Rep[1..n] as the final apportionment. In practice, we can compute a valid apportionment (with reps = R) by calling HHGuess with a small number of integer divisors close to the standard divisor $D=P/R$.

In the following problems, let

$$P=\sum _{i=1}^n\mathrm{Pop}[i]$$

denote the total population of all $n$ states, and assume that $n\le R\le P$.

(a) Show that calling HHGuess with the standard divisor $D=P/R$ does not necessarily yield a valid apportionment.

(b) Prove that if HHGuess returns the same value of reps for two different divisors $D$ and $D^{\prime }$, it also computes the same allocation Rep[1..n] for both of those divisors.

(c) Prove that if HHGuess returns the correct value $R$, it computes the same allocation Rep[1..n] as our earlier algorithm ApportionCongress.

(d) Prove that a “correct” divisor $D$ does not necessarily exist! That is, describe inputs Pop[1..n] and R, where $n\le R\le P$, such that for every real number $D>0$, the number of representatives allocated by HHGuess is not equal to $R$. [Hint: What happens if we change < to <= in the fourth line of HHGuess?]

Next: Recursion