Capstone laboratories and research pathway | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython example pack ↓

Lab 1 — Route engine: Validate directed weighted graph input. Implement BFS, Dijkstra and Bellman-Ford under separate contracts. Use Floyd-Warshall as a small random-graph oracle. Test negative cycles, disconnected vertices and zero weights. Explain algorithm selection, not just runtime.

Lab 2 — Text index: Compare naive search, KMP and suffix-array indexing. Specify Unicode/byte semantics and test overlapping matches and empty patterns. Measure build time, query time and peak memory; explain updates. Add Aho-Corasick for multiple patterns and compare result sets with an oracle.

Lab 3 — Storage simulator: Combine LRU, Bloom and consistent placement. Confirm Bloom positives against the source of truth; test node churn and hot keys. This is not a consensus implementation. Model the Raft paper’s state machine and safety conditions separately as an advanced extension.

Assessment requires four forms of evidence: correct outputs/invariants, justified complexity, reproducible benchmarks and failure cases. Use MIT/Princeton for proofs, Morin for implementations and Erickson for reductions/design. Separate a paper’s model, theorem, assumptions, proof and experiments. This pathway produces engineering evidence, not a claim that every topic is mastered.

A worked trace

Keep seeds, inputs, expected outputs, computational models and measurement environments for each lab.

Cost and assumptions

Report input size and distribution; one benchmark cannot establish Big-O.

Executable example

Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.

Python 3

import random
rng=random.Random(42)
for n in range(20):
    data=[rng.randrange(-100,100) for _ in range(n)]
    result=sorted(data)
    assert all(result[i]<=result[i+1] for i in range(len(result)-1))
    assert sorted(result)==sorted(data)

TEST YOUR UNDERSTANDING

Your turn

Is checking sorted order alone enough for sorting correctness?

Reveal the reasoning

No; preserve the input multiset. An empty result is sorted but can hide lost elements.

Take it further

Write down the input contract and the invariant before changing the example.
Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
Derive the cost under the stated model; measure several input sizes and explain discrepancies.

Primary reading & lecture notes

Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.

MIT 6.006 · Introduction to Algorithms ↗Pat Morin · Open Data Structures ↗Jeff Erickson · Algorithms ↗

Solve the exercise before moving on.

RasimAtaberkŞahin