Quizzes from CS100, Spring 1994

This page contains eight quizzes that were given in Computer Science 100 when I taught it in the Spring term of 1994. Answers to each question are included, and in some cases notes on the answers. Most of these notes were written to clear up common student mispercetions that were apparent in their answers to the quiz questions.

The quizzes covered, more or less, the first eight chapters from The Most Complex Machine as well as computer labs based on the same material. (Sorry that this is in plain text format, but that is how I wrote it up at the time.)

Here are some links to the individual quizzes:

--David Eck

Quiz 1, with answers

1.  Q: Write down the binary representations for the numbers from
       zero to twelve, starting 0, 1, 10, ...

    A: Counting in base 2 from 0 to 12.

         0  1  10  11  100  101  110  111  1000  1001  1010  1011 1100

2.  Q: What is ASCII code

    A: ASCII code is a particular encoding used to represent text.  Each
       possible character is assigned an eight-bit binary number as its
       code.  (Characters are things like letters, punctuation, tabs,
       carriage returns, ...)  It is used by most computers to store and
       manipulate character data.

    NOTE:  ASCII code is not "machine language".  Machine language
           is a technical term refering to _instructions_ that are
           encoded in a such a way that they can be directly  executed
           by the CPU.  In some sense, the CPU "understands" machine
           language, but it does not understand ASCII code.  It can
           manipulate ASCII code as _data_, but only by executing a
           program that tells it what to do with the ASCII encoded
           characters.  (ASCII code might have been called a "machine
           language" if the term "machine language" weren't already taken
           to mean something else.)

3.  Q: What is meant by the fetch-and-execute cycle?

    A: The fetch-and-execute cycle is what the CPU does to execute a
       program:  It gets a single instruction from memory and carries
       out that instruction, and it repeats this cycle over and over.

4.  Q: How is the memory of a computer structured and what is it
       used for?

    A: The computer's memory is structured as a sequence of numbered
       locations.  Each location holds a binary number of some fixed
       size.  (In most modern computers, each location holds an 8-bit
       number, but in general, the number of bits could be anything.)
       The memory holds program instructions and data to be used by 
       the CPU.

    NOTE:  a)  The term "memory" in English is ambiguous, because it
           can refer to both the place where information is stored
           and to the information itself.  ("My memory is getting
           bad" vs. "I have a lot of nice memories of Spring Break".)
           In computer's,  "memory" always refer to the _place_
           where information is stored.  We say that the memory
           "holds" or "stores" information.

           b)  Here is one of the ways in which our simple picture
           of a computer is wrong:  I have given you the false impression
           that each location in memory can hold a complete instruction in a
           program, but this is not generally true.  It simply takes
           more than eight bits to encode an instruction.  So, an
           instruction is in general spread out over several locations.
           The same is true for data.  An "integer" in most computers
           is stored in two or four consecutive locations rather than
           just one, for example.  (The simple model computer we will
           look at in Chapter 3 has 16 bits per location and does in
           fact use only one location for an instruction.)

5.  Q: The textbook talks a lot about "structured complexity".  What
       is mean by structured complexity and how does it differ from
       mere complication?

    A: Our minds are not capable of grasping large amounts of detail unless
       it has some structure.  You would find it almost impossible to memorize
       a random sequence of a thousand of characters.  If the characters form
       form words in a poem or song, it is easier.
           Structured complexity refers to the fact that complex complex
       objects/data/programs/etc can be built up level-by-level from simple
       components.  The chunking that goes on at each level is simple enough
       to be comprehensible, but you end up with something that is really
       very complex.

Quiz 2, with answers

1.  Q: Add the following two binary numbers and explain briedly the
       procedure you used to do so.

    A: To add binary numbers, start at the right and work to the left,
       adding one column in the sum at each step.  When the sum in a
       column is two or three (that is, 10 or 11 in binary), then there
       is a carry into the next column.  In this example:

            1 1 1       1 1 1         
              1 0 1 1 0 0 1 0 1
            +   1 1 0 1 0 1 1 1
            1 0 0 0 1 1 1 1 0 0 

       The ones in the top row are carries.

