$Id: review2.txt,v 1.1 2005/09/13 16:05:12 locasto Exp $
Fall 2005 COMS1003
----------------------------------------------------------------------

0. What is Babbage's contribution to computer science? What inspired
    him? 

   Babbage designed the first complete calculating machine (the
    Analytical Engine). One of his inspirations was the fact that
    tables of logarithms were produced by hand; this seemed like a
    mechanical task to him, rather than a tediuous and error-prone
    human process.

1. What is the von Neumann architecture? How is it similar to 
    Babbage's Analytical Engine? Detail the von Neumann architecture.

   The von Neumann architecture is the dominant organization of
    computer hardware for modern PC's. The von Neumann architecture 
    is called the "stored-program" computer because the hardware
    can be reused for different tasks by storing a new program and
    data in the memory unit. The architecture is:
     A CPU with an ALU and a CU.
     A memory capable of storing a program and the data it operates on.
     A series of other input and output devices connected to the CPU.

     This architecture is essentially what Babbage proposed in the
     Analytical Engine (the mill, the store, the input, the output).

2. What is the precise definition of an algorithm? Why do we need
    one? How did Alan Turing contribute?

   An algorithm is a procedure for computing the solution to a problem in
    a finite number of steps. Algorithms can be described (and executed by) 
    by Turing machines. Many fundamental mathematical questions cannot be
    answered if there is no precise definition for algorithm.

3. Explain the term memory hierarchy and diagram it.
 
   [registers]                         high speed, high cost, low capacity
   [cache]                                        |
   [primary memory (RAM)]                         |
   [secondary memory (hard disk)]                 \/
   [tape, DVD, CD]                     low speed, low cost, high capacity

4. What is the history of the transistor? Who founded Intel?

   The transistor was invented at Bell Labs by Bill Shockly, John Bardeen,
    and Walter Brattain. Gordon Moore and Robert Noyce founded Intel.

5. Compare interrupts and polling.

   Interrupts are the mechanism by which devices signal the CPU when they have
    data to transfer. Polling is the process by which a CPU asks each device
    in turn if it has data. Polling is simple to implement, but wastes CPU
    cycles.
 
6. How much memory (how many memory cells) can a 32-bit machine 
    address?

    2^32 (there are 32 bits, each can have 2 different values)
    4,294,967,296

7. Explain the fetch-decode-execute cycle. How does a pipeline
    help speed up a computer?

    The fetch-decode-execute cycle is essentially the endless series of steps
     that the CPU is involved in to execute user programs and software 
     applications. A typical cycle may look like this:

     1. Fetch instruction (data in memory) pointed to by PC. Store in IR.
     2. Increment the PC. (PC=PC+4)
     3. Decode the instruction in IR.
     4. Fetch operands (any data) needed by the instruction.
     5. Execute the instruction (usually involves the ALU)
     6. Write back any results to the proper registers.
     7. Check for interrupt flag.
     8. Goto step 1.

8. Diagram a one-bit half-adder.

   It's easiest to start with the truth table and generate the circuit from
    there.

    A + B = SUM, COUT
    0   0    0     0
    0   1    1     0
    1   0    1     0
    1   1    0     1

   We notice that the SUM column corrosponds to the values for an "XOR"
    truth table, and that the COUT column is really an "AND" truth table.

   A      B
   |      |
   |      |
   +------|-------------||--\
   |      |             >>XOR>--- SUM
   |      +-------------||--/
   |      |
   |      |
   |      |
  ----------
  |        |
  |  AND   |
  \        /
   \      /
    \----/
       |
       |
      COUT

9. Explain RISC vs. CISC and the relative advantages and 
    disadvantages of each.

    RISC
      - Small instructions that execute in 1 cycle (1 clock tick)
      - Direct hardware execution
      - Issue many instructions at once
      - pipeline
      - minimal number of instructions reference memory
      - many general pupose registers


    CISC
      - complex addressing modes, many instructions reference memory
      - large number of instructions
      - usually a microcode interpretation layer
      
    CISC has a large legacy base of applications; even though RISC is
    "cleaner", wholesale abandoment of the CISC infrastructure would have
    been too expensive, so many RISC concepts were incorporated into later
    CISC chips.

10. What are the two best answers in Computer Science?

  1. It depends.
  2. 2^n