COS 109: Problem Set 6

Mon Nov 10 18:04:25 EST 2014

Due 5:00 PM, Wednesday, Nov 12, 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. Trust but Verify

(a) An NSA press release says

According to figures published by a major tech provider, the Internet carries 1,826 Petabytes of information per day. In its foreign intelligence mission, NSA touches about 1.6% of that. However, of the 1.6% of the data, only 0.025% is actually selected for review. The net effect is that NSA analysts look at 0.00004% of the world's traffic in conducting their mission -- that's less than one part in a million. Put another way, if a standard basketball court represented the global communications environment, NSA's total collection would be represented by an area smaller than a dime on that basketball court.
    (i) Approximately how many PB/day does the NSA "touch"?
    (ii) Approximately how many PB/day does the NSA "look at"?
    (iii) An NBA basketball court is 94 feet by 50 ft (28.65m by 15.24m). Approximately what fraction of the area of a basketball court does a dime cover? How many parts per million is this?
    (iv) If a basketball court were tiled with dimes placed edge to edge in a rectangular array like this, what fraction of the surface of the court would be covered?


    (v) In April 2014, Sony announced a magnetic tape material that can store data at 148 gigabits per square inch. About how many gigabytes could be stored on the surface of a basketball court using this material?

 

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 <= 4) {
         print i
         i = i + 1
     }
     print i

(b)  i = 1
     while (i <= 4) {
         i = i + 1
         print i
     }
     print i

(c)  i = 1
     while (i < 4) {
         i = i + 2
         print i
     }

(d)  i = 4
     while (i > 0) {
         print i
         i = i - 1
     }

(e)  i = 4
     while (i >= 0) {
         i = i - 4
         print i
     }
     print i

(f)  i = 1
     while (i <= 10) {
         if (i is odd)
             print i
         i = i + 3
     }

(g)  i = 1
     while (i <= 10) {
         if (i is odd)
             print i
         else
             print i + 1
         i = i + 3
     }

 

 

3. Limits to Growth

(a) A post by Paul Graham, founder of Y-Combinator, at paulgraham.com says "If you have 100 users, you need to get 10 more next week to grow 10% a week. And while 110 may not seem much better than 100, if you keep growing at 10% a week you'll be surprised how big the numbers get. After a year you'll have 14,000 users, and after 2 years you'll have 2 million." Are his numbers right or not, and why? (This is a good place to refresh your memory of the Rule of 72 rather than reaching for your calculator.)

Ignore this question. (b) In his 1956 story The Last Question, Isaac Asimov says "Population doubles every ten years. Once this Galaxy is filled, we'll have another filled in ten years. Another ten years and we'll have filled two more. Another decade, four more. In a hundred years, we'll have filled a thousand Galaxies. In a thousand years, a million Galaxies. In ten thousand years, the entire known Universe. Then what?" How many galaxies are there in the entire known Universe?

 

4. Size Matters

There's only modest credit for these off-the-wall estimation questions, so don't waste much time on them, but thinking about them is good practice.

(a) The world's largest wooden church is in Finland; according to urban legend (but not in fact) it's big because the architect specified its dimensions in centimeters but the builders interpreted them as inches. By approximately what factor is the church's area larger than planned for? By what approximate factor is its volume larger?

(b) While spending a fun afternoon raking leaves a few weeks ago, I took to wondering how many leaves there were on my lawn; it felt like billions but was probably mere millions. Estimate very very roughly the number of leaves on a single big tree that is maybe 75 feet tall, sort of like the big oaks and maples along Prospect. Hint: Think about surface area: leaves need sunlight to do their thing. Second hint: It doesn't much matter what the shape of the tree is. Third hint: There's no right answer; this is about making plausible estimates in the complete absence of actual knowledge.

(c) Estimate how much the cannon barrel in front of Cannon Club weighs. Don't look it up, and don't ask friends, but provide your best estimate.