Algorithm Engineering, Evaluation and AI Applications

Introduction

An algorithm is not merely an abstract procedure with an asymptotic running time. In a production system, its usefulness depends on implementation quality, hardware behavior, data characteristics, software dependencies, operational constraints, and the consequences of failure. Algorithm engineering is the disciplined process of transforming algorithmic ideas into reliable, efficient, testable, and maintainable software.

This perspective is especially important in artificial intelligence (AI). Machine-learning pipelines repeatedly execute data structures and algorithms for training, inference, graph traversal, recommendation, ranking, nearest-neighbour search, and vector retrieval. An algorithm with an attractive theoretical complexity may perform poorly because of cache misses, memory allocation, synchronization, skewed workloads, or an unsuitable data distribution. Conversely, a theoretically less sophisticated method may be preferable when it is simpler, more robust, or faster for the actual workload.

This chapter develops a practical evaluation framework covering profiling, benchmarking, workload analysis, testing, reproducibility, and the assessment of algorithms used in machine learning, graph analytics, recommendation, search, and vector retrieval.

Learning Objectives

After completing this chapter, a student should be able to:

1. Distinguish asymptotic analysis from empirical algorithm evaluation.
2. Design reliable benchmarks and interpret performance measurements statistically.
3. Use profiling to identify CPU, memory, I/O, synchronization, and allocation bottlenecks.
4. Construct representative workloads and explain why workload sensitivity matters.
5. Apply testing strategies for deterministic, randomized, parallel, and approximate algorithms.
6. Design reproducible experiments and report results responsibly.
7. Evaluate algorithms used in AI systems, including graph algorithms, recommenders, search engines, and vector-retrieval systems.
8. Analyse trade-offs among accuracy, latency, throughput, memory, cost, fairness, privacy, and maintainability.

1. From Algorithm Analysis to Algorithm Engineering

1.1 The limits of asymptotic complexity

Asymptotic notation describes how resource use grows as input size increases. If an algorithm performs a number of operations proportional to n log n, its time complexity is O(n log n). This abstraction is valuable because it suppresses machine-specific details and permits comparison across input sizes.

However, asymptotic notation does not specify:

• constant factors;
• memory locality and cache behaviour;
• branch prediction;
• object-allocation overhead;
• parallel scalability;
• I/O and network costs;
• compiler and runtime effects; or
• the distribution and structure of real inputs.

For example, scanning a compact array may outperform a theoretically faster tree-based method for small or moderate datasets because arrays have excellent spatial locality. Similarly, a hash table may offer expected constant-time lookup, but its performance depends on the quality of the hash function, load factor, collision handling, resizing policy, and memory layout.

A complete evaluation therefore combines:

1. Theory: correctness, complexity, approximation guarantees, and termination.
2. Implementation analysis: data layout, concurrency, memory management, and dependencies.
3. Measurement: controlled experiments using representative workloads.
4. Operational evaluation: reliability, observability, cost, security, and maintainability.

1.2 A performance model

A useful first approximation for elapsed time is:

Here, each term represents elapsed time attributable to computation, memory access, input/output, network communication, synchronization, and runtime or system overhead. The terms are not always independent; for example, synchronization can increase memory traffic, and I/O can overlap with computation. Thus, the equation is a decomposition for diagnosis rather than a universal physical law.

For a service processing requests, two important measures are:

and

Throughput is measured in requests per second, records per second, or another domain-specific unit. Utilization is dimensionless and normally expressed as a percentage. High utilization does not necessarily imply good performance: a system can be fully utilizing a CPU while producing unacceptable latency.

Latency should be reported using a distribution rather than only an arithmetic mean. The p95 latency is the value below which 95% of observations fall; p99 similarly describes the 99th percentile. Tail latency is often decisive in interactive AI applications because a small fraction of slow requests can degrade user experience.

2. Profiling and Bottleneck Diagnosis

Profiling observes where a program spends time or resources. It should answer a specific question, such as “Which functions dominate CPU time?” or “Why does memory usage grow during batch inference?” Profiling without a hypothesis can produce large quantities of low-value data.

2.1 Types of profiling

Sampling profilers periodically interrupt execution and record the current call stack. They usually have low overhead and are effective for identifying hot functions. Their limitation is statistical: short-lived functions may be missed.

Instrumentation profilers insert measurement code at function entry and exit. They can provide detailed call counts and inclusive or exclusive times, but instrumentation may substantially alter execution.

