This page contains eight quizzes that were given in Computer Science 100 when I taught it in the Spring term of 1994. Answers to each question are included, and in some cases notes on the answers. Most of these notes were written to clear up common student mispercetions that were apparent in their answers to the quiz questions.
The quizzes covered, more or less, the first eight chapters from The Most Complex Machine as well as computer labs based on the same material. (Sorry that this is in plain text format, but that is how I wrote it up at the time.)
Here are some links to the individual quizzes:
1. Q: Write down the binary representations for the numbers from
zero to twelve, starting 0, 1, 10, ...
A: Counting in base 2 from 0 to 12.
0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100
2. Q: What is ASCII code
A: ASCII code is a particular encoding used to represent text. Each
possible character is assigned an eight-bit binary number as its
code. (Characters are things like letters, punctuation, tabs,
carriage returns, ...) It is used by most computers to store and
manipulate character data.
NOTE: ASCII code is not "machine language". Machine language
is a technical term refering to _instructions_ that are
encoded in a such a way that they can be directly executed
by the CPU. In some sense, the CPU "understands" machine
language, but it does not understand ASCII code. It can
manipulate ASCII code as _data_, but only by executing a
program that tells it what to do with the ASCII encoded
characters. (ASCII code might have been called a "machine
language" if the term "machine language" weren't already taken
to mean something else.)
3. Q: What is meant by the fetch-and-execute cycle?
A: The fetch-and-execute cycle is what the CPU does to execute a
program: It gets a single instruction from memory and carries
out that instruction, and it repeats this cycle over and over.
4. Q: How is the memory of a computer structured and what is it
used for?
A: The computer's memory is structured as a sequence of numbered
locations. Each location holds a binary number of some fixed
size. (In most modern computers, each location holds an 8-bit
number, but in general, the number of bits could be anything.)
The memory holds program instructions and data to be used by
the CPU.
NOTE: a) The term "memory" in English is ambiguous, because it
can refer to both the place where information is stored
and to the information itself. ("My memory is getting
bad" vs. "I have a lot of nice memories of Spring Break".)
In computer's, "memory" always refer to the _place_
where information is stored. We say that the memory
"holds" or "stores" information.
b) Here is one of the ways in which our simple picture
of a computer is wrong: I have given you the false impression
that each location in memory can hold a complete instruction in a
program, but this is not generally true. It simply takes
more than eight bits to encode an instruction. So, an
instruction is in general spread out over several locations.
The same is true for data. An "integer" in most computers
is stored in two or four consecutive locations rather than
just one, for example. (The simple model computer we will
look at in Chapter 3 has 16 bits per location and does in
fact use only one location for an instruction.)
5. Q: The textbook talks a lot about "structured complexity". What
is mean by structured complexity and how does it differ from
mere complication?
A: Our minds are not capable of grasping large amounts of detail unless
it has some structure. You would find it almost impossible to memorize
a random sequence of a thousand of characters. If the characters form
form words in a poem or song, it is easier.
Structured complexity refers to the fact that complex complex
objects/data/programs/etc can be built up level-by-level from simple
components. The chunking that goes on at each level is simple enough
to be comprehensible, but you end up with something that is really
very complex.
1. Q: Add the following two binary numbers and explain briedly the
procedure you used to do so.
A: To add binary numbers, start at the right and work to the left,
adding one column in the sum at each step. When the sum in a
column is two or three (that is, 10 or 11 in binary), then there
is a carry into the next column. In this example:
1 1 1 1 1 1
1 0 1 1 0 0 1 0 1
+ 1 1 0 1 0 1 1 1
-------------------
1 0 0 0 1 1 1 1 0 0
The ones in the top row are carries.
2. Q: Draw a circuit that computes the value of the Boolean expression:
(A AND (NOT B)) OR (NOT (B AND C))
A: Using the words AND, OR and NOT instead of drawing the gates,
the circuit for (A and (not B)) or (not (B and C)) looks
something like this:
A ---------+__
__ AND--------+_____
B --+-NOT--+ _____OR-------
|_________ |
__ AND---NOT--+
|
C----------+
For a description of the method used to build the circuit,
see the answer to lab question 1, below.
3. Q: Consider the following circuit. Assume that the inputs, A, B, and
C are set to ON, ON, and OFF, respectively, as shown. Label the
output of each gate in the circuit to show whether it is ON or OFF.
The circuit looked something like this:
A --------|
ON | AND --------| NOT ------------------------|
,-| | OR --------
B -----|-------------------------. ,|
ON \ \__ | /
`-| | AND -------'
| OR ---------| NOT -------|
C ---------|
OFF
A: The AND gate at upper left has two inputs that are ON; its output is ON.
The OR gate at the lower left has one input ON and one OFF; it is ON.
Each NOT gate has input ON; the output of each NOT gate is OFF.
The AND gate at the lower right has one inputs OFF and one ON; it is OFF.
The OR gate at the right has both inputs OFF, it is OFF.
4. Q: Write down an expression o fBoolean algebra that describes the
output of he circuit in the preceding problem in terms of its
inputs, A, B, and C.
A: The expression that serves as a "blueprint" for the circuit in
problem 3 is:
(not (A and B)) or ((not (B or C)) and B)
This expression can most easily be built up from "left to right"
by labeling the output of EACH gate in the circuit. The output
of a gate is a simple combination of its inputs. For example,
if the inputs of an AND gate are "B" and "not (B or C)", then
the output of that gate is "B and (not (B or C))". So, the method
used in this problem is really not very different from the one
used in problem 3! (That is, build up the final answer one gate
at a time.)
5. Q: What is a full adder circuit? (What computation does it perform?
What inputs and outputs does it have?)
A: A full adder is a circuit with three input wires and two output
wires. The three inputs represent three bits to be added. The
sum of these bits is a two-bit number represented by the output
of the circuit. Thus, the circuit does computations of the
form: 0 + 1 + 0 = 01, 0 + 1 + 1 = 10, and 1 + 1 + 1 = 11.
A 16-bit adder is made of 16 full adders. Each full adder does
one column in the sum.
1. Q: A black box has an interface and an implementation. Explain what is
meant here by the terms interface and implementation, and give examples.
A: A black box divides the world into two parts, the part inside the
box and the part outside. These communicate through the box's interface,
which defines what inputs it takes and what outputs it produces.
The inside of the box, the part that actually takes the inputs and
produces the outputs, is called the implementation. Subcircuits
of the type used in xLogicCircuits are a good example: A circuit can
be created and saved in a file. Later it can be used as a black box
inside another circuit. Another example is a car, which is used by
a driver as a black box: When you step on the gas [input], the
car goes [output]; the stuff "under the hood" that makes it go is
the implementation.
NOTE: If you say "you don't have to understand how a black box
works (inside) in order to use it," that's true, but it
is only part of the story. As "conceptual tools",
black boxes divide problems into almost-independent parts
that interact in fairly simple ways. This is sometimes
called "modularity", a concept that comes up again in
Chapter 7 with regard to programming. Modularity makes
complex systems easier to design. It also makes them
easier to "fix", since you can change the implementation
of a black box as long as you don't change the way it
looks "from the outside".
2. Q: What is the purpose of the Control circuit, and how does it carry out
that purpose?
A: Our model computer was designed so that all the basic operations
inside the CPU can be accomplished by turning control wires on and
off. Each fetch-and-execute cycle is just a sequence of these basic
operations. The purpose of the Control circuit is to execute machine
language programs by controlling the execution of fetch-and-execute
cycles. It does this by turning control wires on and off in the
right sequence. (It's inputs contain all the information necessary
to determine which wires need to be on; the Control circuit responds
to these inputs by turning on those wires.)
3. Q: Explain the purpose of the address register, ADDR, and give a specific
example of how it is used by the CPU.
A: The address register is attached to the Address wires of the main
memory. The only way the CPU can tell the main memory which location
it wants to use is to put the location number into the address register.
For example, when the CPU wants to store a number into memory, it first
puts the number of the location where it is to be stored into the
address register. Only then can it store the number.
NOTE: The PC and the address register play very different roles.
The PC holds the location in memory of the next instruction
in the program. In order to get that instruction out of
memory, the CPU must first put the correct location into
the ADDR register. It does this at the beginning of each
fetch-and-execute cycle by turning on the Load-ADDR-from-PC
control wire. But ADDR is used at other times as well,
such as whenever the CPU needs to store a number in memory.
In the meantime, while the ADDR is being used in all kinds of
ways, it is the job of the PC to remember the number of the
next instruction in the program.
4. Q: What role does the COUNT register play in the computations performed by
the CPU.
A: The COUNT register counts off the steps in each fetch-and-execute
cycle. Each cycle takes several little steps. When COUNT = 1, the
first step is performed; when COUNT = 2, the second, and so on. At
the end of one cycle, the value of COUNT is reset to zero so that the
next cycle can begin.
NOTE: You shouldn't confuse the type of counting that COUNT does
with the counting done by the PC. These two operate on
different "levels". PC counts off the instructions in a
program that is being executed. But on the lower, CPU
level, the execution of one instruction takes several
steps. These small, low-level steps that carry out one
instruction are counted off by the COUNT register. So,
the COUNT register counts through a whole cycle as the
PC changes just once.
5. Q: What is meant by an addressing mode.
A: An instruction in xComputer's machine language is represented
by a sixteen-bit binary number. The first six bits encode the
instruction, such as ADD or L0D-C or HLT. The remaining ten are
data for the instruction. The addressing mode refers to the way
in which these data bits are interpreted. In constant addressing,
the data bits specify the actual number to be used by the instruction;
in direct addressing, they specify a memory location; in indirect
addressing, they also specify a memory location, but that location
just holds a "pointer" to another memory location. ["Pointer" just
means the address of theat memory location.]
1. Q: What is meant by computational universality?
A: A machine is said to be "computationally universal" if it can do
any calculation that can be done by any computer whatsoever. Because
of limitations on memory size, there are no truly universal machines,
but if we imagine giving a computer as much memory as it needs,
then every computer is computationally universal. [We might say that
this is what distnguishes a computer from a simpler computing device,
such as an adding machine.]
2. Q: Ignoring limitations on memory size, any computer can be programmed to
simulate any other computer. What is the significance of this fact?
A: This is the _evidence_ we have for the universality of every computer:
If computer A can simulate anything computer B can do, then computer A
is at least as powerful as computer B. But by the same reasoning,
B is at least as powerful as A, so in fact they are equally powerful.
[Along the same lines, if we want to show that a particular Turing
machine is universal, one way to do so is to show that it can
similate a computer.]
3. Q: Explain in words the basic step-by-step operation of a Turing machine.
A: Your explanation should include mention of its tape, its state and
its rules.
A computation performed by a Turing machine is a sequence of
very simple individual steps. Its action during each step is
determined entirely by its current state and by the symbol in the
current square on the tape. For each combination of state and
symbol it has a rule that specifies its action. That action has
three parts: it writes a [possibly] new symbol in the square,
moves one square to the left or right on the tape, and [possibly]
changes to a new state.
4. Q: Consider the Turing machine whose rule table is given on the
attached sheet.
a) Suppose this machine is started in state 0 on the following tape on
the square containing the z. Show what the tape will contain when the
machine halts, and indicate where the machine will be when it halts.
The tape contains: ...##z#$0#yy$x#$###...
(Here, # represents a blank square.)
b) Explain in words ehat this machine will do whan it is started on
any tape.
The rule table looks like this:
Current Current New
State Symbol Write Move State
------- ------- ------- ------ -------
0 # # R 0
0 o o R 0
0 i i R 0
0 x x R 0
0 y y R 0
0 z z R 0
0 $ $ R 1
1 # # R 1
1 0 # R 1
1 i # R 1
1 x # R 1
1 y # R 1
1 z # R 1
1 $ $ L h
A: (a) This problem can be done by blindly following the rules
in the table, just as the Turing machine itself does. It starts on
a z in state 0. The rule for this state and symbol tells it to
leave the z there, move right, and stay in state 0. It then sees
a blank while in state 0, and the rule tells it to leave the blank,
move right and stay in state 0. Now, it sees a $ while in state 0;
It leaves the $ there, moves right and changes to state 1. As you
continue in this way, you will see that the machine continues to
move to the right in state 1 and erases symbols as it goes, until
it gets to the next $. It than moves left and halts. In the
end, the tape contains: ...##z#$####$x#$###... and the machine
is on the # to the left of the second $.
(b) This question is asking for the "purpose" of the machine. On a
high level, we could say that this machine "erases the tape between
between the two $'s to the right of its starting location on the tape."
On a slightly lower level, we could say that the machine "moves right
without chaning anything until it comes to a $. It then changes to
state 1 and continues to move right, erasing all symbols, until it
comes to another $." [Note that if there are no $'s, or only one $,
to the right of the machine's starting location on the tape, then
it will continue to compute forever.]
1. Q: By the end of the 1940s, the first general-purpose, electronic
stored-program computers had been created. Briefly explain the
meaning of each of the following adjectives as used here:
A: (1) general-purpose
This means that the computer can be programmed to
do any computation. It is _universal_. It is not limited
to one specific task.
(2) electronic
The computer is constructed from fast vacuum tubes
(or, later, transisters), as opposed to slow relays or even
slower rods and gears. [NOTE: An "electronic" device has
NO MOVING PARTS, unless you count the electrons themselves.
A relay runs on electricity, but it has a metal contact that
moves back and forth between two possible positions. It takes
time to move a piece of metal, so even the fastest relays are
slow compared to electronic devices. It takes much less time
to turn a flow of current on and off. Note that relays are
"electric" but not "electronic".]
(3) stored-program
The computer executes programs that are stored as information
in its memory. This makes it possible to easily change a
program without physically modifying the computer. [NOTE: It
is not the fact that the computer can "remember" a program
that is important here; a deck of punched cards can "remember"
a program forever. What is important is that the computer can
switch from one task to a completely different task at the
click of a mouse.]
2. Q: What role did J. Presper Eckert and John Mauchly play in the
history of computers?
A: Eckert and Mauchly designed and built the ENAIC, the first
fully programmable electronic computer. They also came up
the idea of storing programs in the computer's memory.
(They did not, however, complete the first machine based
on this idea. Their design--for the EDSAC--was first,
but the British got their machine built first.)
3. Q: What are device drivers, and why are they needed?
A: A device driver is software--a collection of subroutines
and interrupts--that the CPU can execute in order to
communicate with and control a specific hardware device,
such as a keyboard, disk drive or scanner. Device drivers
are necessary since the only thing that the COU can do is
execute programs; if it is to have any communication with
the world at all, it must do so by executing programs.
4. Q: A bus is a component found in many real computer
systems. What is meant by a ``bus'' in tontext?
A: A bus is a set of wires connecting the CPU to a number of
other devices. The important point is that several different
devices can "plug into" the bus, so that the CPU doesn't have
to be built with all possible connections for all possible
devices already built-in. Busses can carry addresses, data
and control signals.
5. Q: One of the potential problems associated with the introduction
of computers into the workplace is deskilling. What is meant
by "deskilling"?
A: Deskilling is the replacement of interesting, high-paying,
high-skill jobs with boring, low-paying, low-skill jobs.
It is thought that this could happen if a lot of the
"expertise" necessary to do the job can be programmed int
a computer. [NOTE: This is not the same problem as
unemployment caused by automation. I could imagine 5
happy, highly skilled, $100,000-a-year engineers begin
replaced by 10 miserable, $15,000-a-year computer
attendants: more jobs, but "deskilled" jobs.]
1. Q: Write a sequence of xTurtle commands that will draw two separate
long, parallel lines.
A: There are a lot of ways to do this. Here is one:
forward(10)
PenUp
turn(90)
forwrd(1)
turn(90)
PenDown
forward(10)
Here is another:
Move(10,0)
PenUp
Move(0,1)
PenDown
Move(-10,0)
2. Q: Draw the figure that would be produced by the following xTurtle program:
DECLARE s A: This draws five line segments connected
s := 5 by right-angle turns. Each segment is
LOOP one unit shorter than the previous one.
forward(s) The picture is something like this:
turn(-90)
s := s - 1 ---------------
EXIT IF s = 0 |
END LOOP --- |
| |
| |
---------
(Note that one way to attack a problem like this one
is just to "play computer" and follow the instructions
step-by-step the way the computer would. Part of doing
this is keeping track of the values of any variables.)
3. Q: Explain what is meant by the terms syntax and semantics, and give
examples.
A: Syntax refers to grammatical structure, while semantics
refers to meaning. The syntax of a language is the set
of rules that determine what is grammitcally legal in that
language. The semantics of a language is the set of rules
that determine what something means in that language.
For example, the syntax of a LOOP statement in xTurtle
says that such a statement consists of the word LOOP,
followed by a sequence of statemenst, followed by the
words END LOOP. The semantics of a LOOP statement
says that the computer is to execute the statements
over and over (until an EXIT statement terminates the
loop). [Note: The terms syntax and semantics are also
used to refer to individual sentences or programs.
For example, the syntax of the sentence "John walks quickly"
is that it consists of a noun, a verb and an adverb. It's
semantics is the idea conveyed by the sentence.]
4. Q: Explain briefly what is meant by preconditions and postconditions
and how they can be used in writing programs.
A: A precondition is a something that has to be true at a given
point during the execution of a program, for the rest of the
program to work correctly. A postcondition is something
that is actually true at a given point after some part of
a program has been executed. When writing a program, it
can be useful to think in terms of postconditions and
preconditions: Looking at any point in the program, you can
ask, do the postconditions [that we know are true because of
what has already been done in the program] match up with
the preconditions [that have to be true for the rest of the
program to do what you want it to do]? If not, you know
you have to insert some instructions to make the preconditions
true.
As a simple example, a precondition for the statement
"x := sqrt(y)" to succeed without crashing is that "y >= 0",
since the square root of a negative number is not allowed.
This means that _before_ this statement in a program, you
should either make sure you know that y>=0 for some reason,
or you should test that this is true.
[Note that preconditions and postconditions are _not_
parts of a program! They are not "commands". They are
conditions such as "x is > 0" or "there is a square
on the screen". A condition is something that can be either
true or false. A precondition is a condition that you want
to make sure will be true when the program is being executed.]
5. Q: Exactly what sequence of steps might the computer go through
to execute the assignment statement x := y + 3.
A: The computer would have to retrieve the value stored in
whatever memory location corresponds to the variable y,
add 3 to that value, and then store the result into
the memory location that corresponds to the variable x.
[Note: Some people seemed to take this question to mean,
"What sequence of statements would the computer have
to execute BEFORE this one, in order for this statement
to make sense in a program." That's not what the question
asks, but I gave partial credit for it.)
1. Q: "Parameters" come in two types: actual parameters and dummy parameters.
(Dummy parameters are also called formal parameters.) What are
parameters? What is the difference between acutal parameters and
dummy parameters? Give Examples.
A: Parameters are used for communication between a subroutine and
the rest of the program. They are part of the interface of the
"black box" that the subroutine represents. A dummy parameter is
a name used in the _definition_ of a subroutine to represent the
actual parameter that will be passed to the subroutine when it is
called. For example, in the simple subroutine
SUB angle(side,degrees)
forward(side)
turn(degrees)
forward(side)
END SUB
"side" and "degrees" are dummy parameters. When the subroutine
is called, the actual values provided for these dummy parameters
are called actual parameters. For example, in
angle(3,30)
angle(length,(measure + 1)/3)
The "3", "30", "length" and "(measure + 1)/3" are all actual
parameters. (For the second command to be legal, of course,
length and measure must be DECLAREd as variables earlier in
the program.)
2. Q: Discuss the software life cycle. List some of the stages in the
cycle and explain what is meant by each.
A: Programs of moderate to large size have a life cycle that
starts with the specification of a problem to be solved,
continues through the development of a program to solve that
problem and ends, perhaps many years later, when the program
finally becomes obsolete. We can identify certain stages
in this life cycle:
-- specification: The problem is stated in clear,
unambiguous language.
-- analysis and design: The problem is analyzed to see
how it can be solved by a computer, and
the major parts of the solution are
designed.
-- coding: The solution is translated into a program
written in computer language
-- testing: The program is run under realistic conditions
to uncover any problems or "bugs"
-- maintenance: After the program is released, work continues
to keep it up-to-date and to fix any newly
discovered bugs.
3. Q: (a) Write an xTurtle subroutien that draws a "T" shape, as was shown on
the blackboard. Use only turn, forward and backward commands in the
definition of the subroutine. The turtle should return to its initial
position and heading at the end of the subroutine.
(b) Use the subroutine you have written (along with some other xTrutle
commands) to draw the second figure that was shown on the blackboard.
(The "T" looked something like this:
|
---------------|
|
It was labeled as 5 units long and 2 units high.)
A: (a) Here is one possible solution:
SUB DrawT { DrawT is the _name_ of the subroutine }
forward(5)
turn(90)
forward(1)
back(2) { At this point, the figure has been drawn; }
forward (1) { now return turtle to its starting point }
turn(-90)
back(5)
END SUB
(b) Here are three possible soultions. One is just a simple sequence
of commands, while the other two use loops. The name used to
call the subroutine here should be whatever name was used
for the subroutien in part (a).
{1} DrawT { Tells the computer to execute the subroutine. }
turn(45) { rotate turtle 45 degrees }
DrawT
turn(45)
DrawT
turn(45)
DrawT
turn(45)
DrawT
{2} DECLARE count
count := 0 { no T's drawn yet }
LOOP
DrawT { draw a T }
turn(45)
count := count + 1 { count the T }
EXIT if count = 5 { end if 5 T's have been drawn }
END LOOP
{3} LOOP
DrawT
EXIT IF heading = 180
turn(45)
END LOOP
1. Q: Pick any two of the following important computer languages and explain
the importance of each of the two languages you choose in the evolution
of computer languages: FORTRAN, ALGOL-60, COBOL, Pascal, Ada and C++.
A: FORTRAN : The first high-level programming language.
ALGOL-60 : The language that influenced almost all languages
developed after 1960. It introduced loops and if
statements as _structures_ (where FORTRAN used jumps),
recursive subroutines, and the concept of global and
local variables. The report on ALGOL-60 also introduced
BNF.
COBOL : Whereas FORTRAN and ALGOL-60 were designed mainly for
numerical scientific computing, COBOL was designed to
support the kind of data processing used in business and
government. COBOL introduced records and files, and so was
an important step in the recognition of the importance of
data structures.
Pascal : Introduced extensive data structuring capabilities; widely
used for teaching programming.
Ada : A vast extension of Pascal, incorporating ideas on modularity,
abstract data types, and software reusability.
C++ : An object-oriented language, one of the most widely used today
by professional programmers.
2. Q: Discuss the analogy between "structured complexity" as seen in data
structures and as seen in subroutines. Give specific examples.
A: Structured complexity refers to the construction of a complex
system as a sequence of levels, where details on one level are
chunked together into black boxes to be used as components
on higher levels. Data structures and subroutines are both
used in constucting complex systems is this way; the difference
is that data structures deal with structures of data while
subroutines deal with structures of instructions.
Thus, once a data type has been defined, it can be used
to build more complicated types. For example, a "date" type
might be defined to consist of a month, a day and a year.
Such a date type might be used to represent a student's
date of birth in a "student record" type. From this in
turn, an array of student records could be constructed.
Similarly, once a subroutine for drawing squares is written,
it could be used in another subroutine, such as a subroutine
that draws a house. A house-drawing subroutine could be used
in turn to draw a village consisting of several houses.
3. Q: Suppose that a program needs to store information about 30 students.
For each student, the student's name and three test grades must be
stored. Describe a data type, constructed using arrays and records,
that could be used to store all this information.
A: Top-down Approach. Since there are 30 students, and we have the
same set of data items for each student, we should make an array
with 30 items, where each item contains all the data for one
particular student. Each item in the array would be a record
containing a string (the student's name) and three real numbers
(the student's grades on the tests).
Bottom-up Approach: We have at least two different types of
data items for each student, so we should group the data for
a given student--name and three test grades--into a record.
To take into account that there are 30 students, we should
make an array of 30 such records.
[Note: In Pascal, the relevant data types could be defined a
TYPE StudentData = RECORD
name: string;
test1: real;
test2: real;
test3: real;
END;
StudentList = ARRAY[1..30] OF StudentData;
Alternatively, the three test grades might be stored in
an array before they are combined with the name into a
record. And maybe the name could be split into first name
and last name. That is:
TYPE GradeArray = ARRAY[1..3] of real;
StudentData = RECORD
LastName: string;
FirstName: string;
TestGrades: GradeArray;
END;
StudentList = ARRAY[1..30] OF StudentData;
There are many ways to build a data structure, just as
there are many ways to write a program. ]