Problems 2.5b (10 points) and 2.7 (20 points), due Thursday 9/29.
For 2.7, if you aren't familiar with the song under discussion, it is this one:
http://en.wikipedia.org/wiki/The_Twelve_Days_of_Christmas_(song)
Please don't read the whole article--all we care about is the structure of the lyrics. (Search for "structure" in the article).
Thanks to Lucia for pointing out the link. I suppose most of the class knows the song, which can be hard to escape from at a certain time of year.
About #7. I looked through a lot of cumulative songs and all of them not just add a line to every stanza, but they change something else. For example, The Twelve Days of Christmas goes "On the Nth day of X-mas," changing the number of the day. Do we have to consider this details, or it'll be sufficient enough to add just an extra line to the previous stanza?
ReplyDeleteI'll wait to give students a chance to post on this.
ReplyDeleteIt may help to actually write some code to print out the song. Just remember that the whole song must come from the code---no loading in verse data from external files. Then figure out the relationship between the growth rate for your code and the growth rate for its output.
I wrote some code to print out the song, and was able to draw the same conclusing as given in the problem statement - "you can convey the words plus instructions for one of these songs by specifying just the new line that is added to each verse, without having to write all the previous lines each time". From here you can say something about how the length of the program grows vs the length of the song. Lines of code vs lines in the song seems like a good measure to me, but the problem statement goes on to talk about words and lines being bounded by at most some constant c words. What is the question trying to get at here?
ReplyDeleteI wrote some code to get some visualization as to what was going on. I can also see a relationship between the number of lines of code,the length of the song, and the number of words. From the last line in the problem "Show how to encode such a song using a script that has length f(n) that grows as slowly as possible". To me it just sounds like we are to optimize the algorithm we used to write the song. Since the problem also mentions analyzing the asymptotic growth, are we also analyzing the algorithm we came up with?
ReplyDelete@kdpotter The constant C tells how long the longest line of the song is. For instance, in the original song, the longest line is 6 words: "a partridge in a pear tree" We are going to assume that when this gets extended to more and more days, the longest line never gets longer than C words. If the number of days gets really big, this might mean we have to start repeating lines, but don't worry about that.
ReplyDelete@julian, in short, yes. But remember that we are only analyzing asymptotic growth up to constant factors. So optimization that doesn't help by more than a constant factor will not change your answer.
I am really confused here. What are we analyzing? The asymptotic growth of space that algorithm takes as apposed to the song that it might take when written down?
ReplyDeleteI am with you Lucia, I programmed it assuming that all the words are in three String[] arrays: words of the song in order like {"And", "a", "Partrige",...},
ReplyDeletedays like {"first",...}, and then the
main verse excluding the day....Thus far I have a i = 0 to 11 for the days, a recursive function that puts the words together in a string verse 1 and so on.
Plus, a loop for the print outs which does 1 for i = 0, 2 for i = 1 and so on... But
I could be totally off here :(
I think it might be similiar to hw3 question 6 with the double array B???
Now I would generalize it. Line 1, Line 2, Line 3, ...
ReplyDeleteAnd toss away the rest of the arrays.
I was reading the question over and over again, and it says the output is n total words which for 12 days like 400+, but then it says the script has a length f(n) which is also the output??
ReplyDeleteI would think that the input would be the non-repeating words of the song ~ 50, and the output is all the repeating words actually sung outloud ~ 400+???
Reading the question, my feeling is that we are basically developing a generic script to generate a generic song... and we can use pseudo-code for the question.
ReplyDeleteThat should eliminate problems like how the text is put in the data structure, and exact wording on the song.
Then, we just need to evaluate the algorithm as it grows.
For those of you confused about problem 2.7 I think I've figured it out and I'll share what really helped me when thinking about the problem.
ReplyDeleteTry to not get confused about n versus f(n). These are related, but different things. From the problem it states that n is the # of words sung out loud and f(n) is the length of the physical script.
It states in the problem that "these songs tend to last a long time, despite having relatively short scripts" what does this say about the relation between n (words sung out loud) compared to f(n)? Which one do you think grows faster over time?
I hope this helps you guys out. I'm still trying to work the final solution out myself, but I hope this will help other people get started on the right track.
@Krista 9/26 3:45PM
ReplyDeleten is the output length
f is the script length
These are related, so we can think of f as a function of n, or vice versa.
The problem basically wants you to find an equation relating f to n, and solve it to get a formula for f in terms of n.
If you prefer, call the script length L instead, and do the above. Then your formula for L is the function f(n) you are supposed to derive.
L will be not just the number of distinct words. It also has to include all the instructions for how to write out the full lyrics. Ken's comment is right--the script can be in any programming language, even (well-written) pseudocode or plain English.
I also agree with Lucas's comment, and hope this helps.
Hint: To derive a relation between L and n, it may help to relate each of L and n to something else, like the number of days.
So I have to share this video since we are talking about the Twelve days of Christmas, though don't watch it if you haven't finished 2.7, I don't want to confuse anyone!
ReplyDeletehttp://youtu.be/2Fe11OlMiz8