Hardware-performance profiling uses processor counters to examine cache misses, branch mispredictions, cycles, instructions, and memory bandwidth. It is valuable when source-level timing alone cannot explain a bottleneck.

Memory profiling measures allocation frequency, retained objects, heap growth, fragmentation, and leaks. In managed languages, allocation rate can cause garbage-collection pauses even when peak memory remains acceptable.

Distributed tracing follows a request across services. It is essential when an apparently slow algorithm is actually waiting on a database, remote model server, or vector index.

2.2 A disciplined profiling workflow

A practical workflow is:

1. Define the performance objective and metric.
2. Establish a baseline using a fixed version of the software.
3. Profile representative workloads.
4. Locate the dominant resource or critical path.
5. Form a causal hypothesis.
6. Change one important factor at a time.
7. Re-measure correctness and performance.
8. Retain the improvement only if it survives independent workloads.

The “largest percentage” in a profile is not automatically the best optimization target. A function may dominate CPU time because it is unavoidable, while a smaller function may be responsible for excessive allocations or synchronization. Optimization should consider both cost and avoidability.

2.3 Amdahl’s law and optimization limits

If a fraction p of execution time can be improved by a factor s, the overall speedup is bounded by Amdahl’s law:

where 0 ≤ p ≤ 1 and s ≥ 1. The formula assumes that the improved and unimproved portions are separable and that the optimization does not add significant overhead.

For example, if 80% of execution time is accelerated by a factor of 4, then:

Thus, a fourfold improvement in one component produces only a 2.5-fold overall speedup. This result encourages engineers to identify the true end-to-end critical path rather than optimizing an isolated kernel.

3. Benchmark Design and Statistical Evaluation

3.1 Benchmarking principles

A benchmark is a controlled experiment, not simply a timer around a function call. A credible benchmark specifies:

• the question being investigated;
• hardware and software environment;
• input size and data distribution;
• warm-up policy;
• number of repetitions;
• measured response variable;
• competing implementations;
• correctness checks; and
• statistical treatment of results.

The benchmark harness should separate setup time from the operation being measured unless setup is part of the production cost. For example, building an index and querying an index are distinct phases in a vector-retrieval system. Both may matter, but combining them obscures the trade-off.

Warm-up is important in systems with just-in-time compilation, caching, adaptive optimization, or lazy initialization. A benchmark should either measure cold-start performance explicitly or discard a justified warm-up period before measuring steady-state behaviour.

3.2 Repetition and uncertainty

Let x₁, x₂, …, xₙ be n measured runtimes. The sample mean is:

The sample standard deviation is:

The mean and standard deviation are appropriate when measurements are reasonably stable and not severely skewed. Latency measurements often contain outliers and right skew; medians and percentiles may then be more informative.

A commonly used approximate 95% confidence interval for a mean is:

where t₀.₉₇₅,ₙ₋₁ is the appropriate Student t critical value. This interval estimates uncertainty in the population mean under assumptions including independent observations and a suitable sampling model. It is not a guarantee that 95% of individual future observations lie in the interval.

When comparing two algorithms, paired measurements on the same workloads can reduce noise. If dᵢ is the performance difference for pair i, analyse the differences d₁, …, dₙ rather than treating the two sets as unrelated. Report effect size as well as statistical significance; a tiny but statistically detectable improvement may have no operational value.

3.3 Avoiding common benchmark errors

Frequent errors include:

• timing input generation rather than algorithm execution;
• allowing one implementation to use a precomputed result;
• comparing different correctness requirements;
• using unrealistically small inputs;
• measuring only the fastest run;
• ignoring garbage collection and memory pressure;
• changing compiler flags between implementations;
• reporting averages while hiding tail latency; and
• selecting workloads that favour the preferred algorithm.

Benchmark results should include enough metadata for another engineer to reproduce them: source revision, dependency versions, compiler or interpreter version, operating system, processor, memory, random seeds, dataset identifiers, and configuration parameters.

4. Workload Analysis

Performance is a property of an algorithm–implementation–workload combination. A workload should therefore be described by more than a single size parameter.

Relevant dimensions include:

• input size and growth rate;
• value range and key distribution;
• sortedness or temporal order;
• duplication and skew;
• graph degree distribution and community structure;
• query selectivity;
• read/write ratio;
• batch size and concurrency;
• dimensionality and norm distribution of vectors; and
• frequency of updates and deletions.

