CPSC 120, Fall 2002
First Test, September 25
This is the first test from CPSC 120:
Principles of Computer Science, Fall 2002.
Answers given here for
essay-type questions are sample answers only.
Other answers can also
receive full credit.
Question 1:
Define each of the following terms, as they relate to this course:
a) transistor
b) ASCII
c) machine language
Answer:
a) A transistor is an electronic switch that is used as the fundamental building block of computers. It has an input wire, an output wire, and a control wire. Turning the control wire on and off switches the flow of information from input to output on and off.
b) ASCII (American Standard Code for Information Interchange) is a standard system for assigning 8-bit binary code numbers to characters so that they can be stored and manipulated as data in a computer.
c) Machine language is a programming language consisting of instructions that are encoded as binary numbers which can be executed directly by the hardware of a computer. Each type of computer has its own machine language. Programs written in other languages must be translated into machine language before they can be executed by the computer.
Question 2: Write the Boolean algebra expression that describes the output of the following circuit:
Answer: (A AND (NOT B)) OR (NOT (B AND C))
Question 3: Draw the logic circuit whose output is described by the expression:
(A AND (B OR C)) AND (NOT (A AND B AND (NOT C)))
Answer: Here is the circuit, built using the xLogicCircuits applet:
Question 4: Suppose that A is true, B is false, and C is true. Determine whether each of the following Boolean expressions is true or false:
a) A AND (B OR C)
a) NOT (A AND B)
a) ((NOT A) OR B) OR (B AND C)
Answer: (a) is true, (b) is true, and (c) is false.
Calculations:
A AND (B OR C) = true AND (false OR true)
= true AND true
= true
NOT (A AND B) = NOT (true AND false)
= NOT (false)
= true
((NOT A) OR B) OR (B AND C) = ((NOT true) OR false) OR (false AND true)
= (false OR false) OR (false AND true)
= (false) OR (false)
= false
Question 5: The base-ten number 203 can be expressed as a sum of powers of two as
27 + 26 + 23 + 21 + 20
What is the corresponding base-two (binary) number?
Answer: 11001011
Explanation: Every power of two corresponds to a position in a binary number. The positions are numbered from right to left, starting from zero. Every power of two that appears in the sum (0, 1, 3, 6, and 7) corresponds to a one in the binary number. So, the answer has 1's in positions 0, 1, 3, 6, and 7.
Question 6: Add the following binary numbers:
1 1 0 1 1 0 0 1 0
+ 1 1 0 1 1 0 1 1
---------------------
Answer: 1010001101
Question 7: Registers play important roles in the Central Processing Unit of a computer. Define the term register, explain why they are essential to the fetch-and-execute cycle, and give some examples of specific roles that registers play in the xComputer model computer.
Answer: The term "register" refers to any memory circuit that is part of the CPU of a computer. Generally, a register is designed to hold a single binary number with some specified number of bits. For example, in xComputer, the AC holds a 16-bit number, and the ADDR holds a 10-bit number.
A fetch-and-execute cycle gets one instruction from memory and executes it. Each step in the fetch-and-execute cycle is very simple and can be performed merely by turning control wires on and off. Registers are essential because they make it possible to remember the result of one step so that it can be used in later steps. Each step performs a simple operation such as copying a number from one register to another or storing the result of a computation in a register or moving a number between memory and a register. Once data is put into a register, it will stay there until a new value is explicitely loaded, and the value in the register will remain available on its output wires ready to be used by other components.
In the xComputer, for example, the output wires of the X and Y registers are attached to the inputs of the ALU. Putting values into these registers sets things up so that those values can be processed by the ALU in a later step. The program counter keeps track of which instruction in the program is next in line to be executed, so that that instruction can be fetched in the next fetch-and-execute cycle. Without some kind of memory circuit, there would be no way for the CPU to keep track of this information.
Question 8: (a) Consider the following short program for the xComputer model computer. Next to each instruction, briefly explain the meaning of that instruction:
LOD-C 1
STO 10
ADD 10
JMP 1
(b) Describe what the computer will do when it executes this program.
Answer:
LOD-C 1 -- Puts the actual number 1 into the accumulator.
STO 10 -- Copies the number in the accumulator into
memory location number 10.
ADD 10 -- Adds whatever number is in location 10 to
the number in the accumulator and puts the
answer in the accumulator
JMP 1 -- Puts the number 1 into the program counter.
The computer will continue execution of the
program from location 1 (that is, from the
STO 10 instruction in this example).
When the program begins, the number 1 is put into location 10. (It is first put into the AC and then copied into location 10.) The ADD 10 instruction adds this same number to the AC. Since the AC and location 10 contain the same number, the number in the AC is doubled. Because of the JMP 1 instruction, the computer repeats the steps STO 10, ADD 10 over and over. Each time they are executed, the number in location 10 is doubled. The values are 1, 2, 4, 8, 16,.... So, the computer is computing powers of 2.
Question 9: Data is represented in computers in the form of binary numbers. Suppose that a binary number such as 10111001001001000111001011001100 is stored in a computer. Can you tell what this data represents? What does your answer illustrate about data representation?
Answer: There is no way to tell what this data represents, without knowing more about the context. Binary numbers do not have a fixed meaning. The same binary number can be used to represent many different kinds of data, depending on how that data is encoded. This 32-bit number might represent four ASCII characters, two Unicode characters, a single real number, the colors of a few pixels in some image, a date, a bit of music, and so on. This illustrates that binary numbers are symbols, which do not have a fixed, intrinsic meaning. They get their meaning from context and from the particular encoding that is used.
Question 10: Some of the input wires to a Main Memory (or "RAM") are called address wires. Explain the purpose of the address wires and how they are used.
Answer: Main Memory consists of a large number of "locations." Each location is a memory circuit that can hold a binary number. These locations are numbered 0, 1, 2, 3,..., and the number of a location is called its "address." At a given time, only one location in memory can be used for storing and reading data. The purpose of the address wires is to tell main memory which location it should make available. The pattern of ON/OFF values of the address wires can be interpreted as a binary number. This number is the address of the desired location. The contents of that location are visible on the memory's data-out wires. If a value is loaded into memory, the value goes into the location whose address is given by the number on the address wires.
Question 11: In the xComputer model computer, the first three steps of the fetch-and-execute cycle are always the same, no matter which machine language instruction is being executed in that cycle. Explain the purpose of each of these steps. Why is it done? What role does it play in the fetch-and-execute cycle?
Step 1. Load Address form Program Counter
Step 2. Load Instruction Register from Memory
Step 3. Increment Program Counter
Answer:
Step 1. Load Address form Program Counter: The number in the PC is copied into the ADDR. The PC contains the address of the instruction that is supposed to be executed in this cycle. This number must be put on the address wires of the main memory to make that instruction accessible. The output wires of the ADDR register are attached to the memory's address wires, so putting a number in ADDR effectively tells the memory to use that address.
Step 2. Load Instruction Register from Memory: Copies a number from the memory's data-out wires into the IR. Because the ADDR register was set up in Step 1, the number that is copied is the instruction that has to be executed in this cycle.
Step 3. Increment Program Counter: Adds 1 to the PC. When the next cycle begins, the PC must contain the address of the instruction to be executed in that cycle. Ordinarily, that will be the instruction that comes after the current instruction. So, the PC should be incremented by 1 to get ready for the next fetch-and-execute cycle. (However, note that the value in the PC might change again in this cycle, if the instruction that is being executed is a jump instruction.)
Question 12: One of the major themes of this course is structured complexity. Explain what is meant by structured complexity and how it differs from "mere complication." Include some examples in your discussion, and explain why structure is so important to the design and understanding of complex systems.
Answer: Something that is "merely complicated" can be complex in the sense that it has a lot of detail, but if there is no structure there is no way to understand it in a meaningful way. A jigsaw puzzle, for example, has a lot of detail but not much structure. Either all the details are in place or they aren't. There is no theory that can guide you in putting the puzzle together.
Structured complexity, on the other hand, is built up in a hierarchical fashion, level by level. Complex components are built from simpler components, which are themselves built of even simpler components. Once a component has been created, it can be used as a "black box" in more complex structures. This allows you to concentrate on designing or understanding one level at a time. Each level can be easy to understand, but by building level on level, structures of extraordinary complexity can arise.
The most complex things found in nature are biological systems, and their complexity is structured in this sense. Organisms are made out of organs which are made from tissues which are made from cells which are themselves complex systems. Computers imitate this hierarchical structure. We say that computers can be constructed from transistors, but a computer is not just a jumble of transistors assembled individually like the pieces of a jigsaw puzzle. Transistors are used to build logic gates. Logic gates are used to build simple circuits such as one-bit adders and one-bit memories. These circuits are combined to build multi-bit adders and registers. These are combined to make the ALU, CPU, and Main Memory.