CPSC 536H - Assignment 1

released Thu, 12/01/05; due Mon, 12/01/09, 18:00

Read the paper "A Theoretician's Guide to the Experimental Analysis of Algorithms" by David S. Johnson (linked from the course web page) and answer the following questions clearly and concisely, in your own words:

1. What is the difference between what Johnson calls a "horse-race paper" and an "experimental analysis paper"?

2. Considering Johnson's discussion of anomalies, elaborate on his arguments why anomalous results can be very important.

3. When evaluating multiple algorithms on a distribution of randomly generated problem instances, why is it important to use one set of benchmark problems for all algorithms (rather than separate samples from the distribution for each of them)?

4. Carefully consider "Pet Peeve 9". Do you see any weaknesses in Johnson's arguments? Carefully justify your answer.

5. Reading questions: List at least 3 questions that you had after reading Johnson's paper. These could be related to aspects that, even after careful study, you did not understand, or questions prompted by Johnson's discussion of experimental analysis techniques but not answered by him. In the latter case, relate your question(s) to specific parts of Johnson's paper.

General remarks: