Due midnight Wednesday November 13
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.
For this problem, a "key" is just "a password" that is potentially shared with other people.
(a) Suppose that Alice, Bob and Carol have a relationship in which
(b) Suppose that David joins the group, and relationships are even more complicated: they need passwords for each individual and each 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 from all combinations. How many different secret passwords are now needed? List the passwords by the people who will share them.
(c) As the group grows, more and more passwords will be needed. Give a general formula or way to express how the number of passwords varies as a function of N, the number of people in the group. If you don't see a formula, then give the numbers you have computed, for 1 through 6 people.
(Hint: figure out how many passwords are needed for one person, for two people, and so on up to five people, combine that with what you did above, and look for a pattern.)
(a) A draft book chapter on DNA evidence (which I struggled unsuccessfully to understand) says "The human genome has more than 3 billion `letters' (A, T, G, C)." That is, the genome is just a very long sequence of those four letters. If these letters were printed in books, the resulting pile would be as high as the Washington Monument." Is this estimate much too high, much too low, or maybe in the right ballpark, and why do you say so?
(b) Reporting a similar number, the NY Times said in June 2007, "The human genome consists of some 2.9 billion of the letters AGCT -- the equivalent of about 750 megabytes of data." How could you encode the letters A, G, C and T so that you could fit the genome into 750 MB?
(c) A report from UC Berkeley 20+ years ago estimated that in the year 2002 "the human species stored about five exabytes of new information on paper, film, optical or magnetic media, a number that has doubled in the past three years." If data accumulation does double every three years and if it did amount to 5 EB in 2002 (and if this exponential process continues smoothly), in what year would the annual amount stored be 5 yottaabytes?
(d) In what year would it be 5 quettabytes?
(a) If the IPv4 address 63.254.255.255 is stored in a 32-bit integer variable v and incremented by the statement v = v+1, what is the resulting value, also expressed in dotted decimal notation?
(b) What is that resulting value expressed in hexadecimal?
(c) In an IPv4 address, the first part is the network id and the rest is the host id on that net. If there are N bits in the network id part, what is the maximum number of host ids that could be on that network?
Let's test its survivability. There may be multiple answers to some of these questions; you only need to give one.
(a) What is the smallest set of links that you would have to destroy to completely disconnect Princeton from Stanford? List the links by their endpoints, for example A-G or Stanford-B.
(b) If a router is destroyed, any link connected to it no longer works. What is the smallest set of routers (not including Stanford or Princeton themselves) that you would have to destroy to disconnect Princeton from Stanford? List the routers by letter.
(c) What routers are exactly two "hops" away from Princeton? That is, what routers can you reach from Princeton by following a path that goes through exactly two links? Don't count direct loopbacks like Princeton-D-Princeton; that is, Princeton is not two hops from Princeton. (Note that there are some situations where a node can be reached by paths of different lengths.)
(d) What is the shortest path (that is, the path with the fewest links) from Princeton to Stanford? Give the sequence of routers that make up the path.
(e) What is the longest path from Princeton to Stanford that doesn't have a loop, that is, that doesn't go through any router more than once?
Please use this Google Doc template for your answers. It would be a great help if you could type your answers.
Submit your problem set by uploading a file called pset8.pdf to Gradescope. You can submit as many times as you like; we will only look at the last one.
