Algorithms Research & Evidence-Based Practice 3 — Questions and Answers
Question 1: What is the role of a 'systematic literature review' in algorithm research?
- To implement all known algorithms in a unified codebase
- To comprehensively identify and synthesize existing research on a topic using a defined protocol (Correct answer)
- To rank algorithms by their worst-case complexity
- To verify that an algorithm produces correct outputs
Correct answer: To comprehensively identify and synthesize existing research on a topic using a defined protocol
A systematic literature review follows a reproducible protocol to collect, filter, and synthesize all relevant prior work on a research question.
Question 2: In algorithm benchmarking, what is 'warm-up time' and why is it excluded from measurements?
- Time for the CPU to reach operating temperature, irrelevant to software
- Initial execution time skewed by JIT compilation or cache loading that doesn't reflect steady-state performance (Correct answer)
- Time spent reading the input file from disk
- The overhead of initializing random seeds before benchmarking
Correct answer: Initial execution time skewed by JIT compilation or cache loading that doesn't reflect steady-state performance
Warm-up runs allow JIT compilers to optimize hot paths and caches to fill, so excluding them gives a fairer measure of steady-state performance.
Question 3: Which statistical test is commonly used to determine if the performance difference between two algorithms is statistically significant?
- Pearson correlation
- Wilcoxon signed-rank test (Correct answer)
- Chi-square test of independence
- F-test for equality of variances
Correct answer: Wilcoxon signed-rank test
The Wilcoxon signed-rank test is a non-parametric test appropriate for comparing paired algorithm runtime samples that may not be normally distributed.
Question 4: What does 'reproducibility' mean in the context of algorithm experiments?
- The algorithm produces the same output for deterministic inputs
- Independent researchers can re-run experiments and obtain consistent results (Correct answer)
- The algorithm terminates in the same number of steps every time
- Source code compiles without errors on any platform
Correct answer: Independent researchers can re-run experiments and obtain consistent results
Reproducibility means another researcher, using the same code and data, can independently confirm the original experimental results.
Question 5: Why is it important to report both average-case and worst-case performance in algorithm research?
- Funding agencies require both metrics
- Average case reveals typical behavior while worst case reveals reliability under adversarial or pathological inputs (Correct answer)
- Worst case is always worse than average by a constant factor
- Average case is always easier to compute than worst case
Correct answer: Average case reveals typical behavior while worst case reveals reliability under adversarial or pathological inputs
Average case describes expected real-world performance while worst case exposes fragility to specific inputs, together giving a complete picture.
Question 6: When an algorithm paper reports only results on synthetic data, what concern does this raise?
- Synthetic data is always too small to stress-test the algorithm
- The algorithm may not generalize to real-world data distributions (Correct answer)
- Legal issues around data privacy are avoided unnecessarily
- The paper cannot be submitted to peer review
Correct answer: The algorithm may not generalize to real-world data distributions
Synthetic data may not capture the statistical properties of real-world inputs, so generalizability of results remains unverified.
Question 7: What is the purpose of 'ablation studies' in algorithm research?
- To remove outliers before computing the mean runtime
- To disable individual components of an algorithm to measure each component's contribution to overall performance (Correct answer)
- To test the algorithm on progressively smaller inputs
- To compare the algorithm against randomly generated competitors
Correct answer: To disable individual components of an algorithm to measure each component's contribution to overall performance
Ablation studies systematically remove or disable parts of a system to isolate and quantify the contribution of each component.
Algorithms Research & Evidence-Based Practice 3
What is the role of a 'systematic literature review' in algorithm research?