COS 109: Problem Set 7

Due 5:00 PM, Tuesday, December 5, by submission to drop box at https://dropbox.cs.princeton.edu/COS109_F2017/Problem_Set_7
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. File Systems

Suppose that part of the file system on a computer looks like this, where names beginning with D are directories (folders), and names beginning with F are files:
     D1
         D2
             D3
                 F4   2007 bytes
             F3        100 bytes
             F4       2007 bytes
         D3
             F5       5121 bytes
         D4
             D6
             F4       2007 bytes
             F6         11 bytes
         F1           3072 bytes
         F2           2008 bytes
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, 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 would the file system have to read from disk (including reading D1) to read all the blocks of file D1\F1 into RAM?

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

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

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

(f) Most files waste some space at the end because their size isn't an integral number of blocks. Which file wastes the most, and how much?

(g) Which file wastes the least, and how much?

 

2. Limits to Growth

(a) From TIAA/CREF Participant, 8/03: "In his will, Franklin left 1000 pounds sterling to the cities of Philadelphia and Boston, with the stipulation that the funds be lent out at 5 percent interest a year. Because of compounding, Franklin figured that in 100 years his bequests to these cites would be worth 131,000 pounds." Assuming that 5% was achieved, was his estimate much too high, much too low, or about right, and why do you say so? (The Franklin Institute in Philadelphia owes its existence to his bequest.)

(b) Suppose a Petri dish can hold 1,000,000 bacteria. If the dish starts off with 1 bacterium and the population grows at 3% per minute, approximately how long will it take to fill up the dish?

(c) How long will it take if the dish can hold about 2,000,000 bacteria?

(d) Unix systems maintain time as the number of seconds since 00:00 on January 1, 1970; among other things, this is used to keep track of when files were last changed. The time is stored in a 4-byte integer, but one bit of that integer is used to indicate the sign of the number (negative numbers indicate times before 1970). Given this representation, in what year will time overflow (i.e., wrap around)?

3. Further review

(a)(Algorithmic running times) I am running an algorithm on an input of size 10 and it is requiring 100 operations. Next, I would like to run the algorithm on an input size of 20. How many operations will this require if the algorithm's running time is

  1. logarithmic
  2. linear
  3. quadratic
  4. exponential

(b) (sizes of representations) For these practice questions, work out the answer by using familiar powers of two and powers of ten and not by reaching for your calculator. How many bits and how many bytes to represent

  1. 7.28 billion people in the world and 322 million Americans
  2. 53 million people in England
  3. 251,107,000 people who were eligible to vote in the 2016 election
  4. $149,948 median family income in Princeton (2010)
  5. 50,650 New York City marathon finishers (2017)
  6. 5,391 Princeton undergrads
  7. 535 members of Congress
  8. 193 countries in the United Nations

4. An estimation problem

(a) List the devices that you own that can conenct to the internet

(b) Imagine that every Princeton student has the same number of devices as you do. How many IP addresses would this require?

(c) Based on previous assignments, estimate how many IP addresses are needed to allow all devices owned by undergraduate students in America to conenct to the internet.

(d) Imagine that every person in the US has as many devices as you do, how many IP addresses are needed to allow all such devices to conenct to the internet?