Graded out of 33 1. Limits to Growth (a) From TIAA/CREF Participant, 8/03: "In his will, Franklin left 1000 pounds sterling to the cities of Philadelphia and Boston, with the stipulation that the funds be lent out at 5 percent interest a year. Because of compounding, Franklin figured that in 100 years his bequests to these cites would be worth 131,000 pounds." Franklin died in 1790. Assuming that 5% was achieved, was his estimate much too high, much too low, or about right, and why do you say so? (The Franklin Institute in Philadelphia owes its existence to his bequest.) about right: 5% doubles in 14 years; 100/14 is about 7, 2^7 * 1000 is 128000 -- all very consistent some people seem to have just used their calculators for this. that's ok, though you are kind of missing the point of the course, which is to be able to do this kind of thing without a calculator. (b) Suppose a Petri dish can hold 1,000,000 bacteria. If the dish starts off with 1 bacterium and the population grows at 3% per minute, approximately how long will it take to fill up the dish? 72 / 3 = 24 minutes to double 20 doublings to get to 1 million, so 20 * 24 = 480 minutes (c) How long will it take if the dish can hold about 2,000,000 bacteria? one more doubling = 504 minutes to get to 2M 2. Round and Round it Goes Here's some straightforward boring practice in figuring out what sequences of instructions do. For each of the following excerpts, state what sequence of values, if any, is printed. (a) i = 1 while (i <= 3) { print i i = i + 1 } print i 1 2 3 4 (b) i = 1 while (i <= 3) { i = i + 1 print i } print i 2 3 4 4 (c) i = 1 while (i < 3) { i = i + 2 print i } 3 (d) i = 3 while (i > 0) { print i i = i - 1 } 3 2 1 (e) i = 3 while (i >= 0) { i = i - 3 print i } 0 -3 (f) i = 1 while (i <= 10) { if (i is odd) print i i = i + 3 } 1 7 (g) i = 1 while (i <= 10) { if (i is odd) print i else print i + 1 i = i + 3 } } 1 5 7 11 3. A Bit More Bits and Bytes (a) BCD or "binary coded decimal" encoding is an old representation of numbers that stores two decimal digits of four bits each in a single 8-bit byte. This clearly wastes some space, in the sense that it only stores 10 different values in 4 bits, where it could have stored 16, but at the time it was convenient for hardware reasons. What is the largest decimal number that can be stored in two bytes using BCD? What is the largest decimal number that can be stored in two bytes if ASCII digits are used? What is the largest number that can be stored in two bytes using binary? 9999 in BCD 99 in ASCII 65535 (2^16-1) in binary (b) A typical ATM PIN has four decimal digits. What's the least number of bits that are necessary to transmit the PIN from the ATM to the bank for validation? How many bits are necessary if BCD is used? 14 bits in binary, 16 bits in BCD (c) How many bits would IP addresses need to have so that each person on earth could have his or her own unique IP address? 33 (d) By what factor does the number of possible Ethernet addresses exceed the possible number of IPv4 addresses? 2^48 / 2^32 = 2^16 or any equivalent 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 green 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. AC and FG i think this is unique. (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. AF or CF or AG or CG (i think) full points for any one (c) What routers are 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. A D C G F some places are both 1 and 2 hops away so they should be reported. (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. S A C P (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? S E F B A C G D P all or nothing on this one. (f) Suppose you want to build a fully-connected network, in which every router is connected directly to every other router. How does the number of links grow in proportion to R, the number of routers? quadratic, or R^2, or a more complicated quadratic formula like R(R-1)/2. limited partial credit for giving the series 1 3 6 10 ... (g) Suppose instead 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? R-1 a long chain, or a central one that all others connect to.