4.1 Representative and adversarial workloads

A representative workload approximates expected production behaviour. It may be obtained from anonymized historical traces, synthetic generators calibrated to production statistics, or a combination of both. An adversarial workload is intentionally difficult and tests robustness: a hash table may receive colliding keys, a graph algorithm may receive a high-degree hub, and a recommendation system may receive a new user with no interaction history.

Both are necessary. Representative workloads support capacity planning, while adversarial workloads expose failure modes and worst-case behaviour.

4.2 Experimental factors

A factorial experiment varies several factors systematically. For example, vector retrieval might vary dataset size, vector dimension, index type, search parameter, and query batch size. The engineer should distinguish:

• independent variables: factors deliberately varied;
• dependent variables: measured outcomes;
• controlled variables: conditions held constant; and
• confounders: hidden factors that may explain an observed difference.

Randomized workload order can reduce bias caused by thermal changes, background processes, or temporal drift. Blocking experiments by machine or deployment environment can separate hardware variation from algorithmic effects.

5. Correctness and Reliability Testing

A fast incorrect algorithm is unusable. Testing must therefore be integrated with performance evaluation.

5.1 Test oracles and invariants

A test oracle determines whether output is correct. For sorting, the oracle can verify that the output is ordered and is a permutation of the input. For a shortest-path algorithm, it can verify path validity and compare distances against a trusted reference on small graphs.

An invariant is a property that should remain true during or after execution. Examples include:

• a heap’s parent key is no greater than its children’s keys;
• a balanced search tree satisfies ordering and balance constraints;
• graph edge counts remain consistent after updates; and
• an index returns identifiers that exist in the source dataset.

5.2 Testing strategies

Unit tests isolate data structures or functions. They should include boundary cases such as empty input, one element, duplicate values, maximum values, and repeated deletion.

Property-based testing generates many inputs and checks general properties rather than fixed outputs. It is effective for parsers, collections, sorting, graph transformations, and numerical routines.

Differential testing compares two implementations or a production implementation with a simple reference algorithm. The reference need not be fast; it must be trusted for small inputs.

Metamorphic testing checks relations between executions when an exact oracle is difficult. For example, adding an irrelevant item to a dataset should not change the nearest neighbour of a query if the item is provably farther away.

Fuzz testing supplies malformed, random, or adversarial inputs to identify crashes, hangs, resource exhaustion, and security vulnerabilities.

Load and stress testing examine behaviour under expected and excessive demand. Soak testing observes long-running systems for leaks, fragmentation, drift, and degradation.

Randomized algorithms require controlled seeds for debugging and multiple seeds for evaluation. A single seed can accidentally hide instability or create an unrepresentative result.

6. Reproducible Experimentation

Reproducibility means that an experiment can be repeated with the same materials and produce comparable findings. Exact bit-for-bit replication may be impossible across hardware, parallel schedules, libraries, or floating-point implementations, so reports should distinguish:

• repeatability: the same team repeats the experiment in the same environment;
• reproducibility: another team uses the supplied materials and obtains consistent results; and
• replicability: an independent implementation or study confirms the finding.

A reproducible experiment should provide:

1. version-controlled source code;
2. immutable or identified datasets;
3. environment specifications or containers;
4. configuration files rather than undocumented manual settings;
5. random seeds and generator details;
6. scripts that build, run, validate, and summarize results;
7. raw measurements, not only charts; and
8. documented exclusions, failed runs, and known limitations.

Reproducibility does not mean suppressing inconvenient results. Removing outliers is acceptable only when a pre-specified, defensible rule identifies a measurement failure. Otherwise, the outlier is part of the observed behaviour and should be reported.

7. Evaluating Algorithms in AI Systems

AI systems require multi-dimensional evaluation. A useful objective is not simply “minimum runtime” but a constrained trade-off among quality, latency, throughput, memory, energy, cost, robustness, and governance.

7.1 Machine-learning algorithms

Training algorithms can be evaluated by convergence speed, final objective value, generalization performance, memory consumption, communication cost, and stability across random seeds. The training loss is not sufficient: a model can reduce training loss while worsening validation performance.

For classification, common measures include accuracy, precision, recall, and F1 score. If true positives, false positives, and false negatives are denoted TP, FP, and FN, then:

These formulas assume the denominators are nonzero. Accuracy can be misleading for imbalanced classes, whereas precision and recall focus on different error costs. Evaluation should use an appropriate test set, avoid leakage, and report confidence or variation across splits and seeds.

