15-105 SPRING 2009 [CORTINA]

HOMEWORK 1 - due Friday, January 23 in class

WRITTEN PROBLEMS

Hand these problems in on paper in class.

  1. (1 pt) The soroban is the Japanese version of an abacus.

    1. A soroban with 8 rods has how many beads in total?

    2. Draw a soroban with 8 rods that stores the value 0.

    3. Assume the soroban stores only integer values. That is, the rightmost rod represents the one's digit. Draw a soroban with 8 rods that stores the value 2639.

    4. What is the minimum number of beads that need to be moved to add 9 to the value stored on a soroban? Explain.

  2. (1 pt) Babbage's Difference Engine utilized the method of finite differences to compute the values of a polynomial function. Babbage computes the values of the function and all of its difference functions for x=0, and these values are given below. What does the machine compute for f(1), f(2), f(3) and f(4) when the machine is cranked?

    f(0) = 5
    Δf(0) = 2
    Δ2f(0) = 3
    Δ3f(0) = 1

  3. (1 pt) Answer the following questions about famous computational machines of the past.

    1. Herman Hollerith's tabulating machine was designed to solve what computational problem? Why was a solution to this problem desperately needed?

    2. UNIVAC gained its fame due to what event in 1952? Write two or three sentences describing how it was used in this case.

  4. (1 pt) War has had a signficant impact in the development of modern electronic computers. Explain why each of the following computers or devices were developed during the indicated war.

    1. ENIAC and World War II

    2. Integrated circuits and the Cold War

  5. (1 pt) Answer the following questions about modern computer companies. (You may need to look some of these up on the web.)

    1. What was Microsoft's first software product?

    2. The Apple Macintosh was launched in what Orwellian year?

    3. The first modern personal computer with a graphical user interface, a mouse and a laser printer was developed at what company?

    4. Google was founded by two graduate students from what university?

  6. (2 pts) Write a clear and precise algorithm for washing a load of white clothes. Based on your algorithm, what are the inputs? what are the outputs? what are the "primitive operations" (instructions that are assumed to be basic enough to be understood)?

  7. (3 pts) Modern computers follow the Von Neumann model, named after John von Neumann, an advisor to the ENIAC project. In this model, there is a central processing unit and a memory unit that stores instructions of a computer program. An instruction is fetched from memory, decoded, and then executed. This process is repeated on the next instruction in memory, unless the previous instruction tells us to jump to another location in memory.

    Assume that such a computer has three internal storage registers named R1, R2 and R3 and the following machine instructions: 

    ADD registerA, registerB - Adds the value in registerA to the value in the registerB, storing the result in registerB (overwriting its original value).
BNZ register, address - Jump to the instruction at the given address if the contents of the specified register is not zero
CLEAR register - Clears the specified storage register (sets it to 0)
HALT - Stop the computer
LOAD value, register - Loads the specified storage register with the given value (overwriting its original contents)
SUB value, register - Subtracts the given value from the contents of the specified register

    What computation is performed by each of the following machine programs assuming the computer starts with the instruction at address 100? Show your work. 

    ADDRESS   INSTRUCTION
100       CLEAR R1
101       LOAD 6, R2
102       ADD R2, R1
103       SUB 1, R2
104       BNZ R2, 102
105       HALT 

ADDRESS   INSTRUCTION
100       LOAD 1, R1
101       LOAD 6, R2
102       ADD R1, R1
103       SUB 1, R2
104       BNZ R2, 102
105       HALT

ADDRESS   INSTRUCTION
100       CLEAR R1
101       LOAD 3, R2
102       LOAD 6, R3
103       ADD R2, R1
104       SUB 1, R3
105       BNZ R3, 103
106       HALT