Algorithms Research & Evidence-Based Practice 5 — Questions and Answers
Question 1: What is the 'no free lunch theorem' and its implication for algorithm research?
- Every algorithm has the same average-case performance summed over all problems
- No single algorithm outperforms all others across every possible input distribution (Correct answer)
- All NP-hard problems require exponential time in the worst case
- The optimal algorithm always uses the least memory
Correct answer: No single algorithm outperforms all others across every possible input distribution
The no free lunch theorem states that no single algorithm dominates all others across all problem instances, emphasizing that benchmarks must cover diverse inputs.
Question 2: In the context of algorithm research, what is 'construct validity'?
- Whether the algorithm's data structures are correctly built
- Whether the metrics chosen (e.g., wall-clock time) accurately reflect the theoretical concept being measured (e.g., efficiency) (Correct answer)
- Whether the algorithm terminates correctly on all valid inputs
- Whether the code compiles without errors across platforms
Correct answer: Whether the metrics chosen (e.g., wall-clock time) accurately reflect the theoretical concept being measured (e.g., efficiency)
Construct validity asks whether the empirical measure (e.g., runtime in milliseconds) genuinely captures the theoretical construct (e.g., computational efficiency) under study.
Question 3: Why should algorithm researchers use open benchmark suites (e.g., SNAP for graphs) instead of custom private datasets when possible?
- Open benchmarks are always larger than private datasets
- Open benchmarks enable reproducibility and fair comparison with prior work (Correct answer)
- Open benchmarks are pre-sorted for algorithmic convenience
- Custom datasets violate academic fair-use policies
Correct answer: Open benchmarks enable reproducibility and fair comparison with prior work
Standardized open benchmarks let different research groups run the same inputs, making results directly comparable and experiments reproducible.
Question 4: A new approximation algorithm for TSP claims a 1.5-approximation ratio. What empirical evidence would best complement this theoretical guarantee?
- Proof that the algorithm runs in O(n²) time
- Benchmark comparisons showing the algorithm's solution quality and runtime on diverse TSP instances versus existing methods (Correct answer)
- A formal reduction from TSP to a simpler problem
- Measurement of the algorithm's memory footprint on large instances
Correct answer: Benchmark comparisons showing the algorithm's solution quality and runtime on diverse TSP instances versus existing methods
Empirical benchmarks show how the approximation guarantee manifests in practice and whether the algorithm is competitive with existing approaches on real instances.
Question 5: What is 'confirmation bias' in algorithm research and how can it be mitigated?
- The tendency to favor algorithm designs that confirm existing computational models, mitigated by peer review
- The tendency to design experiments that favor a hypothesis, mitigated by pre-registering experimental protocols (Correct answer)
- The tendency to cite only papers that agree with the proposed approach, mitigated by systematic literature review
- The tendency to choose inputs that highlight best-case performance, mitigated by using adversarial inputs
Correct answer: The tendency to design experiments that favor a hypothesis, mitigated by pre-registering experimental protocols
Confirmation bias in experiments involves unconsciously designing setups that favor the expected result; pre-registration commits to methodology before seeing outcomes.
Question 6: What does it mean for an experimental result to be 'statistically significant but not practically significant'?
- The result was computed correctly but the code was not optimized
- The measured performance difference is unlikely due to chance but too small to matter in real applications (Correct answer)
- The algorithm runs faster on average but uses more memory
- The result applies to theoretical models but not to hardware implementations
Correct answer: The measured performance difference is unlikely due to chance but too small to matter in real applications
A tiny difference (e.g., 0.001ms) can be statistically significant with enough samples yet have no meaningful impact on practical use.
Question 7: Which of the following best describes the purpose of 'sensitivity analysis' in algorithm experiments?
- Checking whether the algorithm is sensitive to floating-point rounding errors
- Testing how algorithm performance changes as key parameters (e.g., input size, load factor) vary (Correct answer)
- Measuring how sensitive the CPU is to thermal throttling during benchmarks
- Verifying that the algorithm handles null or empty inputs without crashing
Correct answer: Testing how algorithm performance changes as key parameters (e.g., input size, load factor) vary
Sensitivity analysis examines how outputs change when input parameters vary, revealing which parameters most strongly influence algorithm performance.
Algorithms Research & Evidence-Based Practice 5
What is the 'no free lunch theorem' and its implication for algorithm research?