7.2 Graph analytics

Graph algorithms are sensitive to topology. Breadth-first search may be efficient on sparse graphs but expensive on graphs with very high-degree hubs. PageRank, centrality, connected components, and community detection should be measured using graph size, number of edges, degree distribution, diameter, and update frequency.

For a graph with V vertices and E edges, a standard adjacency-list traversal is commonly expressed as O(V + E), assuming each vertex and edge is processed a constant number of times. This is a theoretical bound; memory locality, parallel scheduling, and graph representation can dominate actual performance.

Correctness testing should include disconnected graphs, self-loops, parallel edges, isolated vertices, directed and undirected interpretations, and dynamic updates where applicable. Results should also be checked for sensitivity to vertex ordering and partitioning in distributed execution.

7.3 Recommendation systems

Recommendation evaluation has at least two layers. Offline evaluation measures ranking quality using historical data. Online evaluation measures user and business outcomes, often through controlled experiments. Offline metrics such as precision@k, recall@k, mean reciprocal rank, and normalized discounted cumulative gain should not be interpreted as direct substitutes for user satisfaction.

A recommender must also address cold-start users and items, popularity bias, feedback loops, diversity, novelty, exposure fairness, and catalog coverage. A model that optimizes clicks can promote sensational or repetitive content. Algorithm engineering therefore includes monitoring for unintended consequences, not just optimizing a score.

7.4 Search and vector retrieval

Exact nearest-neighbour search compares a query vector with every stored vector. For N vectors of dimension d, a straightforward scan requires approximately proportional work to N × d per query, ignoring index and hardware details. Approximate nearest-neighbour (ANN) methods reduce query cost by searching only a candidate subset, at the cost of possible recall loss and index-construction overhead.

For a query, recall@k can be defined as:

where A_k is the set of k results returned by the approximate method and G_k is the exact top-k ground-truth set. Both sets contain k items under the usual definition, so the value lies between 0 and 1. If ties occur, the tie policy must be specified.

Important ANN measures include:

• recall@k or another retrieval-quality measure;
• p50, p95, and p99 query latency;
• queries per second under a stated concurrency;
• index-build time;
• index size and resident memory;
• update and deletion cost; and
• performance under changing data distributions.

A retrieval parameter that increases the number of candidates often improves recall but increases latency and memory traffic. The correct operating point depends on application-level utility, not on recall alone.

8. Illustrative Case: Evaluating a Product-Search Retrieval Service

Background

Consider an illustrative online retailer with 20 million product embeddings. A semantic-search service must return ten relevant products for each query. The existing exact scan provides strong quality but violates the 100 ms p95 latency objective during peak traffic.

Problem

The engineering team must choose between an inverted-file index and a graph-based ANN index. The decision must consider retrieval quality, latency, memory, update behaviour, and operational cost. A benchmark using only average latency would be inadequate.

Analysis and experimental design

The team constructs a frozen evaluation set of 10,000 anonymized queries. Exact search produces ground-truth top-ten results. The test varies index type, search parameter, query batch size, and concurrency. Each configuration is run with five independent random seeds where construction is randomized. The first 200 queries are used for warm-up, and subsequent queries are measured. Correctness checks verify that returned product identifiers exist and that filtering rules are respected.

The report includes p50 and p95 latency, recall@10, index memory, build time, and update delay. Workloads are divided into frequent queries, rare queries, short queries, and queries containing new terminology. A separate stress test introduces a high update rate and measures degradation.

Approach and decision

Suppose the graph index achieves recall@10 of 0.96 at 42 ms p95 and uses 48 GB of memory. The inverted-file index achieves recall@10 of 0.91 at 24 ms p95 and uses 22 GB. A stricter product category requires recall@10 ≥ 0.95, so the inverted-file configuration fails the quality constraint despite lower latency. The graph index is selected for the primary service, while a lower-memory configuration is retained for less demanding workloads.

The decision is not based on one number. It reflects a constraint: quality must reach the required threshold while p95 latency remains below 100 ms. The team also schedules periodic index rebuilding, monitors recall using labelled traffic, and tests filtering and deletion behaviour.

Outcome and learning points

The case illustrates five principles. First, exact search is a valuable reference oracle even when it is not operationally feasible. Second, quality and latency must be measured together. Third, p95 is more relevant than only the mean for interactive services. Fourth, workload segmentation can reveal that one configuration is not universally best. Fifth, an index is a maintained system component: build, update, memory, monitoring, and governance costs matter alongside query speed.

