PLEASE SHOW ALL WORK AND EXPLAIN ANSWERS. THANKS. 7. There\'s a class of folk so

Question

PLEASE SHOW ALL WORK AND EXPLAIN ANSWERS. THANKS.

7. There's a class of folk songs and holiday songs in which each verse consists of the previous verse, with one extra line added on. "The Twelve Days of Christmas" has this property; for example, when you get to the fifth verse, you sing about the five golden rings and then, reprising the lines from the fourth verse, also cover the four calling birds, the three French hens, the two turtle doves, and of course the partridge in the pear tree. The Aramaic song "Had gadya" from the Passover Haggadah works like this as well, as do many other songs. These songs tend to last a long time, despite having relatively short scripts. In particular, you can convey the words plus instructions for one of these songs by specifying just the new line that is added in each verse, without having to write out all the previous lines each time. (So the phrase "five golden rings" only has to be written once, even though it will appear in verses five and onward.) There's something asymptotic that can be analyzed here. Suppose, for concreteness, that each line has a length that is bounded by a constant c, and suppose that the song, when sung out loud, runs for n words total. Show how to encode such a song using a script that has length f(n), for a function f(n) that grows as slowly as possible.

Explanation / Answer

ans:

Let f(n) = n

Encoding Mechanism: Specify the string that is used for all stanzas, followed by the new occurrences i each stanza one after the other:
Example:
On the kth day of Christmas, my true love gave to me

A Partridge in a Pear Tree

2 Turtle Doves

3 French Hens

.... and so on

Proof that encoding is O(n)
Total no of words in encoding = k + cn
where k is the no. of words used for encoding the string that is used in all stanzas (On the first day of Christmas, my true love gave to me)
So, no. of words = k+cn < (c+1)n for sufficiently large n
Hence, encoding is O(n)

please rate

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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