This is Quiz #1 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: Computation can be defined as the "mechanical
manipulaton of symbols."
(a) Explain what is meant by the word "symbol" in this definition.
(b) What does it mean to say that the symbol manipulation is
"mechanical"?
Answer: (a) A symbol is something that has no meaning in itself but that can be seen as representing or standing for some external meaning. For example, some 0's and 1's stored inside a computer might be a symbol for the number "17" or for the height of Mount Everest. (b) The symbols are manipulated according to definite, unambiguous "rules" (that is, "instructions") without any thought and without any regard to their external meanings.
Note: Symbols are very common, and not just in computers and computations. Words are symbols. The U.S. flag is a symbol. The position of the hands on a clock is a symbol. Symbols get their meanings from convention and from circumstance.
Question 2: What is the difference between a "high-level language" and a "machine language"?
Answer: A machine language consists of instructions encoded as binary numbers that can be directly executed by the CPU. It is essentially unreadable by humans. A high-level language, which is a little closer to English, can be used by people to write programs, but those programs must be translated into machine language before they can be executed by a computer.
Note: The terms "machine language" and "high-level language" refer to programming languages, consisting of instructions that a computer can execute. ASCII code is not, by definition, a "machine language", even though it is arguably a language used by machines. "Machine language" is a technical term, which is used in this course with its technical definition.
Question 3: Explain why "loops and decisions" are necessary for writing complex programs, and explain briefly what they have to do with "jump instructions" in machine language.
Answer: If a program could only run through a list of instructions from beginning to end, it could only perform fairly simple tasks (since it would run out of instructions very quickly). Loops let the computer go back and repeat a set of instructions over and over. A loop is implemented by a jump instruction at the end of the loop that tells the computer to jump back to the beginning of the loop. Decisions allow the computer to base its next action on whether or not some condition holds. They can be used, for example, to jump out of a loop when it has been executed enough times.
Note: This is the answer that most people gave (obviously remembering my discussion in class). However, a much better answer---more in line with what was in the reading---would be: In order to be written and understood by people, complex programs must exhibit structured complexity. Loops and decisions, along with subroutines, help to provide that structure. A loop is a "chunk" of instructions for performing some task over and over. A decision is a way of selecting between two possible tasks. On the level of machine language, where loops and decisions don't exist explicitely, they have to implemented using jump and conditional jump instructions.
Question 4: What is the purpose of the computer's "main memory"?
Answer: The main memory stores data and program instructions for use by the CPU. (The CPU fetches the instructions from memory and executes them, often manipulating items of data in the process.)
Note: A "real" computer has two different types of memory: main memory and secondary memory. Main memory, often called "RAM", is very fast and is directly accessible to the CPU. However, it is temporary storage that is erased when the power is turned off. Secondary memory can store information permanently. It usually consists of disk drives. When you run a program, it has to be copied from secondary memory into main memory so that the computer can run it. The data used by the program (such as the characters that you type in a word-processing program) are also stored in main memory. If that data is to be saved permanently, it has to be saved to a file in secondary memory.
Question 5: One of the main ideas of this course is "structured complexity." Explain what is meant by structured complexity, and give an example that has nothing to do with computers.
Answer: Structured complexity refers to hierarchical levels of structure: Simple components are "chunked" together to make slightly more complex components, which can then be used for building even more complex componenst, and so forth. For example, in the human body, cells are groupts into tissues, which are grouped into organs, and so forth.
Note: There are, of course, many other examples besides the human body. The idea of levels of structures is very important. If we can't build up a complex system one reasonably easy level at a time, we are faced with a complicated mass of unorganized detail, like a jigsaw puzzle or a book full of random characters.
[by David Eck]