CPSC 100, Spring 1997:
Answers to Test #1

This is the first 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: What is the boolean algebra expression that describes the output of the following circuit in terms of its inputs, A, B, and C?

(picture of circuit)

Answer: ((NOT A) AND B) OR (NOT (B OR C))

Question 2: For each of the following circuits, mark the final output as either ON or OFF, given that the inputs are set as shown.

(picture of circuits)

Answer: The answers are marked in big red letters on the circuit above. Intermediate results are marked in green. (The red and green stuff was not in the original problem, of course.)

Question 3: A multiplexer is a circuit with three inputs (A, B, and C) and one output, which has the following behavior: If C is ON, then the output is equal to A; but if C is OFF, then the output is equal to B.

(a) Write down a Boolean algebra expression that describes the output of this circuit in terms of its inputs A, B, and C.

(b) Draw a circuit using your expression from part {\bf (a)} as a "blueprint." (Note: You can get some credit for this part of the problem even if your answer to part (a) is wrong.)

Answer: (a) (C AND A) OR ((NOT C) AND B). This answer can be obtained by analyzing the cases where the output of the multiplexer circuit should be on. If C is on, then the output should be equal to A. So if C is on and A is also on, then the output is on. This gives "C AND A" as one case where the output is on. Similarly if C is off, then the output should be equal to B. So if C is off and B is on, then the output should be on. This gives "(NOT C) AND B" as another case when the output should be on. The final answer is obtained by noting that the output is on if either the first case is true OR the second case is true.

(b) Using the above expression as a blueprint, we get the circuit:

(picture of circuit)

Note: It is also possible to do this problem by creating an input/output table that shows all the possible combinations of values for the three inputs, A, B, and C, along with the desired output in each case. There are eight rows in the table. In the rows where C is ON, the output value is the same as the value of A; in the rows where C is OFF, the output value is the same as the value of B:

                 A   |   B   |   C   |   Output
                OFF  |  OFF  |  OFF  |    OFF
                ON   |  OFF  |  OFF  |    OFF
                OFF  |  ON   |  OFF  |    ON
                ON   |  ON   |  OFF  |    ON
                OFF  |  OFF  |  ON   |    OFF
                ON   |  OFF  |  ON   |    ON
                OFF  |  ON   |  ON   |    OFF
                ON   |  ON   |  ON   |    ON

A Boolean algebra expression to describe the output can be generated mechanically from this table:

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

Question 4: There are 256 different 8-bit binary numbers. Why?

Answer: An 8-bit binary number has eight positions. For each position, there are two possibilities, either a zero or a one. The number of possibilities for each position are multiplied together to give the total number of possibilities: 2*2*2*2*2*2*2*2 = 28 = 256.

Question 5 (a) Briefly state the meaning of each of the individual assembly language instructions in the following program for xComputer:

           Location  Instruction
              0        LOD-C 0
              1        STO 20
              2        LOD-C 1
              3        STO 21
              4        LOD 20
              5        ADD 21
              6        STO 20
              7        LOD 21
              8        INC
              9        STO 21
              10       SUB-C 100
              11       JMZ 13
              12       JMP 4
              13       HLT

(b) Now explain what the program does as a whole. (What is its purpose? What meaningful task does it accomplish?) To answer this question, you will have to analyze the program and perhaps simulate part of its execution by hand. This is not an easy question.

Answer: For part (a), the problem is to explain the meaning of each individual line in the program:

          Location   Instruction      Meaning
              0        LOD-C 0          Load the number 0 into the Accumulator
              1        STO 20           Store the number in the Accumulator into location 20 (in RAM)
              2        LOD-C 1          Load the number 1 into the Accumulator
              3        STO 21           Store the number in the Accumulator into location 21
              4        LOD 20           Load the number in location 20 into the Accumulator
              5        ADD 21           Add the number in location 21 to the Accumulator
              6        STO 20           Store the number in the Accumulator into location 20
              7        LOD 21           Load the number in location 21 into the Accumulator
              8        INC              Add 1 to the number in the Accumulator
              9        STO 21           Store the number in the Accumulator into location 21
              10       SUB-C 100        Subtract 100 from the Accumulator
              11       JMZ 13           If the number in the Accumulator is 0, then jump to location 13
              12       JMP 4            Jump to location 4
              13       HLT              Halt the computer

(b) This program computes 1 + 2 + 3 + ... + 99. The program begins by storing 0 in location 20 and 1 in location 21. Then it goes in a loop, the part of the program from location 4 to location 12. In this loop, the program first adds whatever is in location 21 into location 20. Thus, the number in location 20 increases each time through the loop by whatever is in location 21. Then the program adds 1 to the value in location 21. So, the number in location 21 starts at 1, then increases to 2, then to 3, then to 4, and so on as the computer executes the loop over and over. In the meantime, location 20 starts at 0. The first time through the loop, 1 is added to this, giving 1. The second time through, 2 is added, giving 1+2. The third time, 3 is added, giving 1+2+3. And so forth. This stops when the SUB-C command produces a value of zero, which is when the value in location 21 has just become 100. At this time the value in location 21 is 1+2+3+...+99.

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

