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