COS 109: Problem Set 4

Tue Sep 22 14:17:51 EDT 2020

Due midnight, Thursday October 1

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.

Problem set answers need not be long, merely clear enough that we can understand what you have done, though for computational problems, show enough of your work that we can see where your answer came from. Please type your answers if at all possible, especially if your penmanship, like mine, is peccable. Thanks.

Don't forget that if the data you start with is approximate, the results cannot be precise.

1. In the Right General Area

(a) A recent story on the LSST camera says that its focal plane contains 3.2 billion pixels, each about 10 microns wide. If the pixels are square and the array of pixels is square, what is the approximate area of the focal plane in square meters?

(b) If the camera uses the standard RGB representation of colors, about how many MB of memory is required to hold one image from the camera?

(c) A recent technology story says that the state of the art in the manufacture of integrated circuits is about 100 transistors per square micron. If this is true, about how many transistors would there be in a 1 cm by 1 cm circuit?

(d) An article from several years ago reported on IBM's plans to build a new factory to make integrated circuits (at a cost of $2.5B). This factory was going to produce wafers that are 15 inches in diameter. Supposing that there are 400 chips of a particular type on an 10-inch wafer, and assuming that everything else is unchanged, approximately how many chips of that type will there be on a 15-inch wafer?

(e) A package of falafel mix says "makes 12 2-inch patties." How many 1-inch patties would it make?

(f) How many 4-inch patties would it make?

2. Algorithm Analysis

(a) Sports teams often perform a post-game ritual in which each member of one team shakes hands with each member of the other team. For a baseball team with 9 players, what is the total number of handshakes? (If you and I shake hands, that's one shake, not two.)

(b) At social gatherings (a kind of event that is no longer common), each attendee might shake hands with each other attendee (a custom that is no longer common either). If there are n attendees, how does the total number of handshakes grow in proportion to n?

(c) Suppose we had a phone book that included the name of every person on earth. How many name comparisons would be necessary to look up a particular name?

(d) If it takes one eon to play the Towers of Hanoi with 20 disks, about how many eons will it take to play with 30 disks? An expression is fine; there's no need to do arithmetic.

3. The Rule of 72

The "Rule of 72" is a very useful rule of thumb for estimating the effects of compounding, where some quantity grows by a fixed percentage in each of a series of identical time periods. The rule of 72 says that if a quantity is compounding at x percent per time period, it will double in approximately 72/x periods.

For example, if gas prices are rising 8% per year, in 72/8 or 9 years a gallon of gas will cost twice as much as it does today. But if prices are only rising 6% per year, doubling will take 72/6 or 12 years. Conversely, if the doubling time is given, you can compute the number of periods by dividing 72 by the rate: if something doubles in 10 years, the rate is 72/10, or about 7% per year. The approximation breaks down if the rate is too high, but it's good enough for typical values. (The web site given above has a good explanation of how it works, and a simple Javascript implementation that you might enjoy looking at. But don't use it to do the calculations below, and don't use your calculator; this problem is about learning to do your own arithmetic in your head or at least with pencil and paper.)

(a) In a Turing Award talk in June 2018, Dave Patterson said that processor speeds no longer double every two years; instead their speeds are increasing only 3% per year. If this is true, in what year will processors be twice as fast as they are this year?

(b) Suppose that 25 years from now, you're trying to send your kids to Princeton and you discover that the tuition has quadrupled from what it is now. Approximately what annual rate of tuition increase would that correspond to?

(c) Princeton's rate of return on its endowment investments was 6.2% in the 2019 fiscal year. Past performance certainly does not guarantee future results, but if this rate were to continue, roughly what would the value of Princeton's current approximately $25B endowment be 25 years from now?

(d) A NY Times story a while back says that total power consumption by Internet servers is doubling about every 6 years. Suppose that Internet servers used 5 gigawatts in 2013 and 10 gigawatts in 2019. How fast is power consumption growing per month?

(e) Suppose (improbably) that this power consumption continues to double at the same rate. In what year will servers consume 10 terawatts?

Submission

Please use this Word template for your answers. It would be a great help if you could type your answers.

Submit your problem set in PDF format by uploading a file called pset4.pdf to https://tigerfile.cs.princeton.edu/COS109_F2020/Pset4. You can submit as many times as you like; we will only look at the last one.