This is the first of two in-class tests from CPSC 100: Principles of Computer Science, Spring 1996. The answers given would receive full credit, but in many cases, there are variations or even completely different answers that would also receive full credit. The "Notes" are meant to clarify the answer or to provide some interesting extra information.
Question 1: Define the following terms, as they relate to this course:
(a) CPU
Answer: The Central Processing Unit is the active part of the computer that actually executes machine language instructions. (The instructions are fetched from main memory, which holds the program that the CPU is to execute.)
(b) feedback loop (in a circuit)
Answer: A feedback loop occurs in a circuit when the output wire from some gate is connected, either directly or possibly through a number of intermediate gates, back to an input of the same gate. Feedback loops are necessary for building memory circuits.
(c) address (of a location in memory)
Answer: Main memory is made up of a sequence of locations. The number that specifies the postion of the location in this sequence is called the address of the location. By specifying an address, you pick out one particular location for storing or retrieving data.
(d) register
Answer: A register is a memory circuit that is part of the CPU (rather than main memory). Registers hold numbers that the CPU can use directly in its calculation. Examples of registers include the program counter and the accumulator.
Question 2: Suppose that on a certain computer, the main memory has 12 address wires, 32 data-in wires, and 32 data-out wires. How many memory locations are there in the main memory? How many bits does each memory location hold? Explain your reasoning.
Answer: The main memory has 4096 locations, and each location holds a 32-bit number. The data-in and data-out wires are used, respectively, to store data into a location in memory and to read the contents of a location. Each data-in (or each data-out) wire corresponds to one bit of the number in that location.
The address wires are used to specify one particular location out of all the locations in memory. Each address wire can be set to zero or to one. Each location corresponds to a different pattern of zeros and ones. Thus, the locations are numbered with 12-bit binary numbers as: 000000000000, 000000000001, 000000000010, 000000000011, ..., 111111111111. The number of locations is the same as the number of 12-bit binary numbers, which is 2 raised to the 12-th power, or 4096. To put it more simply, since each address wire can be independently set to 0 or 1, there are 2 times 2 times ... times 2 different possible address, where there are 12 two's being multiplied together.
Note: This question is related to various things we have seen in class: There are 256 possible ASCII codes since each code is an 8-bit binary number and 2 raised to the eighth power is 8. In an input/output table for a circuit with 3 inputs, there are 8 rows because 8 is 2 raised to the third power. In the main memory of xComputer, there are 1024 locations because it has 10 address wires, and 2 raised to the tenth power is 1024.
Question 3: What ordinary, base-ten number is represented by the binary number $101101_2$? Show your work.
Answer: Each postion in a base-two number corresponds to a power of 2. Using ^ to represent "raised to the power" and X for multiplication, we can write
101101 = 1 X 2^5 + 0 X 2^4 + 1 X 2^3 + 1 X 2^2 + 0 X 2^1 + 1 X 2^0
= 32 + 0 + 8 + 4 + 0 + 1
= 45
Note: Some people actually tried doing this by counting up in binary from 0 to 101101. This is OK, but is surely harder than it needs to be! (Also, very difficult to get right.)
Question 4: Give the Boolean algebra expression that corresponds to the following circuit:
Answer: (not (A and B)) or (A and (not B))
Note: This is a somewhat silly circuit, since it is equivalent to the simpler circuit given by (not (A and B)). That is, for any given combination of inputs, these two circuits both give the same output.
Question 5: Suppose you want to build a circuit with three inputs and one output that satisfies the following input/output table:
A B C Output
--------------------------|---------------
ON ON ON | OFF
ON ON OFF | OFF
ON OFF ON | ON
ON OFF OFF | OFF
OFF ON ON | OFF
OFF ON OFF | ON
OFF OFF ON | OFF
OFF OFF OFF | OFF
(a) Write down a Boolean algebra expression that describes the output in terms of the three inputs, A, B, and C.
Answer:
(A and (not B) and C) or ((not A) and B and (not C))
(b) Draw the circuit specified by the expression you wrote in part (a).
Answer:
Note: You should not have to think to do a problem like this one. The steps for producing first a Boolean algebra expression and then a circuit from an input/output table are straightforward and mechanical.
Question 6: Explain what is meant by the fetch-and-execute cycle and what role it plays in the execution of programs.
Answer: The fetch-and-execute cycle is the method used by the CPU to execute machine languages programs. A program is a sequence of instructions that are executed one at a time by the CPU. In the fetch-and-execute cycle, the CPU fetches one instruction from memory, executes that instruction, then fetches the next instruction and executes it, and so on.
Question 7: One of the most important registers in the xComputer is the accumulator. Discuss some of the ways in which the accumulator is used. In particular, how is it used in the following assembly language instructions: LOD-C 42, ADD-C 10, and STO 1023.
Answer: The accumulator is used to hold a data value that is being used in the current computation of the CPU. For example, when a number from memory is "added", it is added to the number currently in the accumulator. It is also possible to move numbers between the accumulator and memory. In particular, for example: To exeucte the instruction LOD-C 42, the CPU will load the number 42 into the accumulator. To execute ADD-C 10, the CPU will add the number 10 to whatever is currently in the accumulator and put the result back into the accumulator. To execute STO 1023, the CPU will copy the number currently in the accumulator into memory location number 1023.
Question 8 (a): The CPU of xComputer contains a kind of "clock" that is not meant to keep time. Instead, the ticking of this clock is what makes the computer run. Explain exactly how this happens. What happens in the CPU when the clock "ticks"?
Answer: As the clock ticks, it turns a wire on and off. Each time this wire is turned on, the number in the COUNT register is incremented by one. Since the count register is connected to the control circuit, this changes the inputs to the control circuit. And from there, other changes occur until one step of the fetch-and-execute cycle has been fully executed.
(b)Explain why you can't necessarily make a computer run faster simply by increasing the speed at which its clock ticks.
Answer: Since one step of the fetch-and-execute cycle is done for each tick of the clock, you can in fact make the computer run faster by increasing the clock speed, but only up to a certain point. The ticking of the clock causes a series of changes in the states of various logic gates. It takes some time for all these changes to complete, and so there is a certain minimum amount of time that must be allowed between clock ticks. Otherwise, the next step in the fetch-and-execute cycle might begin before the results from the previous step are ready.
Question 9: 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 built up in relatively easy stages. Simple components can be "chunked" together into somewhat complex structures that then can be used as building blocks in even more complex structures and so forth, for as many levels of structure as needed. This is important because it would be impossible to deal with things as complex as computers and computer programs if they had to be understood all at once in complete detail. Computers are built from transistors, but there are many levels of structure between transistors and computers. Transistors are chunked into gates, which are used to produce simple circuits such as half-adders and one-bit memories, which can then be combined into more complex circuits such as multi-bit adders and multi-bit memories, and so forth. Similarly, programs are built from very simple instructions using structuring devices such as loops, decisions, and subroutines.
Note: No one will ever get full credit in one of my courses for any question about structured complexity unless they show some understanding of the idea of levels of structure.
Question 10: Explain the role that the Control Circuit plays in a computer.
Answer: Everything that happens in the CPU happens because certain control wires are turned on and off. For example, when it is necessary to copy the number from the program counter register into the address register, this can be accomplished simply by turning on a control wire named "Load-ADDR-from-PC". All the control wires are attached to outputs from the control circuit, and it is the control circuit that is responsible for deciding which control wires need to be turned on and off at any given time. It does this on the basis of its inputs, which are connected to the COUNT register, the instruction register, and the accumulator. In some sense, the control circuit is the real "brain" of the computer, since it decides what has to happen at each step, and it manipulates the control wires to make it happen.
Question 11: In a computer's main memory, both programs and data are represented as binary numbers. How does the computer know the difference? (Or does it?) What does this have to do with the idea of computation as "the mechanical manipulation of symbols"? (This is meant to be a somewhat open-ended question; please respond fully, in essay form.)
Answer: The computer doesn't really "know" anything! It just goes to some memory location (indicated by the program counter), grabs the number it contains, and treats it as machine language instruction to be executed. If the number in that location happens to "really" be data, the CPU won't know; it will still interpret it as an instruction and respond to it as such.
All the computer does is follow rules mechanically. The numbers it uses as instructions and the numbers it manipulates as data are just symbols, whose meaning is irrelevant to the comptuation. A human user might see some meaning in the computation, but the meaning has no effect on what the computer does. The human user might say that the program was making a mistake when, for example, a jump instruction jumps to a location holding data rather than to a location holding part of the program. But the computer isn't really making a "mistake"; it's just following the program.
Note: There are many ways to answer this question. The answer given here is just one example.
[by David Eck]