This page contains questions and answers for the sixth quiz in CS100: Principles of Computer Science, a course based on the book The Most Comples Machine. The answers given here are sample answers only. There is always some variation in the answers that would receive full credit. The Notes contain any extra comments I happen to have; they are not parts of the answers.
Question 1: Explain briefly what is meant by the term computer database.
Answer: A computer database is a collection of information stored permanently (usually) on a computer's hard disk, organized so that data can be easily modified and retrieved.
Note: The difference between a database and some typical bunch of data on a computer is, first of all, the size of the data collection--a database can be extremely large--and its structure. A large collection of data is only useful if it is reasonably easy to find the exact data you want. Often, a special "query language" is used to manipulate the data in a database.
Question 2: One of the major areas of computer application is optimization. Explain what is meant by this term and give an example.
Answer: Optimization refers to choosing the best possible option from a range of possible options. In some cases, a computer can be used to compute the best option. This is true, for example, in linear programming, where the problem is to allocate available resources among various possible uses in the way that will optimize (usually) profit.
Question 3: In analysis of algorithms, "big-O" notation is used to give some idea of the efficiency of an algorithm. We might say, for example, that an algorithm is O(n^2) or that is is O(n*log(n)). What, by definition, does it mean to say that a certain algorithm is O(n^2)?
Answer: By definition, an algorithm is said to be O(n^2) if there is a constant k such that the average running time for inputs of size n is less than or equal to k*n^2, at least for large values of n. (Input size might mean, for example, the number of characters in an input data file, or the number of numbers in an array.)
Note: In the cases we have seen, it is true that the running time is approximately proportional to n^2. That is, there is a constant k such that the run time is just about equal to k*n^2 for large n. Technically, though, the definition allows the possibility that the run time is actually strictly less than k*n^2. The formula, then, only gives an upper bound on the running time.
Question 4: Suppose that selection sort is applied to the following list of numbers:
12 5 17 3 2 10
Show what this list will look like after each phase of selection sort. (There are five phases; each one moves one number into its correct final location.)
Answer: In the first phase, the largest number (17) is located and is swapped with the number (10) at the end of the list. In the second phase, the second largest number is located and swapped with the number second from the end, and so forth:
After phase 1: 12 5 10 3 2 17 (swap 10, 17)
After phase 2: 2 5 10 3 12 17 (swap 12, 2)
After phase 3: 2 5 3 10 12 17 (swap 10, 3)
After phase 4: 2 3 5 10 12 17 (swap 3, 5)
After phase 5: 2 3 5 10 12 17 ("swap" 3 with itself?)
Note: The last step might look silly, but to be perfectly, technically correct, it should be there. After phase 4, the computer has no way of knowing that the two remaining numbers, 2 and 3, are already in the right order, so it finds the largest of them, 3, and puts it in its final position. As it happens, in this case, it is already in that position, so it looks as though nothing has happened.