1. A Small Matter of Programming


(a) This Javascript program is supposed to print a table of Celsius
temperatures from 0 to 100 inclusive in steps of 10, and their
corresponding Fahrenheit temperatures.  It is also supposed to print a
line above the table that labels the two columns.  Not surprisingly, the
program contains errors, although the first document.write statement and
the formula it contains are correct.  Find and fix the errors.  (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 you have identified the errors.)

  there are 5 errors.  here's one corrected version.

	var cels = 0;
	document.write("<br>Celsius   Fahrenheit");
	while (cels <= 100) {
	    document.write("<br> " + cels + "  " + (9 / 5 * cels + 32));
	    cels = cels + 10;
	}

  i don't care about syntax, just the logic and semantics.  you have
  to fix these errors so that

  - loop prints exactly 11 lines 0, 10, 20, ..., 90, 100
  - heading is before the loop
  - text in heading is Celsius  Fahrenheit


(b) The following Javascript-like code is supposed to simulate flipping
a fair coin exactly 100 times.  At the end, it should print the number
of heads and tails.  Sadly, it doesn't quite work.  Fix the errors.
Find and fix the errors.  

  again, there are 5 errors (not a coincidence).  here's a corrected
  version:

	i = 1
	heads = 0
        tails = 0
	while (i <= 100) {
	     r = Math.random() // random number r >= 0, < 1.0 
	     if (r >= 0.5) {
	          heads = heads + 1
	     } else {
	          tails = tails + 1
	     }
	}
	print "heads = ", heads, " tails = ", tails 

  i don't care about syntax, just the logic and semantics.  you have
  to fix these errors:

  - loop must round exactly 100 times
  - summary must be after the loop
  - tails must be initialized
  - tails must be incremented



(c) The original Fortran language of 1958 used "goto" statements, very
much like the goto instruction in our toy assembler language, to
describe the flow of control in a program; statements can have numeric
labels if they are to be the target of a goto statement (and the
specific numeric value has no significance).  For example, "goto 10"
causes control to transfer to the statement labeled "10" in the fourth
line of the following excerpt.  

  something like

	if (x > y)
	  m = y
	else
	  m = x
	print m

  any working variant is fine.  a redundant test is fine, but not
  one that omits the case where x and y are equal.  

  it computs the minimum of x and y



2. File Systems 


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

	25 = 6 for directories plus 2 + 1 + 2 + 6 + 2 + 1 + 3 + 2

(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?

	4 = 1 + 3

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

	5 = 1 + 1 + 1 + 2

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

	1 (reading the directory reveals different file sizes)

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

	2 (there is no D4 in D1/D2)

(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?

	D1/D3/F5 (1023)

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

	D1/F1 (0)

  The idea in all of these is that reading a directory gives all
  the info in the directory, which is the names of directories and
  files, and gives the sizes of the files as well.  Files with
  different sizes are different, directories that don't exist
  don't get read, and one never reads something unnecessarily.  


3. How do you get to Carnegie Hall?  


(a) How many bits and how many bytes for 

33	 7 billion people
29	 310 million Americans
26	 50 million people in England
19	 500,000 people at the Simon and Garfunkel concert in Central Park
17	 $106,000 median household income in Princeton (2009)
16	 47,438 New York City marathoners (2011)
13	 5,200 Princeton undergrads
10	 535 members of Congress
8	 193 countries in the United Nations
7	 90 students in COS 109


(b)
  Anything that is legitimate, and "tight", in the sense that at
  least the specified number of bits are needed.


(c) A COS 126 midterm a few years ago asked this question: "A certain
recent Princeton CS class printed their [4-digit] class year on T-shirts
in binary.  The binary number is all 1's except for two adjacent 0's.
Which class was this (in decimal)?"  I have long believed that COS 109
people can do this stuff just as well as 126 can.  Prove me right.  (i)
What is the class year number in binary?  (ii) In decimal?  (iii) In
hex?

	11111001111
	1999 in decimal
	7CF


(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)?

	2038

	small penalty if you used an approximation based on 2^31 = 2B.