Friday, December 14, 2012

The Early Results

As the semester winds up, I feel that the course has been a success.  This precedes grading of the final exam, and inspection of the student evaluations, and is colored by the usual relief on achieving the minimal standard that no disaster occurred.  No one dropped out after the first week, no one imploded, and no one ran screaming from the classroom.  (As they must, for greatest significance, these statistics include the instructor.)

As a quick means of illustrating the outcomes, while keeping student work confidential, let me simply provide the questions from the Take-Home part of the final exam (which was complemented by an In-Class part).


1. Although we still haven’t decided whether an algorithm that we refer to by name, such as Selection Sort, includes all of its dynamic instantiations (executions), we know that it can’t be defined fully by just one execution trace. Why?

2. We have seen that games rely on input data during execution. Theoretically, the result of any deterministic process that has all input known at start can be computed by an observer without even running. Consider an auction, as well, and explain whether these things are algorithms, in your opinion.

3. (From the Final Review class): If a description, including task and preconditions, is part of an algo- rithm, what kind of part is it? What is the ontology of the description, and how does it relate to the ontology of the instructions? Here are some possibilities.

(a) The preconditions, because they are don’t fit our definition, are a separate but necessary part of an algorithm. The algorithm object is really a pair of things, one a written description and the other a written set of instructions as we have conceived of it.

(b) The preconditions are implicit in the instructions themselves, and don’t require a separate recognition. The algorithm is nothing without those conditions. So Binary Search, for example, because it works only on sorted data, “assumes” sorted data, without any need to say so explicitly.

Choose one, or make up your own, and defend it based on our accepted definition of algorithm, and your own view of the unsettled questions.

4. Choose one of the questions below to answer. Your answer may be speculative, but give reasons for your claims.

(a) We have never clearly discussed one of the questions from the textbook: Do we ourselves embody algorithms? This does not mean executing an algorithm deliberately and consciously; it means how we accomplish tasks in our daily lives. We have discussed performing Binary Search in a naive form, when searching in a phone book, for example. How about others, such as transmission protocols and LIFO processing? Does your view on these questions tell us anything about algorithms in general?

(b) Is recursion itself an algorithm? Recall that we have seen a definition of primitive recursion (giving the minimal structures of a programming language) that includes this operation:
f (x, 0) = h(x) 
f (x, succ(y)) = g(y, f (y)
Although it is given as a declarative, contributing to the definition of a set of functions, can it be construed as a set of directions and thereby an algorithm in itself? Explain your answer by using aspects of algorithms that we have seen in this class.

5. We have a list of still-controversial properties, as given in Chapter 10 of the textbook. These are attributes that may or may not apply to algorithms in general (or perhaps they have different values for individual algorithms). They are inter-dependent in many ways. Pick one and explain how settling its status would affect two of the other controversial properties.