COS 109: Problem Set 8

COS 109: Problem Set 8 (Last one!)

Tue Nov 5 07:14:15 EST 2024

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.

1. Key Rings

One major problem with secret-key cryptographic systems (which we will cover in class soon) is the proliferation of keys if secret information is to be shared among different independent combinations of people.

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

Each one of them needs to protect their own personal information, for which each needs an individual password.
Each person needs to carry on private conversations with each other person. That is, Alice and Bob want to talk without Carol being able to know what they are saying, so Alice and Bob need to share a password for their private conversations, and that password is different from their individual passwords. Similarly, Alice and Carol want to talk without Bob, so they need to share a password between themselves. And so on: each such combination requires a separate different password;
Alice, Bob and Carol need to talk among themselves while preventing outsiders from understanding those larger-group conversations as well -- yet more different passwords are needed.

How many different passwords do Alice, Bob and Carol need in total? List the passwords by the people who will share them.

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

2. Lottabytes

(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? You will have to come up with a plausible estimate for the number of letters in a book.

(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? Hint: think about bits and binary.

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

3. IP Addresses

An IPv4 address is a 32-bit integer.

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

4. You Can't Get There From Here

One of the original design goals of ARPANET, the precursor of the Internet, was that it should be fault-tolerant and able to survive incidents that destroyed parts of it. In that spirit, here is a fake network with routers (the red circles) and links between them (the lines). There are no connections except at routers.

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?

Submission

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.