CPSC 536H - Assignment 2

Read Chapter 4 of the book "Stochastic Local Search - Foundations and Applications" by Hoos & Stützle, and answer the following questions as clearly and concisely as possible:

1. Is it possible to conclude from an empirical run-time distribution whether a Las Vegas algorithm is essentially incomplete? Briefly explain your answer.

2. What is the difference between a solution cost distribution (SCD) and a run-time distribution (RTD)?

3. What are solution quality traces and how can they be used to compute empirical QRTDs and SQDs?

4. Which statistical hypothesis test would you use to decide whether the RTD of a given Las Vegas algorithm on a given problem instance is affected by changing a single algorithm parameter?

Now, read the notes for Module 2 (available from the course web page), and answer the following questions as clearly and concisely as possible:

5. Which quantiles are graphically represented in a box plot?

6. Why is it often preferable to measure and compare median rather than mean performance?

7. Why should one study entire SCDs rather than merely some descriptive statistics (such as median and quantile ranges or ratios)?

The following question is not for credit, i.e., feel free to skip it if you don't have time:

Is there anything important in the reading for this assignment that you find confusing or unclear? If so, briefly indicate which parts caused you difficulties.

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.