COS 109: Problem Set 4

Mon Sep 25 20:19:29 EDT 2023

Due midnight, Wednesday Oct 4

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. Thanks.

And a reminder from earlier problem sets: don't forget that if the data you start with is approximate, the results cannot be precise.

1. Numbers in the News

In United States of America v. Donald J. Trump, Mr Trump's lawyers requested a trial date of April 2026, saying that they had received 8.5 terabytes of electronic discovery materials from the Department of Justice, totaling over 11.5 million pages of text plus other digital materials. (The original filing is here for anyone sufficiently interested.) The request was rejected, and the trial will be in March 2024.

The filing says that this information would be a stack of 11.5 million pages, a "tower of paper stretching nearly 5,000 feet into the sky. That is taller than the Washington Monument, stacked on top of itself eight times, with nearly a million pages to spare." (To save you the trip to Google or the filing itself, the Washington monument is 555 feet or 169 meters high.)

(a) The filing says that paper thickness is 200 pages/inch. Is the estimate of the height of the stack too high, too low, or about right, and why do you say so?

(b) "To put 11.5 million pages in some perspective, we began downloading the government's initial production on August 13, 2023. Two days later, it was still downloading." Suppose that the download finished in 4 days. What is the approximate download speed in MB/sec?

(c) If the 11.5 million pages are just ASCII text, about how many gigabytes of text is involved in the discovery?

2. In the Right General Area

(a) A new Apple iPhone 15 has a 6.1 inch screen (measured diagonally). An iPhone 11 from a few years earlier has the same screen size, but the iPhone 15 has twice as many pixels on its screen that the older one does. The resolution of the new phone is 460 pixels per inch. What is the resolution on the older phone, in pixels per inch?

(b) An article from several years ago reported that IBM planned 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 200 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?

(c) As part of a home renovation project, we are replacing the tiles in a shower. The old tiles are 4 inches by 4 inches. The new tiles are 2 inches by 2 inches. If there are 200 old tiles, how many new tiles are needed?

(d) If it took one pound of grout to seal the joints between the old tiles, how many pounds of grout will it take for the new tiles?

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 rate by dividing 72 by the number of periods: 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 with pencil and paper. Keep in mind that the rule is an approximation; you can't use it to produce more than about 1 significant figure in a numerical answer. And since the data is approximate, using your calculator to compute an answer to more figures is equally wrong.

(a) In a Turing Award talk in June 2018, computer architect Dave Patterson said that processor speeds are increasing at 3% per year. If this is true, in what year will processors be twice as fast as they are this year?

(b) Suppose that about 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 has averaged 12% per year for the past decade, though it varies wildly. Past performance certainly does not guarantee future results, but if Princeton were to sustain 12% each year, roughly what would the value of Princeton's current approximately $36B endowment be 25 years from now? (Of course this is all unrealistic, but the power of compounding is very important.)

4. 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) If there are n players on each team, 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 in India (population about 1.4 billion). How many name comparisons would be necessary to look up a particular name if we used binary search?


Please use this this Google Doc as a template for your answers. It would be a great help if you type your answers so we can read them, but if you prefer to write by hand, that's OK as long as you are very neat. (That is, not like me!)

Either way, convert your answers to PDF and submit them by uploading a file called pset4.pdf to the "Pset4" assignment in Gradescope. When submitting on Gradescope, you will be asked to label each question with the page of the PDF your answer appears on (feel free to reach out if this causes any issues). You can submit as many times as you like; we'll only look at the last one.