This is the first of two in-class tests from CPSC 100: Principles of Computer Science, Fall 1995. 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) machine language
Answer: Machine language refers to the set of programming instructions that can be executed directly by the CPU of a given computer. Every type of computer has its own machine language. Machine language instructions are encoded as binary numbers.
(b) ASCII code
Answer: The ASCII code ("American Standard Code for Information Interchange") is a standardized way of assigning an eight-bit binary code number to each of the characters on the keyboard, so that they can be stored and used as data in a computer.
(c) ALU
Answer: The Arithmetic-Logic Unit is the component of the CPU that computes arithmetic and logical operations when they are required for the execution of machine language instructions.
(d) register
Answer: A register is a memory circuit that is a part of the CPU. A register holds a binary number that is available for direct use by the CPU. Examples include the Program Counter, the Instruction Register, and the Accumulator.
Question 2: Explain why "loops and decisions" are necessary for writing complex programs, and explain how they can be implemented in machine language.
Answer: Building a complex program requires the ability to "chunk" simple instructions together into meaningful structures. Loops and decisions are two of the methods that can be used to form such chunks. In machine language, where only very simple operations are available, "loops" must be implemented with jump instructions: A JMP instruction can tell the computer to return to the beginning of a loop, so that the instructions in the loop will be repeated over and over. Decisions can be implemented by conditional jump instructions, such as JMZ, which allow the computer to take different actions depending on the results of some test.
Note: We will see that loops and decisions are built into high-level languages, so that they don't have to be implemented in such languages by low-level jumps. We will also see that subroutines are an even more important method for building complex programs.
Question 3: What role does the clock play in a computer? What is the relationship of the clock to the fetch-and-execute cycle?
Answer: The clock turns its output wire on and off as it "ticks." It is this ticking that makes the computer go. Every time the clock ticks, the value in the COUNT register changes and another step of the fetch-and-execute cycle is begun.
Question 4 (a): Find the output of the following circuit for each possible combination of inputs (note that the circuit is the same in each picture; only the inputs are different):
(b)Write down the Boolean algebra expression that describes thiscircuit.
Answer: (a)The outputs of this circuit are as follows:
Top Input | Bottom Input | Output
------------|----------------|-----------
OFF | OFF | ON
OFF | ON | OFF
ON | OFF | OFF
ON | ON | ON
(b)The formula is: (not (A and (not B))) and ((not B) or A))
Note: This problem did not ask you to find a formula that has the same output as the pictured circuit -- that question would have many different answers. It asked you to find the formula that serves as an exact blueprint for the circuit, which has essentially just one answer (except for the possibility of swithching the arguments of an and or and or). You can find the correct expression by going through the circuit from left to right and figuring out what expression is represented by the output wire of each gate.
Question 5: A circuit is to be designed that has certain specified properties. It has three input wires named A, B, and C. It has one output wire. The desired output can be described as follows: If input C is ON, then the output should be the same as A; if input C is OFF, then the output should be the opposite of B.
(a)Write a Boolean algebra expression that describes the desired output in terms of A, B, and C.
(b)Using your answer to part (a) as a blueprint, draw a circuit that has the specified properties.
Answer: By considering the condition for the output to be on, the formula for the output can be seen to be: (C and A) or ((not C) and (not B)). The corresponding circuit is:
Note: This problem can be done more mechanically by first writing down the input/output table that specifies the behavior of the circuit:
A | B | C | OUTPUT
-------|-------|-------|-------------
OFF | OFF | OFF | ON
OFF | OFF | ON | OFF
OFF | ON | OFF | OFF
OFF | ON | ON | OFF
ON | OFF | OFF | ON
ON | OFF | ON | ON
ON | ON | OFF | OFF
ON | ON | ON | ON
From this table, you can then write down a Boolean algebra expression that
describes the circuit: ((not A) and (not B) and (not C)) or
(A and (not B) and (not C)) or (A and (not B) and C) or (A and B and C).
This expression can be used a blueprint for a rather complex circuit that has
the specified behavior. This approach has the advantage of leading
automatically to a correct answer, but it has the disadvantage of
producing an unnecisarily complicated circuit.
Question 6: "Everything that happens in the CPU happens because control wires are turned on and off." Give examples of the sorts of things that can happen when control wires are turned on and off.
Answer: Turning a control circuit on and off can, for example:
These are very simple operations, but everything that the computer does can be reduced to performing large numbers of such operations.
Question 7: What does the folowing short assembly language program do?
LOD-C 15
ADD-C 18
SUB-C 7
STO 10
HLT
Answer: This program takes the number 15, adds 18 to it, subtracts 7 from the result, stores the answer (that is, 26) in memory location number 10, and then halts.
Note: The "-C" in the instructions LOD-C, ADD-C, and SUB-C imply that the actual numbers 15, 18, and 7 are used, rather then the numbers in memory locations 15, 18, and 7.
Question 8: The CPU of the "xComputer" contains two different registers that "count": the COUNT register and the Program Counter register. Discuss the purpose of each of these registers and explain what type of "counting" each one does.
Answer: Both registers "count" the steps being performed by the CPU, but they count steps on different levels. The PC counts off the instructions from the program stored in main memory as they are fetched one at a time in to the CPU and executed. Fetching and executing just one of these program instructions takes the CPU several individual operations, and it is these lower level steps that are counted off by the COUNT register. Thus, the COUNT register counts from zero up to five or more each time the PC changes by one.
Note: These registers do not count in the sense of keeping track of how many steps have been performed. Rather, it is the changing of the values stored in these registers that actually causes the steps to be performed. Thus, it is more correct to say that they "count off" the steps, rather than merely "count" them.
Question 9: A computer consisting of a CPU and main memory has no moving parts, so what does it mean to say that it is a "machine" and that it operates "mechanically"?
Answer: The term "mechanical" as it is used here means "following definite rules without thinking and without regard to the meaning of the operations that are performed." A computer is mechanical in this larger sense, even though, unlike most of the things we call machines, it has no moving parts.
Question 10: A "black box" has two aspects: an interface and an implementation. Explain what is meant by each of these terms, and give an example.
Answer: The interface of a black box is the "view from outside the box." Knowing the interface means knowing what purpose the black box server and knowing how to use the box. The implementation is "what's inside the box." You don't need to know the implementation in order to understand how to use the box. For example, you understand the interface of an ALU if you know how to use it to add numbers, subtract them, etc. You don't need to know anything about what is going on inside the box if all you want to do is use it to perform such operations. (On the other hand, you do need to work with the inside of the black box if your object is to build the box or to understand how it works.)
[by David Eck]