This page contains questions and answers for the second test in CS100: Principles of Computer Science, a course based on the book The Most Comples Machine. The answers given here are sample answers only. There is always some variation in the answers that would receive full credit.
Question 1: Define each of the following terms as they relate to this course
(a) bus (part of a computer system)
Answer: A bus is a bundle of wires through which devices that are part of a computer system can communicate. A bus can carry data, addresses, and control signals. Several devices can all be hooked up to the same bus, and each device can communicate with any other device on the bus. Busses help to organize complex computer systems consisting of many interacting devices.
(b) syntax of a language
Answer: The syntax of the language is the set of rules that determine what constitutes a legal (or grammatical) string of symbols in that language.
(c) module
Answer: A module is a component of a larger system that performs some definite, well-defined function and that interacts with other modules in the system in well-defined, easy-to-understand ways. A comples system, such as a computer or a program, that is built from modules tends to be easier to design, build, and maintain than one that is not.
(d) dummy parameter
Answer: A dummy parameter is a name that is used in a subrotutine definition as a placeholder for an actual parameter that will be passed to the subroutine when the subroutine is called.
(e) the software life cycle
Answer: All programs have a "life-cycle" consisting of various stages including: specification, analysis and design, coding, testing and debugging, and maintenance. Programming and program design must take into account all these stages, not just the actual programming that is done in the coding stage.
Question 2: One approach to discussing the semantics of a programming language is to relate it to processes and states. What is meant by these two terms? What do they have to do with the meaning of the statements in a program?
Answer: When a computer executes a program, it goes through a sequence of states. A state contains all the information relevant to the execution of the program at a particular instant of time. The idea is that if the program is stopped and its state is saved, then it can be restarted later by restoring the state, and it will continue on just as if it had never been interrupted.
A process is just the sequence of states that the computer goes through as it executes the program. In some sense, the process is the "meaning" of the program, in the same way that a movie is the "meaning" of a script. From this point of view, the meaning of a statement is that it carries the computer from one state to another. That is, the meaning of the statement is the change that it produces in the state.
Question 3: Here is a BNF specification for a small subset of English. Write 3 different <sentence>s that can be produced from these rules. For full credit, your sentences must show a variety of possible structures.
<sentence> :== <noun> <verb> <noun>
<noun_part> :== <name> | <thing>
<name> :== John | Mary | President Hersch
<thing> :== <determiner> <common_noun> [ who <verb> <noun> ]
<determiner> :== a | the | some | every
<common_noun> :== dog | unicorn | student | book
<verb> :== knows | likes | hates | looks for
Answer: There are an infinite number of different possible answers. For example:
1) John likes the dog
2) President Hersch looks for a student who likes some book
3) the dog who knows Mary hates the student who likes
the unicorn who knows every dog
Question 4: Random numbers have been a useful tool for making interesting pictures with xTurtle. Here are two programs that use random numbers. Pick one of them and describe what is produced on the screen when the program is run. You can also include a picture if you like.
LOOP DECLARE x
PenUp LOOP
MoveTo(randomInt(10),randomInt(10)) x := randomInt(10)
PenDown forward(x)
forward(0.3) back(0.3) turn(90) back(x)
forward(0.3) back(0.3) turn(90) turn(5)
forward(0.3) back(0.3) turn(90) EXIT IF heading = 0
forward(0.3) back(0.3) turn(90) END LOOP
EXIT if 1 = 2
END LOOP
Answer: For the program on the left: Each time randomInt(10) is called, it returns a random integer in the range 1 through 10. Thus the command MoveTo(randomInt(10),randomInt(10)) moves the turtle to some random point (x,y), where both x and y are integers in the range 1 to 10. Because the pen is up, no line is drawn as it moves. Then, the four lines after the PenDown command draw a small plus sign. The plus sign is drawn with its center at the current location of the turtle. The result is a sprinkling of random plus signs scattered on the screen. Since the condition "1=2" in the EXIT IF statement is never true, the comptuer just keeps drawing more and more plus signs.
For the program on the right: The turtle, starting from the center of the screen facing right, draws a sequence of lines eminating from that point. Each line is separated by a 5 degree angle from the next. Since the turtle stops after it returns to its original heading--that is, after turning 360 degrees--a total of 72 lines are drawn. The length of each line is chosen randomly to be some integer between 1 and 10. The result is a "starburst" of lines of random lengths growing out of the point (0,0).
Here are screen dumps of images produced by these two programs:
Question 5: Consider the following xTurtle program:
SUB rect(length)
forward(length) turn(90)
forward(length) turn(90)
forward(length) turn(90)
forward(length) turn(90)
END SUB
DECLARE size
size := 1
LOOP
rect(size)
EXIT IF size = 5
turn(-90)
forward(1)
turn(90)
size := size + 1
END LOOP
(a) Draw the picture that would be produced by the subroutine call rect(5).
Answer: The subroutine rect is just the standard subroutine that draws a square of a specified size. The subroutine call rect(5) draws a square whose side is five units long and leaves the turtle in its original postion and orientation. I won't bother to draw the picture here.
(a) Draw the picture produced by the entire program.
Answer: The pictue contains five squares of increasing size. After each square is drawn, the lower left corner moves down by 1 and the side of the square increases by one. The result is that the upper left corners of the squares are all in the same location. So, the picture looks like this:
Question 6: Write a complete xTurtle program that will draw the picture drawn below. The picture contains 24 lines, separated by angles of 15 degrees. There are several ways to approach this problem. To get the maximum possible credit, include comments to explain your reasoning.
Answer: If you think of this picture as showing lines eminating from the point (0,0), except that half of each line is not drawn, you might get this program (assuming that the individual line segments are three units long):
LOOP
PenUp
forward(3) { no line drawn here }
PenDown
forward(3) { draw the second half of the line }
PenUp
back(6) { move back to center without drawing }
turn(15) { rotate before drawing next line }
exit if heading = 0 { done when facing right again }
END LOOP
Another way to look at the program is an invisible circle, say of radius 3, with lines sticking out of it every 15 degrees. In that case, the program might be similar to the "necklace" exercise from Lab Number 9. A counting loop is used to count the 24 lines:
DECLARE count
count := 0
LOOP
PenUp
arc(15,3) { move over a 15-degree invisible arc }
PenDown
turn(-90)
forward(3) { draw a line perpendicular to the circle, }
back(3) { and then go back to starting point of line }
turn(90)
count := count + 1 { count this line }
EXIT IF count = 24
END LOOP
Question 7: Discuss the concept of an operating system. What is its purpose? Why is it necessary? List some of the major components of an operating system, and discribe their function.
Answer: The operating system of a computer is the basic software--programs, subroutines, and interrupt handlers---that controls the computer. It allows all the hardware devices that are part of the computer system to communicate, and it also handles communication with the user. The operating system includes device drivers that allow the CPU to interact with and control other devices such as disk drives, monitors, and printers; it includes a user interface or "command shell" that accepts commands from the user and carries them out; it includes subroutines that can be called by application programs using an API (Application Programming Interface); and it includes a start-up program that runs automatically when the computer is turned on.
Question 8: Explain how subroutines can be used in the construction of complex computer programs. Keep in mind that once a subroutine has been defined, it can be called from inside other subroutines. What does you answer have to do with structured complexity? (Your score on this problem depends on the completeness of your answer and the insight it shows.)
Answer: There is a trivial (but important) sense in which subroutines can help in writing complex programs: If you have a prewritten subroutine that performs some task that your program needs, you can use that subroutine as a "black box" without understanding how it works. Subroutines, then, are reusable parts that can be written once and for all, instead of solving the same problem over and over. However, this doesn't really answer the question, since someone has to solve the problem in the first place, and there is still the basic question: how can a complex program be constructed from whatever resources are available (including, perhaps, certain subroutines that have already been written).
When we talk about complex systems, we have to talk about levels of complexity. Real complexity cannot easily be achieved in one step. Instead, components on one level are chunked into more complex components that can then be used as building blocks on the next level. The step from one level to the next shouldn't be too big, and many levels might therefore be necessary. Subroutines are one important way in which complex programs are built level-by-level. A subroutine is a chunk of code that, once it has been written, can be used as part of a higher-level chunk, which can then be used in its turn on an even higer level.