COS 109: Problem Set 8 (last one!)

Mon Nov 17 15:59:21 EST 2014

Due 5:00 PM, Wednesday, Dec 3 (after break), in the box outside Room 311, CS building, or in class. Answers need not be long, merely clear so we can understand what you have done. Please submit typed material, not hand-written, if at all possible, and keep a copy for yourself just in case something goes astray. Thanks.

Collaboration policy for COS 109: Working together to really understand the material in problem sets and labs is encouraged, but once you have things figured out, you must part company and compose your written answers independently. That helps you to be sure that you understand the material, and it obviates questions of whether the collaboration was too close.

You must list any other class members with whom you collaborated.

 

 

1. Potpourri

(a) A story in the New York Times on 11/21/11 said that Microsoft sells "a copy of Office 2010 every second -- over 100 million so far." Microsoft's Office division revenue is nearly $6 billion per year. Using these facts,
    (i) Very roughly, how long had Office 2010 been on sale at the time the article was written?
    (ii) About how much does one copy of Office 2010 cost?

(b) CBS Evening News said 3 or 4 years ago that at $1 per second, it would take 425,000 years to pay off the US national debt. Very roughly, what would the corresponding number of years be today?

(c) An article in Physical Review Letters says that there really is an absolute limit to Moore's Law. Simplifying the numbers a bit, it implies that there is still a factor of 10^15 to be had from repeated doublings of capacity by making things smaller. If the doubling time is the usual 18 months, how many years from now will Moore's Law finally run out?

(d) Older versions of Excel support 65,536 rows; columns are labeled A, B, ..., AA, AB, ..., through IV. Give a likely reason why the last column has that label.

(e) Microsoft's web page says that Excel 2007 "increases the maximum number of rows per worksheet from 65,536 to over 1 million," and says that the last column is now labeled XFD.
    (i) How many bits are likely used to represent the row number in Excel 2007?
    (ii) Explain briefly where "XFD" likely comes from.

(f) In an IPv4 address, the first part is the net id and the rest is the host id on that net. If there are N bits in the net id part, what is the maximum number of host ids that could be on that network?

(g) A story in the Prince on 11/4/14 says that in the 2008-2009 academic year, "Princeton students printed 11,040,632 sheets of paper, enough to stretch from Princeton to Salt Lake City, or a stack 17 times taller than Fine Hall."
    (i) Using this factoid, compute approximately how far Salt Lake City is from Princeton.
    (ii) Approximately how tall is Fine Hall?

 

2. Key Rings

One major problem with secret-key cryptographic systems like DES and AES is key distribution -- how to send a secret key to the other people you want to talk to. This question concerns a second major problem -- the proliferation of keys if various information is to be shared among different independent combinations of people.

(a) Suppose that Alice, Bob and Carol have a relationship in which each person wishes to encrypt their own personal information (for which each needs an individual key) and also carry on private conversations with each other person (i.e., Alice and Bob want to talk without including Carol, and Alice and Carol want to talk without Bob, and so on), and also talk among all three so that outsiders can't understand those conversations either. How many different secret keys do they need in total? List the keys by the people who will share them.

(b) Suppose that David joins the group, and relationships are even more complicated: they need keys for every individual and every possible combination of private conversations among subgroups (e.g., Alice, Carol and David want to be able to talk among themselves while excluding Bob) as well as excluding outsiders. How many different secret keys are now needed? List the keys by the people who will share them.

(c) As the group grows, more and more keys will be needed. Give a general formula or way to express how the number of keys varies as a function of N, the number of people involved. If you don't see a formula, then give the numbers you have computed, for 1 through 6 people.

(Hint: figure out how many keys are needed for one person, for two people and for five people, combine that with what you did above, and look for a pattern. A different hint: make a column for each person, then for each group put a 1 in column i if person i is a member of that subgroup and 0 otherwise.)