CPSC 100, Spring 1997:
Answers to Quiz #1

This is the first quiz 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: This course is supposed to be about "computers and computing." Explain what is meant by computation.

Answer: Computation is the mechanical manipulation of symbols. That is, it consists of "mindlessly" following unambiguous rules, without any consideration of the meaning of the rules or of the symbols that are being manipulated.

Note: Although the results of a computation can be meaningful, the process of computation doesn't depend on the meaning. The fact that computation is meaningless in itself explains why it can be done by a machine. The fact that computations can have meaningful results is what makes computing machines so useful.

Question 2: In ASCII, each character is represented by an 8-bit binary number, and there are 256 such possible codes. In a newer text-encoding scheme called Unicode, each character is represented by a 16-bit binary number. How many different possible 16-bit codes are there, and why?

Answer: There are 216 possible 16-bit codes. (That's 2 raised to the 16-th power, which is 65536.) Each bit doubles the number of possibilities. The number of possibilites with 16 bits is 2 multiplied by itself 16 times. (Similarly, an 8-bit code gives 256 possibilities because 256 is 2 raised to the eigth power.)

Question 3: What is a CPU, and what role does a CPU play in a computer?

Answer: The CPU, or Central Processing Unit, is the active part of the computer which actually executes programs. To execute a machine language program that is stored in main memory, the CPU repeatedly fetches an instruction from memory and then executes that instruction.

Question 4: Programs can be written in high-level language or in machine language. What is the difference between these two types of programming languages?

Answer: Machine language consists of instructions encoded as binary numbers. These machine language instructions can be directly executed by the computer's CPU. A high-level language, on the other hand, is easier for humans to write or read, but programs written in a high-level language cannot be executed directly by the computer. They must first be translated into the machine language that the computer understands.

Note: In the category of "most common mistakes": The term machine language is defined to mean the programming language that can be executed directly by the hardware of a computer. It does not refer to ASCII code. ASCII code is used to encode data; machine language is used for programs. It would be perfectly reasonable for ASCII code to be called a machine language, but it just isn't; the term "machine language" is a technical term which is defined to have another meaning entirely.

Question 5: Structured complexity refers to the fact that very simple components can be combined to make structures of great complexity, which can nevertheless be understood because of the way they are organized. Two of the "very simple components" that we have talked about are bits and transistors. What kinds of structures can be built from these components? Give some specific examples.

Answer: Bits can be combined to make data structures. For example, eight bits can be combined to make an ASCII code that represents some character. A number of ASCII codes can be combined to make a word, and so on. Transistors can be combined to make circuits (including an entire computer, which is just a large circuit). For example, transistors can be combined to make AND, OR, and NOT gates.

David Eck, 13 April 1997