CPSC 100, Fall 1997:
Answers to Test #2

This is the second test from the course Computer Science 100: Principles of Computer Science, taught by David Eck. The answers that are included here are sample answers only. There might be many other answers to a given problem that would also receive full credit. See the home page for the text, The Most Complex Machine, for more information about the course.


Question 1: Define the following terms, as they relate to this course:

a) interrupt

b) syntax

c) dummy parameter

d) the Halting Problem

Answer:

a) An interrupt is a physical signal, sent along a wire to the CPU from another device in a computer system. The CPU reacts to this signal by saving its current state and jumping to an "interrupt handler," which is software that is meant to respond to the condition that caused the interrupt. After the interrupt handler has been executed, the CPU will restore the state that it saved; that is, it will return to what it was doing before the interrupt occurred

b) The syntax of a language is its grammar. It is the set of rules that determine what strings of symbols are legally a part of that language.

c) A dummy parameter is used in a subroutine definition as a stand-in for an actual parameter that will be provided when the subroutine is called. For example, in a subroutine that begins "SUB doThing(x,y)", x and y are dummy parameters. (In a subroutine call statement such as doThing(length,count+1) or doThing(5,7), the parameters length, count+1, 5, and 7 are "actual parameters.")

d) The Halting Problem is this: Given any program whatsoever, determine in advance (without actually running the program) whether or not that program will ever halt when it is run. The Halting Problem is "unsolvable" in the sense that there is no program that can correctly answer this question in all cases.


Question 2: What is the purpose of a declare statement in an xTurtle program? (What does a declare statement do, and why is it necessary?)

Answer: A declare statement, such as "declare x", is used in a program to declare a variable that will be used in the program. It is not legal to use a variable in a program unless it has been declared. When the computer executes this statement, it allocates a memory location and associates it with the variable's name. The memory location is used to store the value of the variable. Thus, the statement "x := 7" really means "store the value 7 into the memory location named x".


Question 3: Explain what is meant by the software life cycle, and list at least three of the stages in the software life cycle.

Answer: A typical program has a life cycle that can extend over many years. The life cycle includes the original design and creation of the program, but it also includes a long period of maintenance during which the program is modified to meet new requirements and newly discovered bugs are fixed. The stages in the software life cycle include: specification, analysis and design, coding, testing and debugging, and maintenance.


Question 4: Write an xTurtle program that will show one square nested inside another, as shown.

nested squares

Answer: There are many ways to do this. Here are two possible answers. (Both solutions assume that the turtle is at the lower left corner of the outer square.)

        forward(5)                        SUB square(x,y,size)
        turn(90)                              { Draw a square of the given size
        forward(5)                              with lower left corner at the
        turn(90)                                point (x,y) }
        forward(5)                           PenUp
        turn(90)                             moveTp(x,y)
        forward(5)                           PenDown
        turn(90)                             move(size,0)
                                             move(0,size)
        PenUp                                move(-size,0)
        move(1,1)                            move(0,-size)
        PenDown                           END SUB
        
        forward(3)                        square(0,0,5)
        turn(90)                          square(1,1,3)
        forward(3)
        turn(90)
        forward(3)
        turn(90)
        forward(3)

Question 5: a) Write an xTurtle subroutine that will draw a wheel with six spokes as shown. The radius of the wheel should be a parameter to the subroutine. (You might find it easiest to draw the spokes first, then draw a circle around them. Note that the angle between the spokes is 60 degrees.)

wheel

b) Now write a LOOP that uses your subroutine from part a) to draw a line of five wheels, like this:

row of five wheels

Answer:Note: For part a), you have to remember how circles are drawn. Assuming that R is a positive number, then the command circle(R) draws a circle of radius R that "sticks out" on the left side of the current turtle position. To draw the rim of the wheel, you need to move the turtle to a position on the rim and orient the turtle so that it faces in the correct direction. Here are possible answers to this problem:

a) The wheel-drawing subroutine:

       SUB wheel(radius)
       
              { Draw a 6-spoke wheel of the given radius.
                The wheel will be centered on the current
                turtle position, and at the end of the
                subroutine, the turtle will be back at its
                original position and orientation.  This
                subroutine assumes that the turtle is
                originally facing to the right.  }
                
           DECLARE ct
           ct := 0      { for counting the number of spokes }
           LOOP  { Draw the spokes. }
              forward(radius)
              back(radius)
              turn(60)
              ct := ct + 1
              EXIT if ct = 6
           END LOOP
           { The turtle has turned 360 degrees, so it is
             again facing to the right. }
           
           PenUp
           move(0,-radius)   { Move to a position at the
                               bottom of the wheel. }
           PenDown
           circle(radius)    { Draw the rim. }
           PenUp
           move(0,radius)    { Move back to the center. }
           
        END SUB
        