9. Engineering Trade-offs, Governance, and Ethics

Algorithm selection is often a multi-objective decision. Improving one objective can worsen another. Lower memory usage may increase CPU time; aggressive caching may increase privacy exposure; approximate retrieval may reduce latency but omit relevant items; and personalization may improve engagement while narrowing exposure.

Evaluation datasets can contain personal, copyrighted, or sensitive information. Engineers should apply data minimization, access control, retention limits, anonymization where appropriate, and documented provenance. Benchmarks must not expose private user queries or enable reconstruction attacks through released outputs.

Fairness evaluation should examine whether performance differs across relevant user or item groups. The appropriate definition of fairness depends on the application and cannot be inferred from a single aggregate metric. Governance should specify who approves datasets, who can change a ranking objective, how incidents are investigated, and when a model or index is retired.

Reproducible measurement also has an environmental dimension. Repeated large-scale experiments consume energy and compute resources. Efficient experimental design, reuse of cached intermediate results when valid, and transparent reporting of failed runs can reduce waste without compromising scientific integrity.

10. Contemporary Directions and Best Practices

Current algorithm engineering increasingly combines classical profiling with automated performance regression detection, hardware-aware data structures, vectorized execution, accelerators, learned indexes, adaptive query processing, and workload-aware configuration. These techniques are promising but introduce additional assumptions and failure modes.

A learned index may perform well on a stable distribution but degrade after distribution shift. An accelerator may reduce kernel time while increasing data-transfer overhead. Automated tuning may discover a configuration that wins on a benchmark but fails in production. Every innovation therefore requires out-of-distribution testing, rollback mechanisms, and monitoring.

A practical checklist is:

• Define quality, latency, throughput, memory, cost, and reliability objectives before implementation.
• Start with a clear baseline and a trusted correctness oracle.
• Profile before optimizing.
• Use representative, boundary, and adversarial workloads.
• Separate setup, steady-state, and update costs.
• Report distributions and uncertainty, not only single averages.
• Test deterministic and randomized behaviour across multiple seeds.
• Record environment, data, code revision, and configuration.
• Evaluate end-to-end performance rather than isolated kernels.
• Monitor production drift and establish rollback criteria.
• Include privacy, security, fairness, and maintainability in the decision.

Chapter Summary

Algorithm engineering connects theoretical algorithms with dependable software systems. Asymptotic complexity remains essential, but it cannot predict performance without considering constants, memory locality, runtime behaviour, concurrency, I/O, and workload structure. Profiling identifies resource bottlenecks, while Amdahl’s law explains why optimizing a small portion of execution has limited end-to-end benefit.

Reliable benchmarking requires controlled conditions, appropriate warm-up, repeated measurements, statistical interpretation, and transparent reporting. Workload analysis must include data distributions, topology, skew, concurrency, and update patterns. Correctness is established through oracles, invariants, differential testing, property-based testing, metamorphic testing, fuzzing, and stress testing.

AI applications require multi-objective evaluation. Machine-learning algorithms must be assessed for generalization and stability; graph algorithms for topology-sensitive performance; recommenders for ranking quality, diversity, bias, and online outcomes; and vector-retrieval systems for recall, tail latency, memory, indexing cost, and update behaviour. Reproducibility, privacy, fairness, security, and environmental cost are integral to professional algorithm evaluation.

Key Terms

Algorithm engineering: The disciplined development and evaluation of algorithms as reliable software systems.

Asymptotic analysis: Study of resource growth as input size increases.

Profiling: Measurement of where a program spends time or resources.

Sampling profiler: A profiler that periodically records execution state with relatively low overhead.

Instrumentation profiler: A profiler that inserts measurement operations into program execution.

Benchmark: A controlled experiment used to compare performance or resource use.

Workload: The data, queries, operations, and operating conditions supplied to a system.

Tail latency: High-percentile response time, such as p95 or p99 latency.

Amdahl’s law: A relation that bounds total speedup when only part of execution is improved.

Test oracle: A mechanism or trusted reference used to determine correctness.

Invariant: A property that must remain true during or after an operation.

Property-based testing: Testing that generates inputs and checks general properties.

Differential testing: Comparison of outputs from two implementations or a reference system.

Metamorphic testing: Testing relations between outputs from related inputs or executions.

