QR 48 Assignment 1
Due Friday, February 20 at the beginning of class.

  1.  
    1. (3 points) Suppose I send 25 random facts about myself to 25 other people and ask them to wait a day and then do the same thing, sending 25 random facts about themselves to 25 other people. If everybody manages to send their lists to 25 people who haven't been contacted before, how long will this go on before everyone on earth has been contacted?  (You can assume that everyone in the world can be reached.)
    2. (3 points) If you are on Facebook, you may have seen some of your friends (perhaps even you!) fill out ‘25 Random Things About Me’, which is then sent on to other friends. According to an article in Time magazine (http://www.time.com/time/arts/article/0,8599,1877187,00.html), approximately 5 million of Facebook’s  130 million users sent 25 facts to their friends in just one week. Assuming that it takes one day for Facebook users who receive a notice from friends to fill out their own random facts, how many Facebook users on average post a new ‘25 Random Things’ out of the 25 users who are invited to do so.  (Hint: use the formula for exponential growth.)
    3. (3 points) Using your answer from part B (If you can’t figure out part B, just pick a number between 1 and 25), answer the following: How long would you expect it to take for all 130 million active Facebook users to fill out a ‘25 Random Things About Me’ note?  Explain why your answer might not be reached in practice.
  2. In this problem, half of the exercise is to find some estimates of the size of things. Whatever estimates you use, state them; the problem is to draw reasonable conclusions from reasonable assumptions, not to get any one “right” answer. Use Google or whatever your favorite search engine is, and explain where you got your numbers.

 

  1. (2 points) The new version of the Amazon Kindle can store 1500 books in its 2GB of memory (http://www.pcmag.com/article2/0,2817,2340623,00.asp).  At this rate, what size is an average book?
  2. (3 points) Jeff Bezos, Amazon’s founder, has stated that his goal for the Kindle is to make every book available for download.  Let’s go one step further – how much storage would be required to hold Widener Library? 
  3. (3 points) According to “Kryder’s Law”, disk storage capacity doubles annually.  Given that the Kindle is  2GB today, how many years will it take before you can store all of Widener Library on a Kindle-like device if Kryder’s Law continues to hold?
  4. (2 points) Hard disk drives used in desktop PCs can store far more than mobile devices such as Kindles and iPods.  Currently, a one terabyte disk drive can be purchased for around $100.  In how many years might you expect to store all of Widener Library on a single hard disk drive?
  1. The members of the Itty Bitty Kitty Committee are stranded on a life raft after their ship sank. They need to send a message out so that they can be rescued, but all they have is a cell phone that has just enough battery power left to transmit a few bytes of data. Afraid that their message will be too long to send, they decide to compress it with a Huffman code. Help the kitties send their message, which you can find in this picture:

kitty.jpg

    1. (3 points) Calculate the entropy of the message.  (Hint: use the character frequency and the entropy equation.)
    2. (4 points) Create a Huffman code for the message; don’t forget to show all of your work.
    3. (3 points) Encode the message using the Huffman code you created and write down its bit representation. How long is it?
    4. (3 points) Using your entropy calculation from part A, what is the efficiency of your compression?
    5. (2 points) Convert the message to its binary ASCII representation (remember, you can use tools from the web – there’s no need to do this by hand). How long is the message in bits?  Is it safe to say that the kitties can communicate using fewer bits using their custom Huffman-encoded transmission when compared to standard ASCII?

     

  1. A single 43-minute episode of the television show Lost is available for download on iTunes in both standard definition and high definition.  The high-definition version is 1.43 gigabytes, and the standard-definition version is 632 megabytes.  The same episode sent across the wire on Verizon FiOS TV took 8.17 gigabytes for 62 minutes, including commercials.
    1. (1 point).  What size would the FiOS transmission have been had there been no commercials?
    2. (1 point).  Compare the size of the iTunes HD version to the FiOS HD version.  How much smaller is the iTunes version?
    3. (2 points) Verizon FiOS high-speed internet advertises a download speed of up to 20 megabits per second.  Assuming you were able to get that maximum download rate continuously, how long would it take you to get the high-definition version of the episode from iTunes?  What about the standard definition version?
    4. (3 points) The truth is that real-world speeds rarely approach the maximums that are advertised.  A more typical speed is 7 megabits per second.  At a continuous rate of 7 megabits per second, how long would it take to get the high-definition version of the episode from iTunes?  What about the standard definition version?  And finally, what about the television version?