There is a class of folk songs and holiday sours in which each verse consists of
ID: 3636998 • Letter: T
Question
There is a class of folk songs and holiday sours 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, etc. all the way to the partridge In the pear tree. The Aramaic song "Had gadya" from the Passover Haggadah and the French song "Y'a qu'un cheveu sur la tete a Mathieu" work 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 is something asymptotic that can be analyzed here. Suppose, for concreteness, that each line has a length that is bounded by a constant number of words 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 in O(f), for a function f(n)that rows as slowly as possible. You should specify what the function f(n) is, and prove that your encoding's length is in O(f).Explanation / Answer
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)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.