COS 109: Problem Set 5

Wed Oct 18 10:15:54 EDT 2023

Due midnight Wednesday October 25

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

For these problems, you will want to be sure that your proposed fixes actually work, by running your code in Python before submitting.

You can experiment with Python in several ways. It's probably easiest to use Google's Colab, which lets you write and run Python code on a web page. You will be doing the same thing for Lab 5, so this is an easy way to get started. The instructions for Lab 5 will also give you more information. There are also a dozen small examples here.

(a) Write a Python program to print the even numbers in the range from 1 to 100 inclusive.

# you fill in the code here

(b) Write a program to count backwards from any input number n down to 0 in steps of 7, like 100, 93, 86, 79, ....

n = input()
# you fill in the rest of the code here
You wrote this code in Toy assembler for the third problem set. Think about how the Python version differs.

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

	if (x > y) goto 10
	m = x
	goto 20
10	m = y
20	print m
What computation this Fortran program perform on the values provided for x and y?

(d) Code that uses goto's is usually convoluted and hard to understand, so goto is rarely used other than in assembly languages; some languages, including Python, don't provide a goto statement at all.

Rewrite the Fortran code sequence of part (c) with a single if-else statement in Python. Test your code from a file or with Colab before submitting.

2. Time to Get Moving

(a) 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 the leftmost (high-order) bit of that integer is used to indicate the sign of the number (negative numbers indicate times before 1970). Given this representation, in what future year will Unix time reach its largest possible value?

(b) If the integer were unsigned (that is, no bit was reserved for a sign), in what year would Unix times exceed the largest possible vale?

(c) On 12/3/14, YouTube described an overflow problem in their programming: "We never thought that a video would be watched in numbers greater than a 32-bit integer (2,147,483,647 views)." If the value 2,147,483,647 is stored as a 32-bit integer, what is its leftmost bit: 0 or 1?

(d) What is 2,147,483,647 in hexadecimal?

(e) When this number is incremented by 1, what is the resulting value in hexadecimal?

3. Do I Know You from Somewhere?

(a) Before Covid ended normal social life, 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.

(b) Approximately what fraction of a football field would all these people 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.

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

(d) And the natural extension: if 10 billion people (somewhat more than the population of the earth) showed up, what would be the dimensions?

(e) And speaking of over-crowded, half a million people showed up for the famous Simon and Garfunkel concert in Central Park in 1981. (Ask your parents if they know about it.) If each person were given a unique identification number, how many bits would it require?

(d) How many bytes would the identification number require?


Please use this Google Doc 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 Gradescope. You can submit as many times as you like; we will only look at the last one.