CPSC 100, Fall 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: Draw the circuit that corresponds to the Boolean algebra expression

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

Answer: The circuit is as follows. Output wires in the circuit are labeled with the boolean expressions that they represent. (These labels are not a required part of the answer.)

Answer to problem 1


Question 2: Find the Boolean algebra expression that corresponds to the following logic circuit:

Circuit for problem 2

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


Question 3: One of the examples of feedback that we looked at was a circuit consisting of a single OR gate. Consider a similar circuit that uses an AND gate instead:

And gate in feedback loop

How does this circuit behave when its single input, A, is turned on and off? Why?

Answer: This is a perfectly useless circuit, since there is no way to ever turn its output on. As long as the input is OFF, the output of the AND gate must be OFF. Turning the input ON doesn't change this, since both inputs of the AND gate must be ON before its output will come ON.


Question 4: What does the following assembly language program do? What number is in location 10 when the program ends? Explain your answer.

                LOD-C 17
                STO   10
                ADD   10
                STO   10
                ADD   10
                STO   10
                HLT

Answer: The program adds 17 to itself, giving 34. It then adds 34 to itself, giving 68. This is the answer that is stored in location 10 when the program ends.

(This program loads the number 17 into the accumulator, and then stores it into location 10. Note that after the first STO 10 instruction, the number in the accumulator is still 17. The next instruction, ADD 10, adds the 17 from location 10 to the 17 in the AC to give 34. This answer is in the accumulator, and the second STO 10 instruction stores this 34 into location 10. The process repeats, giving 34 + 34, or 68, as the final answer in location 10.)


Question 5: Carefully explain the difference between the instruction ADD 17 and the instruction ADD-C 17.

Answer: Both of these instructions add a number to the accumulator. The instruction ADD-C 17 adds the number 17 itself to the accumulator. The instruction ADD 17 gets the number that is stored in location 17 in main memory, and adds that number to the accumulator.


Question 6: Both a machine language and a high-level language are programming languages. What is the difference between them?

Answer: A machine language is a programming language that consists of instructions encoded as binary numbers which can be executed directly by a given type of CPU. High-level languages cannot be executed directly. Instructions in a high level language are in a form closer to human language, which is easier for people to work with. But they must be translated into machine language by a compiler or an interpreter before they can be executed by a computer.


Question 7: Carefully explain the use of the ADDRESS wires on a main memory (or "RAM").

Answer: Main memory contains a numbered sequence of locations. Each location holds a binary number. Only one location can be used at any given time. To access a location, the address of that location -- expressed as a binary number -- must be put onto the address wires of the RAM. For example, if there are 10 address wires, then in order to access location 5 the address wires must be set to represent the binary number 0000000101, which is the binary representation of the address, 5, of the desired location.


Question 8: In xComputer, the first step of every fetch-and-execute cycle is Load-ADDR-from-PC. What is the purpose of this step? What role does it play in the fetch-and-execute cycle?

Answer: This step copies the number in the program counter (PC) into the address register (ADDR). The purpose of a fetch-and-execute cycle is to execute one instruction. The number in the PC is the address of the memory location where that instruction is stored. Putting this number into ADDR makes that location in main memory accessible. Then, later in the fetch-and-execute cycle, the CPU will be able to copy the instruction from the main memory's data-out wires.


Question 9: Carefully explain the role of the Control Circuit in xComputer. What task does it perform? How does it carry out its duties?

Answer: Everything that happens in a computer is accomplished by turning control wires on and off. These control wires cause the simple operations, such as Load-ADDR-from-PC or Increment-PC, that make up the fetch-and-execute cycle. These control wires are output wires of the Control Circuit. It is the task of the Control Circuit to carry out all the operations performed by the computer as it executes programs, and it does this by turing control wires on and off. (The Control Circuit is just a logic circuit. Its inputs contain all the information necessary to determine which control wires must be on and which must be off. The design of the control circuit causes it to respond automatically to any pattern of inputs with the appropriate pattern of outputs.)


Question 10: Why do computers use binary numbers, rather than ordinary, base-10 numbers?

Answer: Values in a computer are represented by wires which can be on or off. It is convenient to use these two values to represent the binary digits 0 and 1.


Question 11: What is the base-10 integer that is represented in base-2 as 11001012? Show your work!

Answer: Each bit in a binary number corresponds to a power of two. The rightmost bit corresponds to 20, the next bit to the left corresponds to 21, the next bit to 22, and so on. So,

11001012 = 26 + 25 + 22 + 20 = 64 + 32 + 4 + 1 = 101


Question 12: Carefully explain the function of the COUNT register in xComputer.

Answer: The COUNT register counts off the steps in a single fetch-and-execute cycle. Each instruction in a program is fetched into the CPU and executed in a sequence of several simple steps. The first of these steps occurs when COUNT is 1, the second when COUNT is 2, and so on. After the instruction has been completely executed, the value in the COUNT register is reset to zero, and the next fetch-and-execute cycle is ready to begin. (Note that the value in the COUNT register changes when the clock ticks; this in turn changes the inputs to the Control Circuit; and that actually causes the next step in the fetch-and-execute cycle to take place.)


Question 13: Suppose that a main memory is to have 65536 locations. How many address wires will that main memory need? Explain carefully why your answer is true. (Note: 65536 = 216.)

Answer: The main memory circuit would need 16 address wires. The address wires are used to pick out one particular memory location. Every possible combination of values for the address wires can specify a different memory location. Since there are two possible values (ON and OFF) for each wire, then with 16 wires, there will be a total of 216 combinations. (The memory locations will be numbered from 0000000000000000 to 1111111111111111 in binary.)


Question 14: The machine language for xComputer has 31 different instructions, but the language could be expanded to contain other useful instructions. Each instruction is represented by a 6-bit instruction code. Given that there are six bits available to encode an instruction, what is the maximum number of different instructions that could exist? Why?

Answer: 26, or 64, since with six bits there are 26 different binary numbers that can be represented.


Question 15: Explain what is meant by structured complexity, and give some examples of structured complexity that you have seen in this course.

Answer: Structured complexity refers to the 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. 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. Data, as it is represented in a computer, also exhibits structured complexity. All data is formed, ultimately, from bits. Bits are combined to make numbers and characters. Numbers and characters are combined to represent more complex data such as dates, words, sounds, and so on.


Question 16: At the beginning of the course, we defined computation as the "mechanical manipulation of symbols." After studying logic circuits and the construction of xComputer, you should have a greater appreciation of what that means. Write an essay discussing, first, what it means to say that computation is mechanical and, second, what evidence you have seen that the operation of a computer is mechanical. Your grade on this question will depend on the depth of understanding you display and on how well you present your ideas!

Answer: A symbol is something that is meaningless in itself, but that can have some sort of externally assigned meaning. 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. In this course we have seen a lot of evidence that computers are "mechanical" devices that compute without thought and without regard to the meaning of the computations that they perform. We have seen how the basic logical and arithmetical operations involved in computation are performed by logic circuits. But a logic circuit is simply a physical device that turns its output wires on and off in response to the settings on its input wires. On a higher level, we have seen how programs are executed in a sequence of simple steps, where each step happens because of the settings of certain wires, and the step itself is accomplished by a logic circuit, the Control Circuit, which does nothing but respond mechanically to the values on its input wires by turing some of its output wires on and off.


David Eck, 11 October 1997