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.