COS 109: Problem Set 6

Wed Oct 25 06:53:23 EDT 2023

Due midnight Wednesday November 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.

1. Limits to Growth

(a) A post by Paul Graham, co-founder of Y-Combinator, at 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 approximately right or not, and why? This is a good place to refresh your memory of the Rule of 72 rather than reaching for your trusty calculator.

(b) Suppose a Petri dish can hold 10,000,000 bacteria. If the dish starts off with 10 bacteria and the population grows at 4% per hour, approximately how many hours will it take to fill up the dish?

(c) How many hours will it take if the dish can hold about 20,000,000 bacteria?

(d) An article some years ago says that servers in data centers worldwide use about 30 gigawatts of power, and that Google uses about 1 percent of that. If a typical server uses 60 watts, roughly how many servers does Google have?

2. Big and Small Numbers

The 2023 Nobel prize in Physics went to Pierre Agostini, Ferenc Krausz and Anne L’Huillier "for experimental methods that generate attosecond pulses of light for the study of electron dynamics in matter." One news story said, "An attosecond is one quintillionth of a second. The number of attoseconds in a single second is the same as the number of all the seconds that have elapsed since the universe burst into existence 13.8 billion years ago."

(a) Compute the number of seconds since the beginning of the universe.

(b) How close is it to the number of attoseconds in a second?

(c) The story went on to say "Electrons move at a whopping 43 miles a second." Very roughly how many attoseconds would it take for an electron to move from Friend 008 to Forbes College?

(d) A few years ago, the web page for CS 152 at Harvard said "Almost every computation in the world (at a rough guess, 15,000,000,000,000,000,000 instructions every second) was written in some programming language." If the computers doing these computations are all typical laptops like yours, very roughly how many computers would that be?

3. Remember File Systems?

Suppose that part of the file system on a computer looks like this, where names beginning with D are directories (indicated by circles), and names beginning with F are files (indicated by squares):

That is, directory D1 contains directories D2, D3 and D4 and files F1 and F2; directory D1/D2 contains directory D3 and files F3 and F4; directory D1/D2/D3 contains file F4; and so on.

Assume that no other files are involved, the files have the given sizes in bytes, directories occupy one disk block each, and all disk blocks are 1024 bytes long. Each question assumes that reading a file or directory into RAM begins by reading the block that contains directory D1 and works down the hierarchy until the desired information is found, reading only blocks that must be read. No directory is read more than once in this process. Be careful to distinguish between files and directories -- a directory contains the names of files and other information about them, but not their contents.

(a) How many disk blocks in total are used by these directories and files?

(b) How many blocks must be read from disk to compute the total number of blocks in the files?

(c) How many blocks would the file system have to read from disk (including reading D1) to read all the blocks of file D1/F2 into RAM?

(d) How many blocks must be read from disk to read all the blocks of file D1/D2/D3/F4 into RAM?

(e) How many blocks must be read from disk to decide whether D1/F1 and D1/F2 have exactly the same contents?

(f) How many blocks must be read from disk to determine whether or not a file named D1/D2/D4/D6/F4 exists?

(g) How many files must be read to see whether there is a Powerpoint presentation among them?


Please use this Google Doc 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 pset6.pdf to Gradescope. You can submit as many times as you like; we will only look at the last one.