b) The program to draw five wheels, using a loop:

        DECLARE ct  { for counting the number of wheels }
        ct := 0
        LOOP
           wheel(3)   { Draw a wheel of radius 3. }
           PenUp
           forward(8) { Move to center of next wheel. }
           PenDown
           ct := ct + 1
           EXIT IF ct = 5
        END LOOP

Question 6: Carefully describe the picture produced by the following program. (You can't actually draw the picture, since it is in color, but you might want to draw a black-and-white version.)

           DECLARE x, ct
           ct := 0
           LOOP
              x := randomInt(3)
              rgb(random,random,random)
              turn(45)
              forward(x)
              turn(-90)
              forward(x)
              turn(45)
              ct := ct + 1
              EXIT IF ct = 10
           END LOOP

Answer: Each execution of the loop produces a "peak", shaped like an upside-down V. The color of each peak will be chosen at random. The height of the line will be one of three sizes, chosen at random. There will be 10 of these peaks, lined up in a horizontal row, each one attached to the next. Here is a sample, in color:

line of 10 peaks


Question 7: Answer the following questions, assuming that the subroutine guess has been defined as:

         SUB guess(num,len)
            declare ct
            ct := 0
            LOOP
               forward(len)
               back(len)
               ct := ct + 1
               EXIT IF ct = num
               turn(90)
               PenUp
               forward(1)
               PenDown
               turn(-90)
            END LOOP
         END SUB

a) Draw the figure produced by guess(1,10)

b) Draw the figure produced by guess(3,5)

c) Draw the figure produced by:

                   guess(5,2)
                   turn(120)
                   guess(5,2)
                   turn(120)
                   guess(5,2)

Answer: The subroutine call statement guess(ct,len) will produce a set of ct parallel lines. The length of each line will be len. The distance between lines will be 1. The first line is drawn from the starting position of the turtle, extending in front of it in the direction of the turtle's heading. The next line is drawn displaced one unit to the left of the turtle's original position, and so on. At the end of the subroutine, the turtle is at the starting point of the last line that was drawn. Note that for part c), the first line of the second group is connected to the last line of the first group. Here are the pictures:

answers to a, b, and c


Question 8: Carefully explain what is meant by computational universality, and describe the evidence we have that computational universality is true.

Answer: Computational universality refers to the fact that, aside from limitations of time and available memory, all computers are equivalent in the problems that they can solve. The evidence for this is that one computer can simulate any computation done by any other computer, provided it is given enough time and memory. There are several different types of simulation. For example, Computer A can simulate Computer B by running an interpreter that knows how to execute programs written in the machine language of Computer B. However, this is not entirely convincing, since it is not obvious that such an interpreter can be written if the machine language of Computer B is very complicated. However, we could also program Computer A to do a low-level simulation of Computer B. In a low-level simulation, the operation of each individual gate in Computer B is simulated. Since the low-level components of any existing computer are very simple, it is always possible to simulate them, even on a very simple computer. (It will take a lot of time and memory, but we are assuming that we have as much time an memory as necessary.) Thus, a very simple computer can simulate all the computations that can be performed even on a very complex computer.


Question 9 Complex programs should be constructed from modules What is a module? Why is a subroutine an example of a module? Why should complex programs be constructed from modules?

Answer: A module is a fairly independent component of a larger, more complex system. The modules in a system should communicate with one another only in straightforward, well-defined, and easy-to-understand ways. A subroutine is an example of a module because it is a component of a complete program, and it communicates with the rest of the program through a well-defined list of parameters. Modules are useful for several reasons. Since modules are fairly independent, each module can be written and tested independently. Since modules interact with other modules in simple ways, there is a fair chance that when the full system is assembled, the modules will be able to work together and the system as a whole will function correctly. Furthermore, building prgrams from modules makes the programs easier to maintain. For example, if a problem is found in one module, that module can be replaced with a corrected version without messing up the rest of the program.


Question 10: Consider a typical, modern computer system that contains many devices in addition to the CPU and main memory. What exactly does the CPU in such a system know about other devices in the system? (There is no single correct answer to this. Your answer should display a depth of knowledge about how computer systems work. Do not trivialize the question!)

Answer: Literally, of course, the CPU doesn't "know" anything. All it does is fetch instructions and execute them, one after another. And if it can be said to know anything at all, it is only how to execute machine language instructions and how to respond to interrupts. However, the CPU can still communicate with and control other devices in the system -- provided that it has software that it can execute to do so. The software that the CPU needs is called a device driver. The device driver consists of subroutines and interrupt handlers that the CPU can use to communicate with and control the device. In a sense, then, once the device driver has been loaded into the system, the CPU does know everything it needs to know about the device. Without the device driver, the device is useless.


David Eck, 7 November 1997