CPSC 100, Spring 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: Discuss subroutines as "black boxes" or "modules." Discuss what this means, why it is important, and what it has to do with the use of parameters and local variables.

Answer: A subroutine consists of a sequence of instructions for performing a certain task, made into a "black box" and given a name. Later, when that task needs to be performed, the subroutine can simply be "called" by giving its name, without thinking about the details of how the task is to be performed. Thus, a subroutine is a "module" that can be used as a building block in making complex program. Constructing a program from modules makes the program easier to design, easier to write, and easier to maintain, because the modules are relatively independent units that can be worked on independently, at least to some extent. For this to work well, the modules should be as self-contained as possible and should communicate with the rest of the program in straightforward, easy-to-understand ways. For subroutines, communication is done through parameters, which allow information to be passed back and forth between the subroutine and the rest of the program. On the other hand, information that is used only inside the subroutine can be stored in local variables. These variables are part of the "implementation" of the black box, and are completely invisible to the rest of the program. Using local variables in a subroutine, rather than global variables, helps keep the subroutine self-contained.


Question 2 (a): Write an xTurtle subroutine that will draw a square with an X inside, as shown in this picture:

(square with X)

Answer: My answer assumes that the side of the square is one unit long. There are many ways to draw the picture. Here is one. It uses the fact that the length of each of the cross bars is sqrt(2), as I wrote on the board during the test. (I've noted a precondition and postcondition for the subroutine, since these are important for part (b). None of the comments were a required part of the answer.)

          SUB CrossedSquare

              { Precondition: the turtle is at the lower left corner
                   of the square that is to be drawn, and the turtle is
                   facing to the right. }

              forward(1)         { Draw the square. }
              turn(90)
              forward(1)
              turn(90)
              forward(1)
              turn(90)
              forward(1)
              turn(90)

              turn(45)        
              forward(sqrt(2))  { Draw diagonal from lower left to upper right }
              turn(135)
              forward(1)        { Move to upper left corner }
              turn(135)
              forward(sqrt(2))  { Draw diagonal from upper left to lower right }
              turn(45)

              { Postcondition: the turtle is at the lower right corner
                   of the square that has been drawn, facing right. }

           END SUB

Question 2 (b): Use your subroutine to draw a row of 10 such squares, as shown. (That is, write a program that will draw this picture, using your subroutine.) Use a LOOP to draw the squares.

(line of 10 squares with X's)

Answer: The following program simply calls the subroutine ten times. Note that at the end of the subroutine, the turtle is left at the right position and in the right orientation for drawing the next square. If the subroutine were written differently -- that is, if it had a different postcondition -- it might be necessary to insert some commands into the program to get move or orient the turtle to satisfy the subroutine's precondition.

          DECLARE count
          count := 0
          LOOP
             CrossedSquare
             count := count + 1
             EXIT IF count = 10
          END LOOP

Question 3: What is meant by the Information Age (also known as the "post-industrial society")?

Answer: During the Industrial Revolution of the nineteenth century, industry replaced agriculture as the major source of employment and wealth. Some people believe that we are now entering a post-industrial society in which information will be the most important commodity, and in which most jobs will involve collecting, processing, and using information and information technology. This transformation has been made possible by the computer.


Question 4: What values are drawn onto the screen by the following program?

               DECLARE x
               x := 2
               LOOP
                  DrawText("#x")
                  x := x * x
                  EXIT IF x > 100
               END LOOP

Answer: This question should be answered by tracing the execution of the program by hand. Before the loop, the variable x is created and its value is set to 2. So, the first time the computer gets to the DrawText("#x") statement, the value which is output is 2. Then, the statement x := x * x, changes the value of x to 2*2, which is 4. Since 4 is not greater than 100, the loop is executed again. This time, the output is 4, and then the value of x is changed to 4*4, which is 16. Again, 16 is not greater than 100, so the loop repeats. The number 16 is drawn on the screen, and the value of x is changed to 16*16. Since 16*16 is greater than 100, the loop ends and the program also ends. The numbers that have been output onto the screen are:

                2
                4
                16

Question 5: Consider the following xTurtle program. Explain in words what is accomplished by this program. Don't just say what each line does; describe the overall purpose of the program. Also draw a picture that illustrates what the program might produce when it is run. (Because of the randomness in the program, a different picture will be produced each time it is run; however, they are all basically similar.)

            DECLARE length
            DECLARE count
            count := 0
            LOOP
               face(RandomInt(360))
               length := RandomInt(5)
               forward(length)
               back(length)
               count := count + 1
               EXIT IF count = 100
           END LOOP

Answer: The loop in this program is repeated 100 times. Each time the loop is executed, the computer chooses a random angle between 1 and 360 and a random length between 1 and 5. It then draws a line of that length radiating out from the point (0,0) at the selected angle. The result is a "starburst" pattern, consisting of 100 lines of lengths 1, 2, 3, 4, and 5 radiating out from a common center. Here are two pictures actually produced by this program:

(two starbursts)


Question 6: Explain the terms integrated circuit and microprocessor.

Answer: (Repeated from Quiz 4.) An integrated circuit consists of several (or perhaps, millions) transistors and other electronic components on a single small "chip" of silicon. An integrated circuit is faster and more reliable than the same circuit made out of individual transistors. A microprocessor is an integrated circuit that contains a complete CPU on a single chip. It was the development of microprocessors that made today's cheap personal microcomputers possible.


Question 7: Define the term recursive subroutine.

Answer: A recursive subroutine is one that calls itself, either directly or indirectly. (Note: A subroutine calls itself "indirectly" if it calls another subroutine that call back to itself -- either directly or indirectly. This is a recursive definition!)


Question 8: Consider the following recursive subroutine:

          SUB Guess(length,complexity)

              forward(length)
              IF (complexity > 0) THEN
                 Guess(length/3, complexity - 1)
              END IF
              turn(120)

              forward(length)
              IF (complexity > 0) THEN
                 Guess(length/3, complexity - 1)
              END IF
              turn(120)

              forward(length)
              IF (complexity > 0) THEN
                 Guess(length/3, complexity - 1)
              END IF
              turn(120)

          END SUB

Given this definition, draw the picture that would be produced by each of the following subroutine call statements:  (a) Guess(9,0)  (b) Guess(9,1)  (a) Guess(9,2) 

Answer: If the complexity is zero, then the subroutine reduces to the statements forward(length) and turn(120), repeated three times. The result is an equilaterial triangle. If complexity is one, you get the same picture with three smaller (one-third size) triangles attached at the vertices. The picture for complexity two is constructed from a triangle with a scaled-down copy of the complexity-1 figure attached at each vertex. Here are pictures that were produced by actually running program:

(recursively decorated triangles)


Question 9: Explain the terms precondition and postcondition, and discuss how thinking about preconditions and postconditions can help you to write programs.

Answer: A precondition is a condition that you want to be true at a certain point during the execution of a program, if the program is to continue correctly. For example, a precondition of the statement y := sqrt(x) is that x is greater than or equal to zero. If this precondition is not met, the program will crash. Another example of a precondition is given in the answer to Question 2 on this test; in this example, the subroutine will not produce the correct picture if its precondition is not met before it is called. A postcondition, on the other hand, is something that you know to be true at a certain point during the execution of a program. A postcondition is a verifiable consequence of the statements that have just been executed. For example, a postcondition of the statement y := sqrt(x) is that x = y2. When you are writing a program, preconditions and postconditions can be helpful in fitting parts of the program together correctly. If you notice that a precondition occurs at a certain point in a program, you can make sure that the precondition is a postcondition of the preceding statements. That is, the precondition is a requirement that has to be met, and you should make sure that the code you have written will guarantee that the precondition holds.


Question 10: Explain the terms syntax and semantics. Then consider the xTurtle statement "x := y + 3". What would be meant by the "syntax" of this statement? What about the "semantics"?

Answer: Syntax refers to the grammar of a language. It is the set of rules that specify what is considered legal in the language. In the case of a programming language, a syntactically correct program is one that can be compiled. If a program contains a syntax error, the computer will refuse to compile and run it. Semantics, on the other hand, refers to meaning. To be semantically correct, it is not enough that the program runs -- it also has to produce the correct result. Syntactically, "x := y + 3" is a correctly written assignment statement, consisting of a variable, followed by the ":=" operator, followed by a mathematical formula. The semantics, or meaning, of this statement is what happens when the statement is executed: The number 3 is added to the value of y, and the result is stored as a new value for the variable x. (The semantics might also include the meaning of this computation is a particular program, that is, the reason why the programmer wants this computation to be performed.)


Question 11: (Question 5 from Chapter 5)  In Mary Shelly's novel, Frankenstein, Dr. Frankenstein creates and gives life to a "monster." He recoils in horror from his creation and abandons it. In the end, of course, the monster has its revenge. It is generally thought that Dr. Frankenstein paid the price for trying to take on God-like powers by creating life. But perhaps his real crime lay in refusing to take responsibility for his creation. Comment on this, in the context of Section 5.3 [concerning social and ethical issues in computing].

Answer: (Obviously, there are many ways of answering this question. But the answer should say something about the responsibility of the creator for the creation. Here is my answer to the question, quoted from pages 399 of The Most Complex Machine.)

Frankenstein is the archetypical story of technology gone out of control. The scientist who seeks knowledge and power without considering the consequences is destroyed by the "monster" he creates. It is a story still worth reading and considering.

The story in the original novel is rather different from the version popularized in the movies. The monster in the book is no unthinking brute; it is articulate and explains its motivations even as it drives its creator to his destruction. The monster claims that it could have been a force for good as easily as for evil, and that Dr. Frankenstein, by creating it and then abandoning it, is responsible for what it has become.

It has always seemed to me that Frankenstein is about the obligation of scientists and other seekers-after-knowledge to try to understand all the consequences of what they create and to take responsibility for it. In Section 5.3, I have argued that this is certainly true for computer technology, which is in itself neither good nor evil, but which has the capacity for both.


David Eck, 31 May 1997