Due 5:00 PM, Wednesday Dec 2 (after Thanksgiving break). 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.
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 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.
(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 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?
(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?
(a) i = 1
while (i <= 3) {
print i
i = i + 1
}
print i
(b) i = 1
while (i <= 3) {
i = i + 1
print i
}
print i
(c) i = 1
while (i < 3) {
i = i + 2
print i
}
(d) i = 3
while (i > 0) {
print i
i = i - 1
}
(e) i = 3
while (i >= 0) {
i = i - 3
print i
}
(f) i = 1
while (i <= 10) {
if (i is odd)
print i
i = i + 3
}
(g) Now that you understand loops, try this one. This program is supposed to display the powers of 2 from 20 to 210 inclusive, using the function pow(n, m), which computes nm. Sadly, the program doesn't work. Fix the errors, which you can do without adding or deleting any lines. (This questions is about logic and numeric values, not syntax; assume the syntax is correct.)
n = 1
while (n < 1024) {
print pow(n, 2)
n = n + 2
}
(h) The following function prints a value computed from its three argument values x, y and z.
function weird(x, y, z) {
w = x
if (y > w)
w = y
if (z > w)
w = z
print w
}
Very briefly, what does function weird do in general, that is,
what operation or computation does it perform? Don't just repeat the
statements of the program in English.
(a) In vacuum, the speed of light and thus electro-magnetic radiation like radio, TV, wireless, etc., is 3 x 10^8 meters per second. What is the approximate number of feet that light travels in a nanosecond?
(b) Signals propagate significantly more slowly in electronic circuits (about 1/3 of the speed 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.
Without using the web, answer the following questions:traceroute to www.u-tokyo.ac.jp, 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
- 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 (probably) inside the University of Tokyo, and how do you know?
(a) A friend told me of an amazingly large wooden church in Finland; apparently it's big because the architect specified its dimensions in feet and the builders interpreted them as meters. (This is presumably an urban legend.) By approximately what factor is the church's area larger than planned for? By what approximate factor is its volume larger?
(b) Estimate how much the cannon barrel in front of Notestein Hall (née Cannon Club) weighs. Don't look it up, and don't ask friends, but provide your best estimate.
(c) While spending a fun afternoon raking leaves a couple of weeks ago, I took to wondering how many leaves there were on my lawn; it felt like billions but was probably mere millions. Estimate the number of leaves on a single big tree that is 75 feet tall, with the first branches starting 25 feet off the ground, sort of like the big oaks and maples along Prospect. Hint: the surface area of a sphere is 4πr2, and leaves need sunlight to do their thing.