1. \"The Barley Mow\" is a cumulative drinking song which has been sung througho

Question

1. "The Barley Mow" is a cumulative drinking song which has been sung throughout the British Isles for centuries. (An early version entitled "Giue vs once a drinke" appears in Thomas Ravenscroft's song collection Deuteromelia, which was published in 1609, but the song is almost certainly much older.) The song has many variants, but one version traditionally sung in Devon and Cornwall has the following pseudolyrics, where vessel[i] is the name of a vessel that holds 2' ounces of beer. The traditional song uses the following vessels: nipperkin, gill pot, half-pint, pint, quart, pottle, gallon, half-anker, anker, firkin, half-barrel, barrel, hogshead, pipe, well, river, and ocean. (Every vessel in this list is twice as big as its predecessor, except that a firkin is actually 2.25 ankers, and the last three units are just silly.) 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 1 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. ("We'll drink it out of the hemisemidemiyottapint, boys!") Suppose vessel[n] has (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 corre- sponding amount of beer: one ounce for the jolly brown bowl, and 2' 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.)

Explanation / Answer

a.

It is given that each vessel[i] is a single word and that one can sing four words per second.

BarleyMow(n) contains a constant number of words added while ignoring all the `vessel[i]` values. Let us assume that to be K.

Now, let us count the number of words added by the variable n to the song. The outer i loop runs for n iterations and each iteration contains a single mention of vessel[i] followed by a mention of vessel[i], vessel[i - 1], vessel[i - 2] ... vessel[1] (courtesy the j loop)

Hence the total number of times a vessel is mentioned can be found easily by dry-running the song pseudocode, it is as follows:

i = n, count = n + 1, vessel[n] + (vessel[n] + vessel[n - 1] ... vessel[1])
i = n - 1, count = n, vessel[n - 1] + (vessel[n - 1] + vessel[n - 2] ... vessel[1])
i = n - 2, count = n - 1
.
.
.
i = 1, count = 2

Hence total number of mentions = (n + 1) + n + (n - 1) + (n - 2) ... + 2 = n + (n * (n + 1) / 2)

Total number of words = n + (n * (n +1)/2) + K

time taken to sing BarleyMow(n) = Number of words / 4 = (n + (n * (n + 1) / 2) + K) / 4 = (n2) seconds

b.

Let total number of syllables added while ignoring all the vessel[i] mentions be K.

Total number of syllables added by one iteration of the outer i loop:

first mention outside j loop: log(i)
j = i: log(i)
j = i - 1: log(i - 1)
j = i - 2: log(i - 2)
...
j = 1: log(1)

total number of syllables added in one i iteration = log(i) + log(i) + log(i - 1) + log(i - 2) ... + log(1)
                          = log(i * i * (i -1) * (i - 2) ... 1)
                          = (i log i)

Therefore, total number of syllables added in ALL iterations = (i*log(i)) <= n(n*log(n)) = (n2*log(n))

Hence the amount of time taken to sing BarleyMow(n) = (n2*log(n)) seconds

c.

Ounces added by jolly brown bowl = 1

Now let us find ounces added when i = k:

    vessel[i] adds 2^k (outside j loop)
    vessel[i] adds 2k + 2k-1 + 2k-2 ... 21 = 2k+1 - 1 (inside j loop)
    total = 2k + 2k+1 - 1 = 3 * 2k- 1

hence total ounces to be drunk:

    (3 * 2k - 1) = 3(2k) - 1 = 3(2k+1 - 1) - k

Answer = 3 * (2k+1 - 1) - k

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.