Skip to content

Module 3: Data structures and algorithms

Use the task tracker to learn how access patterns drive data-structure choices. Predict costs first, measure them second, and change the application only when the evidence justifies it.

Learning outcomes

By the end of this module, you should be able to:

  • describe a workload in terms of reads, writes, ordering, and scale;
  • choose a structure from required operations rather than habit;
  • derive time and space complexity from the work performed;
  • implement linear search, binary search, a stable sort, and breadth-first search;
  • design a small benchmark that compares equivalent behavior;
  • distinguish an educational implementation from production code.

Start with the workload

The Module 1 tracker stores tasks as a list. Before replacing it, write down the operations it supports:

Operation Current structure Expected cost
Append a task List Amortized \(O(1)\)
Find by ID Linear scan \(O(n)\)
Delete by ID Find, then shift elements \(O(n)\)
List every task Sequential traversal \(O(n)\)
Save all tasks as JSON Sequential serialization \(O(n)\)

The list is a reasonable default: the program already loads and saves every task, so optimizing one lookup may not improve the end-to-end command. Keep that hypothesis visible throughout the exercises.

Lab 1: Linear lookup and a map-backed index

Implement two functions with the same observable result:

find_linear(tasks, task_id) → task or not found
build_index(tasks) → mapping from ID to task
find_indexed(index, task_id) → task or not found

Test duplicate IDs even though valid stored data should not contain them. Decide whether index construction rejects the invalid collection or silently overwrites an entry; rejection makes the invariant failure visible.

Analyse the complete operation, not just its fastest line:

Approach Build One lookup Extra space Preserves list order
Linear scan None \(O(n)\) \(O(1)\) Yes
Dictionary index \(O(n)\) \(O(1)\) average \(O(n)\) Separate list still required

A temporary index costs \(O(n)\) to build, so it is useful mainly when reused for multiple lookups. A persistent second structure also creates a consistency obligation after every mutation.

Lab 2: Binary search and its precondition

Implement iterative binary search over tasks sorted by ID. Maintain a half-open interval, [low, high), which makes an empty search range unambiguous.

Test:

  • first, middle, and last IDs;
  • an ID smaller and larger than every stored ID;
  • an absent ID between two present IDs;
  • an empty collection;
  • one task.

Then deliberately call it with unsorted input. Binary search is not “sometimes inaccurate” on unsorted data; its correctness proof no longer applies.

Account for preparation:

Situation Appropriate conclusion
Data is already sorted and rarely mutated \(O(\log n)\) lookup can be useful
Data must be sorted for one lookup Sorting dominates the lookup
Many exact-key lookups, ordering unnecessary A dictionary is usually simpler
Small collection or infrequent lookup A linear scan may be sufficient

Keep binary search in the lab unless the application has a measured need for sorted storage.

Lab 3: Stable sorting

A sort is stable when records with equal keys keep their original relative order. Add a temporary priority field to lab data, then create tasks with equal priorities in a known insertion order.

Implement a stable merge sort and verify:

  1. output is ordered by priority;
  2. input is not accidentally lost or duplicated;
  3. equal-priority tasks retain insertion order;
  4. empty and single-item inputs work;
  5. the result matches Python's sorted for randomized inputs.

Derive its costs from the algorithm:

  • splitting produces \(O(\log n)\) levels;
  • merging processes \(O(n)\) elements per level;
  • total time is \(O(n \log n)\);
  • a straightforward implementation uses \(O(n)\) auxiliary space.

Use Python's stable sorted in application code. Your merge sort exists to teach invariants and analysis, not to replace a mature standard-library implementation.

Do not add dependencies to the task tracker merely to justify a graph. Use a separate fixture such as:

plan → implement → test → document
                 ↘ review ↗

Represent it as an adjacency mapping. Implement BFS with collections.deque and return both distance and parent mappings so a caller can reconstruct a shortest path by number of edges.

Test:

  • a direct neighbor;
  • multiple paths to the same node;
  • a cycle;
  • an unreachable node;
  • a missing start node;
  • a graph containing one isolated node.

State the representation when stating complexity. With an adjacency list, each reached vertex is queued once and each outgoing edge is examined once, giving \(O(V + E)\) time and \(O(V)\) auxiliary space. An adjacency matrix changes the traversal cost.

Benchmark the lookup choices

Benchmark linear, indexed, and binary lookup without including different work by accident.

For each approach:

  1. generate deterministic task collections at several increasing sizes;
  2. verify that all implementations return the same results;
  3. include present and absent IDs;
  4. measure index construction or sorting separately from lookup;
  5. repeat measurements and report the median and spread;
  6. record Python, operating system, processor, and benchmark command.

The standard library is enough:

from statistics import median
from timeit import repeat


def measure(operation, *, calls=1_000, repeats=7):
    samples = repeat(operation, number=calls, repeat=repeats)
    return {
        "median_seconds": median(samples),
        "minimum_seconds": min(samples),
        "maximum_seconds": max(samples),
    }

Choose calls so a sample lasts long enough to measure but does not waste time. Do not compare algorithms using different inputs, include setup in only one measurement, or report only the fastest run.

Interpret the result

Answer these questions before modifying the tracker:

  • At what collection size does lookup time become material to the whole command?
  • How many lookups are required before index construction pays for itself?
  • Does JSON loading and saving dominate all three lookup strategies?
  • What memory and consistency cost does the index introduce?
  • Is the tested workload representative of expected use?

An asymptotically faster operation can have no meaningful user impact when another \(O(n)\) step dominates. The correct decision may be to retain the list and record the condition that would justify revisiting it.

Evidence to keep

Add an algorithms/ lab directory or notebook-free script containing:

  • implementations and focused tests for the four labs;
  • predicted time and space costs before benchmarking;
  • benchmark input generation and raw measurements;
  • a small table or plot of lookup time versus collection size;
  • a decision note for the task tracker.

The decision note should state the workload, alternatives, evidence, choice, and revisit condition. “Dictionary lookup is \(O(1)\)” is not a complete decision.

Completion check

You are ready for the next module when you can:

  • derive every complexity claim from an operation count or invariant;
  • explain average versus worst-case dictionary lookup;
  • state and test binary search's sorted-input precondition;
  • demonstrate stability with equal-key records;
  • reconstruct a shortest unweighted path from BFS parents;
  • reproduce the benchmark and explain its sources of noise;
  • justify whether the task tracker should change based on end-to-end evidence.

Read only when needed

Continue with Module 4: Networks, APIs, and storage after the completion check passes.