COS 109: Problem Set 7

Tue Oct 31 15:12:05 EDT 2023

Due midnight Wednesday November 8

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. Potpourri

(a) The New York Times said a few years ago, "Imagine a bookshelf 150 miles [240 km] long: the content of the books on that shelf would be roughly one terabyte of data." Is this estimate much too high, much too low, or sort of reasonable, and why? Assume the books are just text, like a novel.

(b) A story in the Prince on 11/3/14 said that in the 2008-2009 academic year, "Princeton students printed 11,040,632 sheets of paper, enough to stretch from Princeton to Salt Lake City, or a stack 17 times taller than Fine Hall." The number is obviously far too precise, but using this factoid, compute approximately how many miles or kilometers Salt Lake City is from Princeton. (Don't look it up until after you've done the computation!)

(c) Using this data, approximately how tall is Fine Hall, in feet or meters?

(d) A Slashdot story (10/31/21) describes a pilot project for reducing the area of the Great Pacific Garbage Patch by 50% every five years. Wikipedia says that the patch covers 1.6 million square kilometers. Assuming that the project succeeds in its goal, how many five-year periods will it take before the GPGP would fit comfortably inside the Princeton campus (2.4 sq km)?

2. Some Bits and Bytes

There are not quite enough IPv4 addresses for each each of the 8 billion people on earth to have their own personal one.

(a) How many bytes would a hypothetical new IPv[something] need so that each person in the world could have a personal IP address?

(b) Another option might be for each person to have a personal Ethernet address. How many Ethernet addresses could each person have? Just give an expression as a power of 2.

(c) Finally, how many IPv6 addresses could each person have, again as a power of 2?

(d) Here's a seriously geeky watch (though it's hard to imagine that any self-respecting geek would have bought one). What is the largest "time" that it can display?

(e) How many more lights would you need to add so the watch could report 24-hour times like 23:59?

3. Be Fruitful, and Multiply

(a) Von Neumann's 1946 paper says "... the operation of multiplication could be eliminated from the device as an elementary process if one were willing to view it as a properly ordered series of additions." That is, the product of two non-negative integers X and Y can be computed by adding up X copies of Y; for example, 3 times 5 can be computed by adding up 3 5's: 5+5+5.

Here is some Python that multiplies two numbers by using the regular multiplication operator *, but does it by calling a function:

def mul(m, n): # multiples m * n
  return m * n

x = float(input("Enter first number: "))
y = float(input("Enter second number: "))
prod = mul(x, y)
print("Product =", prod)
Modify the function mul to multiply by repeated addition. You have to replace the line
  return m * n
by a loop that computes the product by repeated addition and returns that value. Make sure your code can multiply by zero, but it doesn't have to handle negative numbers. You will need one or more other variables in mul, to index a loop and to hold the value that you're accumulating.

(b) How could you fix your code from part (a) to handle negative numbers as well? You can write the code and test it (best), or you can just give the basic idea briefly (but be very clear).

(c) Multiplication is a commutative operation: X times Y is the same as Y times X (e.g., 5 3's is the same as 3 5's). How could you use that observation to make the multiplication program run as fast as possible in all cases? Again, you can write the code, or just give the basic idea briefly but clearly.


Please use this Google Doc template for your answers. It would be a great help if you could type your answers.

Submit your problem set by uploading a file called pset7.pdf to Gradescope. You can submit as many times as you like; we will only look at the last one.