2.  Q: Draw a circuit that computes the value of the Boolean expression:
            (A AND (NOT B)) OR (NOT (B AND C))

    A: Using the words AND, OR and NOT instead of drawing the gates,
       the circuit for  (A and (not B)) or (not (B and C)) looks 
       something like this:

            A ---------+__
                        __ AND--------+_____
            B --+-NOT--+               _____OR-------
                |_________            |
                        __ AND---NOT--+

       For a description of the method used to build the circuit,
       see the answer to lab question 1, below.

3.  Q: Consider the following circuit.  Assume that the inputs, A, B, and
       C are set to ON, ON, and OFF, respectively, as shown.  Label the
       output of each gate in the circuit to show whether it is ON or OFF.

       The circuit looked something like this:
          A --------|
             ON     | AND --------| NOT ------------------------|
                  ,-|                                           | OR --------
          B -----|-------------------------.                   ,|
             ON   \                         \__ |             /
                   `-|                          | AND -------'
                     | OR ---------| NOT -------|
          C ---------|

    A: The AND gate at upper left has two inputs that are ON; its output is ON.
       The OR gate at the lower left has one input ON and one OFF; it is ON.
       Each NOT gate has input ON; the output of each NOT gate is OFF.
       The AND gate at the lower right has one inputs OFF and one ON; it is OFF.
       The OR gate at the right has both inputs OFF, it is OFF.

4.  Q: Write down an expression o fBoolean algebra that describes the
       output of he circuit in the preceding problem in terms of its
       inputs, A, B, and C.

    A: The expression that serves as a "blueprint" for the circuit in
       problem 3 is:

             (not (A and B)) or ((not (B or C)) and B)

       This expression can most easily be built up from "left to right"
       by labeling the output of EACH gate in the circuit.  The output
       of a gate is a simple combination of its inputs.  For example,
       if the inputs of an AND gate are "B" and "not (B or C)", then
       the output of that gate is "B and (not (B or C))".  So, the method
       used in this problem is really not very different from the one
       used in problem 3!  (That is, build up the final answer one gate
       at a time.)

5.  Q: What is a full adder circuit?  (What computation does it perform?
       What inputs and outputs does it have?)

    A: A full adder is a circuit with three input wires and two output
       wires.  The three inputs represent three bits to be added.  The
       sum of these bits is a two-bit number represented by the output
       of the circuit.  Thus, the circuit does computations of the
       form:  0 + 1 + 0 = 01,  0 + 1 + 1 = 10, and 1 + 1 + 1 = 11.
       A 16-bit adder is made of 16 full adders.  Each full adder does
       one column in the sum.

Quiz 3, with answers

1. Q: A black box has an interface and an implementation.  Explain what is
      meant here by the terms interface and implementation, and give examples.

   A: A black box divides the world into two parts, the part inside the
      box and the part outside.  These communicate through the box's interface,
      which defines what inputs it takes and what outputs it produces.
      The inside of the box, the part that actually takes the inputs and
      produces the outputs, is called the implementation.  Subcircuits
      of the type used in xLogicCircuits are a good example: A circuit can
      be created and saved in a file.  Later it can be used as a black box
      inside another circuit.  Another example is a car, which is used by
      a driver as a black box:  When you step on the gas [input], the
      car goes [output]; the stuff "under the hood" that makes it go is
      the implementation.

        NOTE:  If you say "you don't have to understand how a black box
               works (inside) in order to use it," that's true, but it
               is only part of the story.  As "conceptual tools",
               black boxes divide problems into almost-independent parts
               that interact in fairly simple ways.  This is sometimes
               called "modularity", a concept that comes up again in
               Chapter 7 with regard to programming.  Modularity makes
               complex systems easier to design.  It also makes them
               easier to "fix", since you can change the implementation
               of a black box as long as you don't change the way it
               looks "from the outside".

2. Q: What is the purpose of the Control circuit, and how does it carry out
      that purpose?
   A: Our model computer was designed so that all the basic operations
      inside the CPU can be accomplished by turning control wires on and
      off.  Each fetch-and-execute cycle is just a sequence of these basic
      operations.  The purpose of the Control circuit is to execute machine
      language programs by controlling the execution of fetch-and-execute
      cycles.  It does this by turning control wires on and off in the
      right sequence.  (It's inputs contain all the information necessary
      to determine which wires need to be on; the Control circuit responds
      to these inputs by turning on those wires.)

3. Q: Explain the purpose of the address register, ADDR, and give a specific
      example of how it is used by the CPU.

   A: The address register is attached to the Address wires of the main
      memory.  The only way the CPU can tell the main memory which location
      it wants to use is to put the location number into the address register.
      For example, when the CPU wants to store a number into memory, it first
      puts the number of the location where it is to be stored into the 
      address register.  Only then can it store the number.

        NOTE:  The PC and the address register play very different roles.
               The PC holds the location in memory of the next instruction
               in the program.  In order to get that instruction out of
               memory, the CPU must first put the correct location into
               the ADDR register.  It does this at the beginning of each
               fetch-and-execute cycle by turning on the Load-ADDR-from-PC
               control wire.  But ADDR is used at other times as well,
               such as whenever the CPU needs to store a number in memory.
               In the meantime, while the ADDR is being used in all kinds of
               ways, it is the job of the PC to remember the number of the
               next instruction in the program.

4. Q: What role does the COUNT register play in the computations performed by
      the CPU.

   A: The COUNT register counts off the steps in each fetch-and-execute
      cycle.  Each cycle takes several little steps.  When COUNT = 1, the
      first step is performed; when COUNT = 2, the second, and so on.  At
      the end of one cycle, the value of COUNT is reset to zero so that the
      next cycle can begin.

        NOTE:  You shouldn't confuse the type of counting that COUNT does
               with the counting done by the PC.  These two operate on
               different "levels".  PC counts off the instructions in a
               program that is being executed.  But on the lower, CPU
               level, the execution of one instruction takes several 
               steps.  These small, low-level steps that carry out one
               instruction are counted off by the COUNT register.  So,
               the COUNT register counts through a whole cycle as the
               PC changes just once.

5. Q: What is meant by an addressing mode.

   A: An instruction in xComputer's machine language is represented
      by a sixteen-bit binary number.  The first six bits encode the 
      instruction, such as ADD or L0D-C or HLT.  The remaining ten are
      data for the instruction.  The addressing mode refers to the way
      in which these data bits are interpreted.  In constant addressing,
      the data bits specify the actual number to be used by the instruction;
      in direct addressing, they specify a memory location; in indirect
      addressing, they also specify a memory location, but that location
      just holds a "pointer" to another memory location.  ["Pointer" just
      means the address of theat memory location.]

Quiz 4, with answers

1.  Q: What is meant by computational universality?

    A: A machine is said to be "computationally universal" if it can do
       any calculation that can be done by any computer whatsoever.  Because
       of limitations on memory size, there are no truly universal machines,
       but if we imagine giving a computer as much memory as it needs,
       then every computer is computationally universal.  [We might say that
       this is what distnguishes a computer from a simpler computing device,
       such as an adding machine.]

2.  Q: Ignoring limitations on memory size, any computer can be programmed to
       simulate any other computer.  What is the significance of this fact?

    A: This is the _evidence_ we have for the universality of every computer:
       If computer A can simulate anything computer B can do, then computer A
       is at least as powerful as computer B.  But by the same reasoning,
       B is at least as powerful as A, so in fact they are equally powerful.
       [Along the same lines, if we want to show that a particular Turing
       machine is universal, one way to do so is to show that it can
       similate a computer.]

3.  Q: Explain in words the basic step-by-step operation of a Turing machine.

    A: Your explanation should include mention of its tape, its state and 
       its rules.
          A computation performed by a Turing machine is a sequence of
       very simple individual steps.  Its action during each step is
       determined entirely by its current state and by the symbol in the
       current square on the tape.  For each combination of state and
       symbol it has a rule that specifies its action.  That action has
       three parts:  it writes a [possibly] new symbol in the square,
       moves one square to the left or right on the tape, and [possibly]
       changes to a new state.

4.  Q: Consider the Turing machine whose rule table is given on the
       attached sheet.
       a) Suppose this machine is started in state 0 on the following tape on
          the square containing the z.  Show what the tape will contain when the
          machine halts, and indicate where the machine will be when it halts.
          The tape contains:    ...##z#$0#yy$x#$###... 
          (Here, # represents a blank square.)
       b) Explain in words ehat this machine will do whan it is started on
          any tape.

          The rule table looks like this:

               Current   Current                       New
               State     Symbol     Write     Move     State
               -------   -------   -------   ------   -------
                  0         #          #        R        0
                  0         o          o        R        0
                  0         i          i        R        0
                  0         x          x        R        0
                  0         y          y        R        0
                  0         z          z        R        0
                  0         $          $        R        1
                  1         #          #        R        1
                  1         0          #        R        1
                  1         i          #        R        1
                  1         x          #        R        1
                  1         y          #        R        1
                  1         z          #        R        1
                  1         $          $        L        h

       A: (a) This problem can be done by blindly following the rules
          in the table, just as the Turing machine itself does.  It starts on
          a z in state 0.  The rule for this state and symbol tells it to
          leave the z there, move right, and stay in state 0.  It then sees
          a blank while in state 0, and the rule tells it to leave the blank,
          move right and stay in state 0.  Now, it sees a $ while in state 0;
          It leaves the $ there, moves right and changes to state 1.  As you
          continue in this way, you will see that the machine continues to
          move to the right in state 1 and erases symbols as it goes, until
          it gets to the next $.  It than moves left and halts. In the
          end, the tape contains:   ...##z#$####$x#$###...   and the machine
          is on the # to the left of the second $.

          (b) This question is asking for the "purpose" of the machine.  On a
          high level, we could say that this machine "erases the tape between
          between the two $'s to the right of its starting location on the tape."
          On a slightly lower level, we could say that the machine "moves right
          without chaning anything until it comes to a $.  It then changes to
          state 1 and continues to move right, erasing all symbols, until it
          comes to another $."  [Note that if there are no $'s, or only one $,
          to the right of the machine's starting location on the tape, then
          it will continue to compute forever.]

Quiz 5, with answers

1. Q: By the end of the 1940s, the first general-purpose, electronic
      stored-program computers had been created.  Briefly explain the
      meaning of each of the following adjectives as used here:

   A: (1) general-purpose
        This means that the computer can be programmed to
        do any computation.  It is _universal_.  It is not limited
        to one specific task.

      (2) electronic
        The computer is constructed from fast vacuum tubes
        (or, later, transisters), as opposed to slow relays or even
        slower rods and gears.  [NOTE: An "electronic" device has
        NO MOVING PARTS, unless you count the electrons themselves.
        A relay runs on electricity, but it has a metal contact that
        moves back and forth between two possible positions.  It takes
        time to move a piece of metal, so even the fastest relays are
        slow compared to electronic devices.  It takes much less time
        to turn a flow of current on and off.  Note that relays are
        "electric" but not "electronic".]

      (3) stored-program
        The computer executes programs that are stored as information
        in its memory.  This makes it possible to easily change a
        program without physically modifying the computer. [NOTE: It
        is not the fact that the computer can "remember" a program
        that is important here; a deck of punched cards can "remember"
        a program forever.  What is important is that the computer can
        switch from one task to a completely different task at the 
        click of a mouse.]

2. Q: What role did J. Presper Eckert and John Mauchly play in the
      history of computers?

   A: Eckert and Mauchly designed and built the ENAIC, the first
      fully programmable electronic computer.  They also came up
      the idea of storing programs in the computer's memory.
      (They did not, however, complete the first machine based
      on this idea.  Their design--for the EDSAC--was first,
      but the British got their machine built first.)

3. Q: What are device drivers, and why are they needed?

   A: A device driver is software--a collection of subroutines
      and interrupts--that the CPU can execute in order to
      communicate with and control a specific hardware device,
      such as a keyboard, disk drive or scanner.  Device drivers
      are necessary since the only thing that the COU can do is
      execute programs; if it is to have any communication with
      the world at all, it must do so by executing programs.

4. Q: A bus is a component found in many real computer
      systems.  What is meant by a ``bus'' in tontext?

   A: A bus is a set of wires connecting the CPU to a number of
      other devices.  The important point is that several different
      devices can "plug into" the bus, so that the CPU doesn't have
      to be built with all possible connections for all possible
      devices already built-in.  Busses can carry addresses, data
      and control signals.

5. Q: One of the potential problems associated with the introduction
      of computers into the workplace is deskilling.  What is  meant
      by "deskilling"?

   A:  Deskilling is the replacement of interesting, high-paying,
       high-skill jobs with boring, low-paying, low-skill jobs.
       It is thought that this could happen if a lot of the
       "expertise" necessary to do the job can be programmed int
       a computer.  [NOTE:  This is not the same problem as
       unemployment caused by automation.  I could imagine 5 
       happy, highly skilled, $100,000-a-year engineers begin
       replaced by 10 miserable, $15,000-a-year computer 
       attendants: more jobs, but "deskilled" jobs.]

Quiz 6, with answers

1.  Q: Write a sequence of xTurtle commands that will draw two separate 
       long, parallel lines.

    A:  There are a lot of ways to do this. Here is one:


         Here is another:


2.  Q: Draw the figure that would be produced by the following xTurtle program:

        DECLARE s            A: This draws five line segments connected
        s := 5                    by right-angle turns.  Each segment is
        LOOP                      one unit shorter than the previous one.
           forward(s)             The picture is something like this:
           s := s - 1               ---------------
           EXIT IF s = 0                          |
        END LOOP                          ---     |
                                          |       |
                                          |       |

           (Note that one way to attack a problem like this one
            is just to "play computer" and follow the instructions
            step-by-step the way the computer would.  Part of doing
            this is keeping track of the values of any variables.)

3.  Q: Explain what is meant by the terms syntax and semantics, and give

    A:  Syntax refers to grammatical structure, while semantics
        refers to meaning.  The syntax of a language is the set
        of rules that determine what is grammitcally legal in that
        language.  The semantics of a language is the set of rules
        that determine what something means in that language.
        For example, the syntax of a LOOP statement in xTurtle
        says that such a statement consists of the word LOOP,
        followed by a sequence of statemenst, followed by the
        words END LOOP.  The semantics of a LOOP statement
        says that the computer is to execute the statements
        over and over (until an EXIT statement terminates the
        loop).  [Note: The terms syntax and semantics are also
        used to refer to individual sentences or programs.
        For example, the syntax of the sentence "John walks quickly"
        is that it consists of a noun, a verb and an adverb.  It's
        semantics is the idea conveyed by the sentence.]

4.  Q: Explain briefly what is meant by preconditions and postconditions
       and how they can be used in writing programs.

    A: A precondition is a something that has to be true at a given
       point during the execution of a program, for the rest of the
       program to work correctly.  A postcondition is something
       that is actually true at a given point after some part of
       a program has been executed.  When writing a program, it
       can be useful to think in terms of postconditions and
       preconditions:  Looking at any point in the program, you can
       ask, do the postconditions [that we know are true because of
       what has already been done in the program] match up with
       the preconditions [that have to be true for the rest of the
       program to do what you want it to do]?  If not, you know
       you have to insert some instructions to make the preconditions
            As a simple example, a precondition for the statement
       "x := sqrt(y)" to succeed without crashing is that "y >= 0",
       since the square root of a negative number is not allowed.
       This means that _before_ this statement in a program, you
       should either make sure you know that y>=0 for some reason,
       or you should test that this is true.
            [Note that preconditions and postconditions are _not_
       parts of a program!  They are not "commands".  They are
       conditions such as "x is > 0" or "there is a square 
       on the screen".  A condition is something that can be either
       true or false.  A precondition is a condition that you want
       to make sure will be true when the program is being executed.]

5.  Q: Exactly what sequence of steps might the computer go through
       to execute the assignment statement   x := y + 3.

    A:  The computer would have to retrieve the value stored in
        whatever memory location corresponds to the variable y,
        add 3 to that value, and then store the result into
        the memory location that corresponds to the variable x.

        [Note: Some people seemed to take this question to mean,
        "What sequence of statements would the computer have
        to execute BEFORE this one, in order for this statement
        to make sense in a program."  That's not what the question
        asks, but I gave partial credit for it.)

Quiz 7, with answers

1. Q: "Parameters" come in two types: actual parameters and dummy parameters.
      (Dummy parameters are also called formal parameters.)  What are
      parameters?  What is the difference between acutal parameters and
      dummy parameters?  Give Examples.

   A: Parameters are used for communication between a subroutine and
      the rest of the program.  They are part of the interface of the
      "black box" that the subroutine represents.  A dummy parameter is
      a name used in the _definition_ of a subroutine to represent the
      actual parameter that will be passed to the subroutine when it is
      called.  For example, in the simple subroutine

                 SUB angle(side,degrees)
                 END SUB

      "side" and "degrees" are dummy parameters.  When the subroutine
      is called, the actual values provided for these dummy parameters
      are called actual parameters.  For example, in

                 angle(length,(measure + 1)/3)

      The "3", "30", "length" and "(measure + 1)/3" are all actual
      parameters.  (For the second command to be legal, of course,
      length and measure must be DECLAREd as variables earlier in
      the program.)

2. Q: Discuss the software life cycle.  List some of the stages in the 
      cycle and explain what is meant by each.

   A:  Programs of moderate to large size have a life cycle that
       starts with the specification of a problem to be solved,
       continues through the development of a program to solve that
       problem and ends, perhaps many years later, when the program
       finally becomes obsolete.  We can identify certain stages
       in this life cycle:

          -- specification:  The problem is stated in clear,
                             unambiguous language.

          -- analysis and design:  The problem is analyzed to see
                             how it can be solved by a computer, and
                             the major parts of the solution are

          -- coding:  The solution is translated into a program
                             written in computer language

          -- testing:  The program is run under realistic conditions
                             to uncover any problems or "bugs"

          -- maintenance:  After the program is released, work continues
                             to keep it up-to-date and to fix any newly
                             discovered bugs.

3. Q: (a) Write an xTurtle subroutien that draws a "T" shape, as was shown on
       the blackboard.  Use only turn, forward and backward commands in the
       definition of the subroutine.  The turtle should return to its initial
       position and heading at the end of the subroutine.

       (b) Use the subroutine you have written (along with some other xTrutle
       commands) to draw the second figure that was shown on the blackboard.

            (The "T" looked something like this:


            It was labeled as 5 units long and 2 units high.)

       A: (a) Here is one possible solution:

            SUB DrawT     { DrawT is the _name_ of the subroutine }
              back(2)     { At this point, the figure has been drawn; }
              forward (1) { now return turtle to its starting point }
            END SUB

          (b)  Here are three possible soultions.  One is just a simple sequence
               of commands, while the other two use loops.  The name used to
               call the subroutine here should be whatever name was used
               for the subroutien in part (a).

               {1}  DrawT    { Tells the computer to execute the subroutine. }
                    turn(45) { rotate turtle 45 degrees }
               {2}  DECLARE count
                    count := 0  { no T's drawn yet }
                      DrawT     { draw a T }
                      count := count + 1  { count the T }
                      EXIT if count = 5   { end if 5 T's have been drawn }
                    END LOOP
               {3}  LOOP
                      EXIT IF heading = 180
                    END LOOP

Quiz 8, with answers

1.  Q: Pick any two of the following important computer languages and explain
       the importance of each of the two languages you choose in the evolution
       of computer languages: FORTRAN, ALGOL-60, COBOL, Pascal, Ada and C++.

    A: FORTRAN :  The first high-level programming language.

       ALGOL-60 :  The language that influenced almost all languages
                   developed after 1960.  It introduced loops and if
                   statements as _structures_ (where FORTRAN used jumps),
                   recursive subroutines, and the concept of global and
                   local variables.  The report on ALGOL-60 also introduced

       COBOL :  Whereas FORTRAN and ALGOL-60 were designed mainly for
                numerical scientific computing, COBOL was designed to
                support the kind of data processing used in business and
                government.  COBOL introduced records and files, and so was
                an important step in the recognition of the importance of
                data structures.

       Pascal :  Introduced extensive data structuring capabilities; widely
                 used for teaching programming.

       Ada :  A vast extension of Pascal, incorporating ideas on modularity,
              abstract data types, and software reusability.

       C++ :  An object-oriented language, one of the most widely used today
              by professional programmers.

2.  Q: Discuss the analogy between "structured complexity" as seen in data
       structures and as seen in subroutines.  Give specific examples.

    A:  Structured complexity refers to the construction of a complex
        system as a sequence of levels, where details on one level are
        chunked together into black boxes to be used as components
        on higher levels.  Data structures and subroutines are both
        used in constucting complex systems is this way; the difference
        is that data structures deal with structures of data while
        subroutines deal with structures of instructions.
           Thus, once a data type has been defined, it can be used
        to build more complicated types.  For example, a "date" type
        might be defined to consist of a month, a day and a year.
        Such a date type might be used to represent a student's
        date of birth in a "student record" type.  From this in
        turn, an array of student records could be constructed.
           Similarly, once a subroutine for drawing squares is written,
        it could be used in another subroutine, such as a subroutine
        that draws a house.  A house-drawing subroutine could be used
        in turn to draw a village consisting of several houses.

3.  Q: Suppose that a program needs to store information about 30 students.
       For each student, the student's name and three test grades must be
       stored.  Describe a data type, constructed using arrays and records,
       that could be used to store all this information.

    A:  Top-down Approach.  Since there are 30 students, and we have the
        same set of data items for each student, we should make an array
        with 30 items, where each item contains all the data for one
        particular student.  Each item in the array would be a record
        containing a string (the student's name) and three real numbers
        (the student's grades on the tests).

        Bottom-up Approach:  We have at least two different types of
        data items for each student, so we should group the data for
        a given student--name and three test grades--into a record.
        To take into account that there are 30 students, we should
        make an array of 30 such records.

        [Note: In Pascal, the relevant data types could be defined a
               TYPE StudentData = RECORD
                                    name: string;
                                    test1: real;
                                    test2: real;
                                    test3: real;
                     StudentList = ARRAY[1..30] OF StudentData;

        Alternatively, the three test grades might be stored in
        an array before they are combined with the name into a
        record.  And maybe the name could be split into first name
        and last name.  That is:

              TYPE GradeArray = ARRAY[1..3] of real;

                   StudentData = RECORD
                                    LastName: string;
                                    FirstName: string;
                                    TestGrades: GradeArray;

                   StudentList = ARRAY[1..30] OF StudentData;

        There are many ways to build a data structure, just as
        there are many ways to write a program. ]