Due 5:00 PM, Wednesday, Oct 1, in the box outside Room 311, CS building, or in class. 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. |
(a) The comedian Steven Wright says "I have a map of the United States...actual size. It says, 'Scale: 1 mile = 1 mile.' I spent last summer folding it." Suppose for simplicity that the map is 4000 km by 4000 km. How many times would you have to fold it in half to make it into a square about 1 meter on a side? (Ignore the practical reality that you can't fold a piece of paper more than a few times -- this is a gedanken experiment.)
(b) If the original map is made of standard paper, 0.1 mm thick, approximately how thick will the folded map be?
(c) "If a byte is a single character on a keyboard and you typed one character per second, it would take more than 30 million years to create a petabyte-length document." (From a Fermilab press release.) Is 30 million years much too big, much too small, or about right, and why?
(d) On Sept 7, 2010 iafrica.com reported that Alcatel-Lucent will lay a new 2 terabit per second transatlanic fiber cable between Angola and Brazil. If this cable transmits at full capacity and every bit transmitted by this cable is saved, about how many exabytes of disk are needed to store one year's worth of traffic?
(e) If the platter in the disk in a classic iPod is 1 inch in diameter and rotates at 3,600 revolutions per minute, about how fast in inches per second is the surface of the platter traveling past the read head at the outermost edge of the disk? If a desktop disk platter is 3.5 inches in diameter and rotates at 7,200 rpm, how fast is the surface traveling at its outermost edge?
"We still have judgment here; that we but teach(a) In his 1946 paper Preliminary discussion of the logical design of an electronic computing instrument von Neumann discusses an architectural tradeoff: whether to include an instruction for multiplication or to synthesize it by using the addition instruction. What section of the 1946 paper first raises this issue? Summarize the tradeoff in a single sentence.
bloody instructions, which, being taught, return
to plague th' inventor."
(Macbeth, Act I, Scene VII.)
(b) The toy simulator (toysim.html) is a Javascript program running in a web page. The toy machine does not have a multiply instruction. Modify the simulator by adding a multiply instruction, with the operation name mul. (The Javascript multiplication operator is *.) This requires a bit of detective work to find the places in the program where instructions are checked for validity and then executed, then making a change that follows the existing pattern.
Start by making your own copy of toysim.html, which you can do by control-clicking on the link and selecting "Save Link As..." in Firefox and Chrome, or "Save Linked File As..." in Safari. Your answer should specify the additional code you wrote and tell where in the existing program you added it. Do not submit the whole program, but copy and paste your added code along with a couple of lines of the original that are on each side to show where you added it.
Here's an example of a program that uses mul to double input numbers, stopping when it reads a zero.
foo get
ifzero bar
mul 2
print
goto foo
bar stop
You can use this program to verify that your version implements mul
properly.
We want you to write two short programs for the toy computer used in class. It's impossible to be sure that any program, even little ones like these, is correct without running it, so you must test your code and your understanding by using the toy simulator. Be careful about typographical conventions and the like, since the simulator is quite fragile. The code you submit should be cut and paste from a working version.
Real programs are always developed incrementally. You may find it easier to start with something small and simple, like some of the programs in the notes, to be sure you understand how the simulator works and how to get numbers in and print them out again, before you try to solve the assigned problem.
(a) Write a program that gets one number from the keyboard and prints its cube (e.g., if the number is 10, the program prints 1000.) This should be about 6 instructions long, and will use your mul instruction.
(b) Write a program that gets one number from the keyboard, prints that number and successive lower numbers down to 0 inclusive, then stops. For instance, if the initial number is 4, the program prints 4, 3, 2, 1, 0 on successive lines. This can be done in 6 instructions, so if you find yourself writing a lot more, you're on the wrong track. Think about the class example that adds up numbers. You might it helpful to figure out the operations that have to be performed each time through the loop, then worry about how to stop the loop.
This part requires a loop; if your program doesn't have some kind of loop, it's wrong. The loop has to end somehow; if your program doesn't make some test that can terminate the loop, it's wrong. Thus your program is likely to contain code analogous to this, though not necessarily the same:
Top GET IFZERO Done ... GOTO Top Done ...