COS 109: Problem Set 7

Tue Nov 11 20:49:33 EST 2014

Due 5:00 PM, Wednesday, Nov 19, 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. Getting from Here to There

Signals propagate in electronic circuits at about 1/3 of the speed of light in vacuum, and there is more overhead as well, but the times reported by traceroute can be used to guess where routers are. Here is the output of running traceroute to determine the path from the CS building at Princeton to the University of Tokyo in Japan, except that the machine names have been removed. The times are for the round-trip.

traceroute to www.u-tokyo.ac.jp (133.11.128.254), 30 hops max, 40 byte packets
1    (128.112.139.1)  1.275 ms  0.654 ms  0.577 ms
2    (128.112.138.2)  0.739 ms  0.581 ms  0.650 ms
3    (128.112.139.193)  1.105 ms  0.927 ms  0.807 ms
4    (128.112.128.114)  1.193 ms  1.059 ms  1.074 ms
5    (128.112.12.22)  1.227 ms  1.189 ms  1.031 ms
6    (198.32.42.65)  2.900 ms  2.589 ms  2.843 ms
7    (198.32.42.210)  6.059 ms  5.847 ms  5.716 ms
8    (198.32.8.65)  21.521 ms  23.906 ms  21.116 ms
9    (198.32.8.33)  40.906 ms  40.853 ms  41.009 ms
10   (198.32.8.21)  72.680 ms  72.533 ms  72.569 ms
11   (203.181.248.130)  204.635 ms  204.082 ms  203.898 ms
12   (203.181.249.42)  204.063 ms  205.502 ms  204.248 ms
13   (203.178.140.216)  204.136 ms  204.797 ms  204.253 ms
14   (203.178.138.244)  204.990 ms  204.431 ms  203.957 ms
15   (133.11.125.201)  215.651 ms  215.841 ms  215.192 ms
16   (133.11.127.66)  206.884 ms  206.185 ms  206.517 ms
17   (133.11.127.41)  216.537 ms  215.043 ms  215.092 ms
18   (133.11.125.82)  206.505 ms  206.536 ms  206.668 ms
19   (133.11.128.254)  215.367 ms  215.269 ms  215.841 ms

Without using the web, answer the following questions:

Which sites are inside Princeton, and how do you know?
Which sites are outside Princeton but (probably) still in the United States, and how do you know?
Which sites are (probably) in Japan, and how do you know?
Which sites are inside the University of Tokyo, and how do you know?

2. 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-B or Stanford-F.

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

(f) Suppose that you want to build a network in which every router can communicate with every other router, either directly or indirectly by passing information through other routers. For that kind of network, what is the absolute minimum number of links necessary to connect R routers?

3. A Bit More Bits and Bytes

(a) "... just 33 genes, each coming in just two varieties (such as on or off), would be enough to make every human being in the world unique. There are more than 10 billion ways of flipping a coin 33 times." (Nature via Nurture, Matt Ridley, 2003). Are these two statements consistent, and if not which one is wrong? (This is a question about numbers, not genomics.)

(b) What is the ratio of possible Ethernet addresses to the number of possible IPv4 addresses?

(c) Chess is played on an 8 by 8 board with columns labeled a through h and rows labeled 1 through 8. The two players alternate by moving a piece from one square to another, for example e2 to e4, until one player wins or the game is a draw. The sequence of "from" and "to" squares is sufficient to completely describe the game. If moves are encoded uniformly, i.e., in the same number of bits, but in as few bits as possible, how many bits would it require to encode a single move for a single player?

(d) In a book review (12/8/09), the NY Times quoted (accurately) Ken Auletta's Googled: The End of the World as We Know It as saying that Google stores "two dozen or so tetabits (about 24 quadrillion bits)." The Times corrected "tetabits" to petabits on 12/21/09.

(i) How many gigabytes does Google store?
(ii) If "tetabits" really should have been terabits, how many gigabytes would there be?

4. Lest we forget: an algorithm question

Suppose you are given a big set of N index cards, each containing the social security number of one person. Process them by this algorithm:

Go through the index cards two at a time and put each pair in its own separate pile, with the smaller number on top.
Go through the resulting piles, two piles at a time, and from each pair create a new pile by repeatedly selecting the smaller visible number from the two original piles and putting it under what you have already selected. This gives you half as many piles, each with twice as many index cards.
Keep repeating this process of making fewer piles; stop when you have only one big pile with all the original index cards.

(i) In two or three words, what does this algorithm do?

(ii) In one pass, how many times is each index card picked up from one pile and put into another, as a function of N?

(iii) How many passes are made through the index cards, again expressed as a function of N?

(iv) How does the total number of steps of the algorithm vary as a function of N?