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 **Note**s
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.