Due 5:00 PM, Wednesday, Oct 2, 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. |
In The Social Atom (2007), author Mark Buchanan says "Take a piece of whisper-thin paper, say 0.1 mm thick. Now suppose you fold it in half twenty-five times in a row, doubling its thickness each time. How thick will it be? Almost everyone asked such a question will grossly underestimate the result." Right now, make your own estimate, which you should be able to do in your head on the basis of what we've done in class. When you do the rest of this exercise you can assess whether you are better than "almost everyone".
(a) If Buchanan is correct about the thickness of a piece of paper, about how thick will the folded paper be?
(b) Is Buchanan's estimate of 0.1 mm much too high, much too low, or about right, and why? (You can probably make your own estimate by observation near printers.)
(c) A recent article in IEEE Spectrum says "The roughly 2000 sequencing instruments in labs and hospitals around the world can collectively generate about 15 petabytes of compressed genetic data each year. To put this into perspective, if you were to write this data onto standard DVDs, the resulting stack would be more than 2 miles tall." Is this estimate much too high, much too low, or about right, and why do you say so?
(d) The standard RGB representation of colors uses 8 bits for the red component, 8 bits for green, and 8 bits for blue (24 bits in all), and thus 6 hexadecimal digits can express any given color. Suppose instead that a representation uses 9 bits for red, 8 bits for green and 7 bits for blue. Assuming that the bits are stored left to right in RGB order, what are the hexadecimal representations of red, green, blue, yellow, cyan and magenta?
"We still have judgment here; that we but teachSection 3.5 of von Neumann's 1946 paper Preliminary discussion of the logical design of an electronic computing instrument says "... we must, in most cases, give two parallel trains of orders preceded by an instruction as to which routine is to be followed. This choice can be made to depend upon the sign of a number (zero being reckoned as plus for machine purposes). Consequently, we introduce an order (the conditional transfer order) which will, depending on the sign of a given number, cause the proper one of two routines to be executed."
bloody instructions, which, being taught, return
to plague th' inventor."
(Macbeth, Act I, Scene VII.)
(a) The toy machine was described in class (and its instruction repertoire is repeated below). Which toy machine instruction provides this "conditional transfer order"?
(b) The toy simulator (toysim.html) is a Javascript program that runs in a web page. Find the two lines in the simulator program that implement this conditional transfer instruction and copy them into your submission.
(c) Modify the simulator by adding an IFNEG instruction that tests whether the accumulator holds a negative value. Here's an example program that uses IFNEG; it just prints input numbers until it sees a negative input value:
foo get
ifneg bar
print
goto foo
bar stop
This is an exercise in playing detective. Find the places in the
simulator program where the new instruction would be handled, then make
a change that follows the existing pattern. (This is pretty close to
how a lot of real programming tasks are handled, though on a very small
scale.) Start with View Source and save that file on your own computer
as a plain ASCII text file with extension .html. 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.
We want you to write two short programs for the toy computer used in class; the instruction-set description is repeated here:
get get a number from keyboard into accumulator
print print contents of accumulator
load Val load accumulator with Val (Val unchanged)
store Lab store accumulator contents into memory location labeled Lab (accumulator unchanged)
add Val add Val to contents of accumulator (Val unchanged)
sub Val subtract Val from contents of accumulator (Val unchanged)
goto Lab go to instruction labeled Lab
ifpos Lab go to instruction labeled Lab if accumulator is greater than or equal to zero
ifzero Lab go to instruction labeled Lab if accumulator is zero
stop stop running
Lab Num initialize this memory location to numeric value Num (once, before program runs)
If Val is a name like Sum, it refers to a labeled memory location. If Val is a number like 17, that value is used directly. So add Sum means to add the contents of the memory location named Sum to the accumulator value (leaving Sum's contents unchanged), while add 1 means to add 1 to the accumulator value.
It's impossible to be sure that any program, even little ones like these, is correct without running it. 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 reads one number from the keyboard and prints twice its value (e.g., if the number is 10, the program prints 20). This should be about 6 lines long. Hint: Think about the class example that adds two numbers. Copy and paste the code from the Toy simulator screen where you ran it.
(b) Modify the program of (a) so it gets one number, prints twice its value, then loops to get another number. It stops (without printing anything more) when the input number is negative. This can be done in 8 lines if you use your IFNEG instruction from part 2, and 9 lines if not, so if you're writing a lot more code, you're on the wrong track. You might find 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. Copy and paste the code from the Toy simulator screen where you ran it.
Part (b) 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 similar to this, though not necessarily the same:
Top GET IFZERO Done ... GOTO Top Done ...