COS 109: Problem Set 5

Minor wording changes on Fri Oct 16 18:48:54 EDT 2020

Due midnight Thursday October 22

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. A Small Matter of Programming

(a) The following Python code is supposed to count down from the initial value of n to 1, printing the values, then print "Boom!" at the end. That is, if the first line is n = 3, the program should print "3, 2, 1, Boom!". Unfortunately, it doesn't work. Find and fix the errors. You might actually find it easier to just figure out how to solve the problem from the specification and then see where things were wrong. (This is a question about logic, not about syntax, but if you put the code into a file and run it, you can be sure that it works.)

   i = 0
   while i > n:
      i = i - 1
      print(n)
      print("Boom!")

(b) This program is supposed to display the powers of 2 from 2^0 to 2^10 inclusive, using the function math.pow(n, m), which computes n^m. Sadly, the program doesn't work. Fix the errors, which you can do without adding or deleting any lines. (This question is about logic and numeric values, not syntax; assume the syntax is correct.)

n = 1
while n < 1024:
   print(math.pow(n, 2))
   n = n + 2
If you want to run it, you will have to import math.

 

2. 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 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?

 

3. Unknowable Numbers

(a) It is sometimes said that the amount of electrical power needed to perform a computing task falls by half every one and a half years, in the sense that newer equipment will use less power to accomplish the same task. If a supercomputer uses 10 megawatts for a particular computation today, how many years from now would improved hardware require 10 milliwatts for the same task? (This is utterly improbable, of course.)

(b) Before normal social life ended, I was at an over-crowded cocktail party, and it started me wondering... Suppose that 10,000 people come to the same party. If they arrange themselves in a filled-in square (to make the arithmetic easier), what would be the approximate dimensions of the square? State clearly how much space you estimate that each person will occupy. Express dimensions using either feet or meters.

(c) Approximately what fraction of the football field at the stadium would they occupy? (Note for non-football types: the field is 100 yards long and 50 yards wide; feel free to go metric -- 100 x 50 meters -- if you prefer.)

(d) Suppose 100 million people showed up at our hypothetical party. What would be the size of the square for this gathering?

(e) And now for something completely different. During the summer, the university installed brand new Astroturf on the Sherrerd lacrosse field, a multi-week project that must have cost a boatload (at the same time as they were crying poor on other fronts). Without looking up anything, estimate much this might have cost. Although there is surely a right answer, I don't know it either, so this is an experiment for all of us.

 

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 pset5.pdf to https://tigerfile.cs.princeton.edu/COS109_F2020/Pset5. You can submit as many times as you like; we will only look at the last one.