CPSC 536H - Assignment 1

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:

• While cooperation between students is encouraged, each student is expected to work out the answers to the questions in this assignment individually and hand in their own assignment. In other words: help each other, but do not copy solutions.
• Your answers have to be submitted via e-mail to Holger, in PDF or plain text format, by the due time indicated above.
• Late hand-ins are normally not accepted. Exceptions will only be made when well-documented, compelling reasons can be given, at the discretion of the instructor.