(a) Pixel
(b) Register
(c) Control circuit (a component of the CPU)
(d) Computational Universality


(a) A pixel is one of the small dots used to represent an image in digital form. Each pixel can be individually assigned a color. The screen of a computer is made up of pixels.

(b) A register is a memory unit that is part of the CPU. A register holds a binary number that is being used directly in the ongoing computation being performed by the CPU.

(c) The control circuit is the circuit that "decides" what action to take at each step of the fetch-and-execute cycle. Its uses inputs from the count register, instruction register, and accumulator to determine what needs to be done. It carries out the appropriate action by turning control wires on and off.

(d) Computational universality refers to the fact that -- except for limitations imposed by the amount of time and memory available -- all computers are equivalent in the problems they can solve.

Question 7: Explain what is meant by structured complexity, and give several examples from different areas (such as computer science, biology, politics,...).

Answer: Structured complexity is the main theme of this course. It refers to that fact that complex systems can be constructed from very simple components, in a series of levels of increasing complexity. The step from one level to the next can be fairly simple, but by continuing through a number of levels, great complexity can be achieved. Even though the system as a whole is very complex, however, the structure allows the system to be understood. This type of complexity has to be distinguished from "mere complication" such as the complexity of a jigsaw puzzle, where each piece has to be placed individually and there is no level of structure between that of the individual piece and that of the whole puzzle. The computer is an excellent example of structured complexity. Transistors are combined to make logic gates; logic gates are combined to make simple circuits such as adders; simple circuits are combined to make more complex circuits such as registers, control circuits, and ALUs; and finally these complex circuits can be used to construct a complete CPU. Similarly a book is made from letters that are combined to make words, which are combined to make sentences, which are combined to make paragraphs, and so forth. And in biology, the body is made up or organs, which are made up of tissues, which are made up of cells, which are made up of smaller components such as the nucleus, mitochondria, and so on.

Question 8: Explain what is meant by the fetch-and-execute cycle, and give some specific examples of the type of simple operations that can occur as steps in a single fetch-and-execute cycle.

Answer: The fetch-and-execute cycle is the basic activity of the CPU by which it executes machine-language programs. During each fetch-and-execute cycle, one machine language instruction is read from memory and is carried out. The cycle repeats over and over as long as the computer is running. A single fetch-and-execute cycle is itself made up of a sequence of very simple operations such as copying a number from one register to another, loading the answer from the ALU into the accumulator, adding one to the value stored in a register, and copying a number from the output wires of the main memory into a register. Each of these operations can be accomplished just by turning the correct control wires on and off. This is done by the control circuit, depending only on the values stored in the count register, the instruction register, and the accumulator.

Question 9: A program written in a high-level language cannot be executed directly by a CPU. Why not? In fact, though, most computer programs are written in a high-level language. How can such programs be executed? (Discuss both compilers and interpreters in your answer.)

Answer: A CPU can only directly execute instructions that are expressed in the machine language of that particular type of CPU. When such an instruction is placed into the instruction register of the CPU, its pattern of zeros and ones physically causes the actions that are necessary to carry out the instruction. It's not a matter of "understanding" the instruction or "figuring out" what it means. The CPU is built to carry out a certain set of instructions in this way, and that set of instructions is called the machine language of that CPU. Any program written in another language, such as a high-level programming language, must be translated into the machine language of a given machine before it can be executed by that machine. Fortunately, this translation can be done by programs. There are two approaches to such translation: A compiler is a program that translates a program into machine language all at once, in advance. The compiled program can then be run independently as often as desired. An interpreter translates a program step-by-step, as it is being executed.

Question 10: Computation can be defined as "the mechanical manipulation of symbols." Explain exactly what this means, and give some examples.

Answer: A symbol is something that is meaningless in itself, but that can have some sort of externally assigned meaning. Words are examples of symbols. The word "dog" is just a sequence of letters, but we recognize that sequence as somehow representing the idea of a dog. In computation, symbols are manipulated according to definite, unambiguous rules. The rules have nothing to do with the external meaning of the symbols. There is no thought or understanding involved. This is what it means to say that computation is mechanical. For example, if a computer looks up the work "dog" in a dictionary, it is simply following the rules for alphabetical order. What it does has nothing to do with the fact that the word dog refers to furry, usually friendly animals. Similarly when the computer (or a person) adds two numbers together, it is only following the rules of arithmetic.

David Eck, 30 April 1997