Algorithms Research & Evidence-Based Practice 4 — Questions and Answers
Question 1: What is 'p-hacking' in algorithm research and why is it problematic?
- Optimizing algorithm parameters to minimize memory usage
- Running many statistical tests and only reporting those that show significance, inflating false-positive rates (Correct answer)
- Compiling code with aggressive compiler optimizations to improve benchmarks
- Hashing inputs to ensure uniform distribution in experiments
Correct answer: Running many statistical tests and only reporting those that show significance, inflating false-positive rates
P-hacking exploits the fact that running many tests increases the chance of a false positive, producing misleading claims of significance.
Question 2: In cache-oblivious algorithm research, what experimental evidence is typically gathered to validate theoretical predictions?
- CPU instruction counts measured via hardware counters
- Cache miss rates measured using profiling tools on inputs of varying sizes (Correct answer)
- Branch misprediction rates across different CPU architectures
- Floating-point error accumulation across precision levels
Correct answer: Cache miss rates measured using profiling tools on inputs of varying sizes
Cache miss rates directly test whether the algorithm achieves the predicted low cache-miss behavior as problem size grows relative to cache size.
Question 3: What does 'effect size' measure in an algorithm performance comparison study?
- The number of operations saved by the better algorithm
- The practical magnitude of the performance difference, independent of sample size (Correct answer)
- The ratio of worst-case to average-case runtime
- The algorithmic gap between the lower bound and best known solution
Correct answer: The practical magnitude of the performance difference, independent of sample size
Effect size quantifies how large the performance difference is in practical terms, preventing a statistically significant but negligibly small difference from being over-interpreted.
Question 4: Why do some algorithm researchers prefer to report median runtime instead of mean runtime?
- Median is easier to compute than mean
- Median is robust to outliers caused by OS scheduling or garbage collection pauses (Correct answer)
- Mean violates IEEE floating-point standards for time measurements
- Median always underestimates the true performance
Correct answer: Median is robust to outliers caused by OS scheduling or garbage collection pauses
Rare but extreme outliers (e.g., OS interrupts, GC pauses) skew the mean upward, while the median reflects typical performance more accurately.
Question 5: What is the 'streetlight effect' pitfall in algorithm benchmarking?
- Only testing an algorithm under bright lighting conditions in labs
- Only evaluating inputs or scenarios that are convenient, missing hard or realistic cases (Correct answer)
- Relying on profiler tools that distort cache behavior
- Choosing a dataset that makes the algorithm look optimal
Correct answer: Only evaluating inputs or scenarios that are convenient, missing hard or realistic cases
The streetlight effect refers to evaluating only easy or convenient inputs rather than the diverse and potentially harder inputs the algorithm will face in practice.
Question 6: When validating a graph algorithm empirically, why is it important to test on both sparse and dense graphs?
- Dense graphs are always harder and reveal the worst case
- Algorithm performance often depends on edge density, and real-world graphs vary widely in density (Correct answer)
- Sparse graphs expose memory allocation bugs more reliably
- Dense graphs allow vectorized operations unavailable for sparse inputs
Correct answer: Algorithm performance often depends on edge density, and real-world graphs vary widely in density
Many graph algorithms have complexity that depends on both vertices and edges, so performance characteristics differ substantially between sparse and dense inputs.
Question 7: Which practice strengthens the external validity of an algorithm benchmark study?
- Using a single large dataset and reporting mean runtime only
- Evaluating the algorithm on diverse datasets from different domains and sizes (Correct answer)
- Comparing only against the weakest known competitor
- Running benchmarks on a single hardware platform to control variables
Correct answer: Evaluating the algorithm on diverse datasets from different domains and sizes
Testing across diverse domains and sizes increases confidence that conclusions generalize beyond the specific conditions of the study.
Algorithms Research & Evidence-Based Practice 4
What is 'p-hacking' in algorithm research and why is it problematic?