Algorithms Design – Chapter 2, Exercise 7

On By pdinizIn Algorithms Design, Book, Solved Exercise

I’m having a hard time trying to find the solutions for this book on the web, so, to help others interested, i’m sharing what i’ve managed to solve at the moment =).

This is a solved exercise from the book “Algorithms Design” from Jon Kleinberg and Éva Tardos. All the answers / solutions in this blog were made from me, so it may contain errors, please check with your instructor in order validate it.

Algorithms Design – Chapter 2, Exercise 7

Question: 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.

Answer:

With a help from my friend Jaisse, i’ve managed to find that:

The question ask us to encode the music.  And this means that we need to create an algorithm capable of singing the song to reproduce “n” words.

//Define a script with K "lines" where each line
//represents a unique verse of the song.
//Now use the algorithm to produce the music:
For i=1,2,...,K
   For j=1,...,i
       sing scriptLine[j]
   End for
End for

OK, now we have an algorithm that reads a script and sings the music.

We call this encoding because, instead of having a file with “n” words to be sung, we only have a small script with “K” words and an algorithm capable of reproducing the long “n” words only when necessary.

We have managed to reduce from “n” words to “K” words, but how much less is “K” compared to “n”?

Well, since the algorithm performs exactly like a sum in the form: \displaystyle\sum_{i = 1}^{K} i, which is an Arithmetic Progression, we can use the Arithmetic Progression formula to say that this algorithm has complexity \frac{K(K+1)}{2}.

Knowing that the algorithm outputs “n” words, we also know that  \frac{K(K+1)}{2} \leq n.  Then to make it easier for us to find a good bound, we could say that \frac{k^2}{2} \leq \frac{K(K+1)}{2} \leq n, then \frac{k^2}{2} \leq n, and finally k \leq \sqrt{2n}. Which means k \in O(\sqrt{n})

7 thoughts on “Algorithms Design – Chapter 2, Exercise 7”

  1. Fausto

    In the last part of your analysis, how did you get the lower bound k^2/2<=k(k+1)/2? how did the k^2/2 come from? I don't understand why it is valid that you use that. Thanks!

    Reply

    1. Hi Fausto, first, thanks for your comment =).
      Feel free to ask/contribute with whatever you want.
      Returning to your question, let me try to give you a better answer:
      — We need to discover what is the size of “k” when compared to “n”, knowing that (k(k+1))/2 <= n. This is the same as (k^2+k)/2 <= n.
      We can now just solve this (more complex) equation, and we will have the upper boundary for "k" in "n", which will be something around O(square{n}).
      I've reduced the equation to (k^2)/2 because it is even simpler to see how it is related to O(square{n}).
      Since (k^2)/2 <= (k(k+1))/2 and (k(k+1))/2 <= n, it is implicit that (k^2)/2 <= n.
      Now it's easy to see that the upper boundary for "n" will be something around square{n}
      Why did i used (k^2)/2? Because it is something that i can prove it is true ((k^2+k)/2 <= n) and will be simpler to prove.
      Why is it valid? Because we know that (k^2)/2 <= (k(k+1))/2 and (k(k+1))/2 <= n, so (k^2)/2 <= n has to be valid.

      Reply
  2. Anonymous

    there are 2 for loops then how come the time complexity be compared with only the number of lines e.g. using (k+1)k/2<=n.
    i mean to say that can you explain me the complexity with respect to the algorithm again if possible.

    Reply

    1. Sure! I believe I oversimplified the summation, lets extend it to make it clearer. First let it be noted that scriptLine(j) is a constant operation, it prints the line j only, so it is a O(1) operation. Now lets represent the whole algorithm as a single expression: \sum_{i=1}^{k}\sum_{j=1}^{i}scriptLine(j) = \sum_{i=1}^{k}\sum_{j=1}^{i}1 = \sum_{i=1}^{k}i. See, it is the same summation that we defined in the beginning of the exercise, so it leads to the same Arithmetic Progression which can be formulated as (k+1)k/2. The rest follows as we described in the original answer =). If this is not exactly what you’re asking please let me know, I will try again!

      Reply

    1. Hi Likitha! Yes, I also wrote the answers for the first 7 exercises of chapter 3 but I got discouraged from posting them. I’ve read in some manual that the authors didn’t want the answers to be arbitrarily shared (so to make sure that students will actually try to do exercises). I don’t know if this indeed proceeds but if the book doesn’t provide the answers there must be a reason =/.

      Reply

Leave a comment