Algorithms Research & Evidence-Based Practice 2 — Questions and Answers
Question 1: In algorithm research, what does 'empirical evaluation' refer to?
- Proving algorithm correctness via mathematical induction
- Testing an algorithm on real or synthetic datasets to measure performance (Correct answer)
- Deriving time complexity from recurrence relations
- Analyzing space usage through formal methods
Correct answer: Testing an algorithm on real or synthetic datasets to measure performance
Empirical evaluation involves running an algorithm on actual inputs to observe practical performance, complementing theoretical analysis.
Question 2: Which experimental design principle helps isolate the effect of a single algorithmic parameter?
- Randomized control
- Ceteris paribus (all else equal) (Correct answer)
- Bootstrap sampling
- Cross-validation
Correct answer: Ceteris paribus (all else equal)
Ceteris paribus—varying one parameter while holding others constant—isolates the causal effect of that parameter on performance.
Question 3: Why do algorithm researchers use multiple independent random seeds when benchmarking randomized algorithms?
- To increase cache hit rates
- To reduce bias from a single lucky or unlucky run (Correct answer)
- To comply with IEEE floating-point standards
- To parallelize the benchmark across cores
Correct answer: To reduce bias from a single lucky or unlucky run
Multiple seeds average out variance inherent in randomized algorithms, giving a more reliable estimate of expected performance.
Question 4: What is the purpose of a 'baseline algorithm' in an algorithm research paper?
- To define the lower bound of the problem
- To serve as a reference point that highlights the proposed algorithm's improvements (Correct answer)
- To initialize data structures before benchmarking
- To compute the asymptotic complexity of the new method
Correct answer: To serve as a reference point that highlights the proposed algorithm's improvements
A baseline is an established method against which the new algorithm is compared to demonstrate relative improvements.
Question 5: Which measure best captures the variability of runtime results across repeated trials?
- Arithmetic mean
- Median
- Standard deviation (Correct answer)
- Maximum value
Correct answer: Standard deviation
Standard deviation quantifies how spread out individual trial runtimes are around the mean, capturing variability.
Question 6: When comparing two sorting algorithms experimentally, using only already-sorted input arrays introduces what kind of bias?
- Selection bias (Correct answer)
- Confirmation bias
- Survivorship bias
- Recency bias
Correct answer: Selection bias
Using only sorted inputs is selection bias because the input distribution does not represent the algorithm's general workload.
Question 7: A researcher claims Algorithm A is faster than Algorithm B because A ran faster on one dataset. What critical flaw exists in this conclusion?
- The claim ignores space complexity
- A single dataset is insufficient to generalize performance (Correct answer)
- The researcher should use Big-O instead of wall-clock time
- Algorithm B should be re-implemented in a lower-level language
Correct answer: A single dataset is insufficient to generalize performance
Performance on a single dataset cannot reliably generalize because results may differ significantly across input types and sizes.
Algorithms Research & Evidence-Based Practice 2
In algorithm research, what does 'empirical evaluation' refer to?