Reproducibility: The ability to obtain consistent findings using documented materials and procedures.

Recall@k: The fraction of exact top-k results recovered by a retrieval method.

Approximate nearest-neighbour search: Retrieval that trades some exactness for lower search cost.

Workload drift: Change in input or query characteristics over time.

Tail-risk metric: A metric focused on adverse high-percentile or worst-case behaviour.

Algorithmic fairness: Evaluation and treatment of performance or impact across relevant groups.

Review Questions

Short Answer Questions

1. Why can an algorithm with better asymptotic complexity perform worse in practice?
2. Distinguish sampling profiling from instrumentation profiling.
3. What is the purpose of a warm-up phase in benchmarking?
4. Why should p95 or p99 latency be reported for interactive services?
5. What is the role of a correctness oracle in performance evaluation?

Long Answer Questions

1. Explain a complete workflow for profiling and optimizing a production algorithm, including the role of baselines and regression testing.
2. Discuss how representative and adversarial workloads complement each other in algorithm evaluation.
3. Derive and interpret the practical implications of Amdahl’s law for a parallel optimization project.
4. Compare unit, property-based, differential, metamorphic, fuzz, load, and soak testing.
5. Design a reproducible experimental protocol for comparing two vector-retrieval indexes.

Analytical / Application Questions

1. An optimization accelerates 70% of a program by a factor of 5. Calculate the theoretical overall speedup and explain why it is lower than 5.
2. A recommender improves offline recall but reduces catalog coverage and performs poorly for new users. Propose an evaluation framework and deployment safeguards.
3. An ANN index has excellent mean latency but unacceptable p99 latency during concurrent peak traffic. Diagnose possible causes and propose a measurement and remediation plan.

Multiple Choice Questions with Answers

Question 1

Which statement best explains why asymptotic complexity alone is insufficient for production algorithm selection?

A. Asymptotic notation applies only to recursive algorithms.

B. It ignores constants, hardware effects, memory locality, and workload structure.

C. It cannot describe algorithms with finite inputs.

D. It measures correctness rather than resource growth.

Correct Answer: B. It ignores constants, hardware effects, memory locality, and workload structure.

Question 2

A function accounts for 80% of execution time and is accelerated by a factor of 4. What is the approximate overall speedup under Amdahl’s law?

A. 1.25

B. 2.00

C. 2.50

D. 4.00

Correct Answer: C. 2.50

Question 3

Which profiling method generally has the lowest execution overhead while identifying frequently active call stacks?

A. Sampling profiling

B. Full function instrumentation

C. Manual logging at every instruction

D. Heap snapshot comparison only

Correct Answer: A. Sampling profiling

Question 4

Which measurement is most appropriate for describing the latency experienced by the slowest 1% of requests?

A. Mean latency

B. p50 latency

C. p90 latency

D. p99 latency

Correct Answer: D. p99 latency

Question 5

What is the primary purpose of using an exact nearest-neighbour search when evaluating an ANN index?

A. To reduce index-construction time

B. To provide a ground-truth result set

C. To eliminate the need for query workloads

D. To guarantee lower memory consumption

Correct Answer: B. To provide a ground-truth result set

Question 6

If TP = 80 and FP = 20, what is the precision of the classifier?

A. 0.20

B. 0.50

C. 0.80

D. 0.90

Correct Answer: C. 0.80

Question 7

Which testing strategy checks general properties over many generated inputs rather than only predetermined examples?

A. Property-based testing

B. Manual inspection

C. Deployment monitoring

D. Code formatting

Correct Answer: A. Property-based testing

Question 8

Which workload characteristic is especially important when evaluating graph algorithms?

A. Screen resolution

B. Degree distribution and graph topology

C. Keyboard layout

D. File-name length only

Correct Answer: B. Degree distribution and graph topology

Question 9

What does recall@k measure in approximate vector retrieval?

A. The fraction of returned top-k items that are exact ground-truth items

B. The percentage of index memory that is used

C. The number of queries processed per second

D. The time required to construct the index

Correct Answer: A. The fraction of returned top-k items that are exact ground-truth items

Question 10

Which practice most directly supports reproducible experimentation?

A. Reporting only the best run

B. Changing several configurations without recording them

C. Publishing code, data identifiers, environment details, seeds, and raw measurements

D. Removing all outliers after observing the results

Correct Answer: C. Publishing code, data identifiers, environment details, seeds, and raw measurements