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. |
(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?
(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.)