The question this layer answers
How should information be organized and transformed efficiently?
Procedures that scale. This layer connects Arrays, Trees, Graphs, Complexity to the rest of the computing stack.
Start with a contract, then choose an algorithm
Given a sorted array a and target x, define lower bound as the first index i with a[i] ≥ x, or the length n when no such element exists. This contract handles duplicates and missing values without special guessing. It differs from returning any matching index.
lo = 0
hi = length(a)
while lo < hi:
mid = lo + floor((hi - lo) / 2)
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
Maintain two facts: every index below lo contains a value less than x, and every index at or above hi contains a value at least x. Initially both regions are empty. Sortedness makes each update safe. The interval length decreases, so termination is guaranteed. At exit lo = hi and the two facts establish the required boundary.
For a = [2, 4, 4, 9, 13] and x = 4:
| lo | hi | mid | a[mid] | Update |
|---|
| 0 | 5 | 2 | 4 | hi = 2 |
| 0 | 2 | 1 | 4 | hi = 1 |
| 0 | 1 | 0 | 2 | lo = 1 |
It returns 1. An empty array returns 0 without any access. A target larger than every element returns n. Each iteration roughly halves the remaining interval, giving O(log n) comparisons with constant-time indexed access. That access assumption matters for linked lists.
A plausible local choice can be globally wrong
With coin denominations 1, 3, and 4, greedily taking the largest coin for amount 6 gives 4 + 1 + 1: three coins. The optimum is 3 + 3: two coins. A counterexample is enough to reject “largest first is always optimal.”
Dynamic programming uses best[0] = 0 and, for t > 0, best[t] = 1 + min(best[t − c]) over allowed coins c ≤ t whose smaller amounts are reachable. Compute in increasing t order. The final coin of an optimal solution leaves a smaller subproblem; choosing the best of every possible final coin explains why the recurrence is correct. Store the selected coin too if you need to reconstruct the solution.
Analysis is about resources under a model
For maximum amount T and k denominations, that implementation uses O(Tk) time and O(T) space. Since T is a numeric value, this is not polynomial in the number of bits needed to encode T; it is often called pseudopolynomial. Complexity statements need an input measure.
Your next step: test duplicates, emptiness, and boundary targets in the search lab. For every algorithm, pair a correctness argument with a resource argument. Fast wrong answers and unbounded correct procedures solve different problems from the one specified.
Free Algorithms & data structures lessons
Choose for operations, constraints, and evidence
An array buys constant-time indexing and locality but makes middle insertion expensive. A hash table buys expected constant-time key lookup but gives up natural ordering and needs a collision policy. A balanced tree keeps ordered operations logarithmic. A heap exposes only the next priority cheaply. The workload, not the name, decides.
A hash function maps keys to buckets; collisions must be resolved; the table must keep load controlled through resizing or another policy. Expected constant time assumes hashes distribute the actual keys well and adversaries cannot force pathological clustering. Equality still confirms the key.
Invariants, growth rates, and honest analysis
A loop invariant supports correctness; a decreasing measure supports termination. Time and space analysis count how work grows with input size. Worst case gives a bound, amortized analysis spreads rare expensive operations across a sequence, and expected analysis depends on a probability model.
In a sorted array, the candidate interval contains every location where the target could still be. One comparison removes roughly half of it while preserving that invariant. After k steps at most n/2^k candidates remain, so k grows like log₂n. A boundary convention such as [low, high) keeps empty ranges and updates precise.
Search, sort, and graph traversal patterns
Sorting creates order that accelerates later operations. Breadth-first search explores an unweighted graph by distance layers and finds shortest hop counts. Depth-first search follows a path before backtracking, exposing reachability, cycles, and dependency structure. Both require a visited discipline on graphs with cycles.
If records are sorted by team and later stably sorted by score, equal-score records retain their previous team order. Stability therefore composes ordering decisions. Whether it matters depends on the product contract, not merely algorithm trivia.
Greedy choices, dynamic programming, and proof
Greedy algorithms commit to a locally best choice and need an exchange or cut argument proving no optimal solution is lost. Dynamic programming stores solutions to overlapping subproblems; its central act is defining a state that contains exactly the information the future needs. Both are proof-driven design patterns.
For edit distance, state (i,j) means the optimal cost to transform the first i source symbols into the first j target symbols. Delete, insert, and match/replace transitions point to smaller states. Once that recurrence and base cases are correct, memoization or tabulation chooses the evaluation order.
Separate a cost model from a stopwatch
Prove a bound over every operation sequence
Connect an implementation invariant to a decision tree
Make expected constant time a precise claim
Different invariants buy different operations
Maintain discovery state and detect impossible schedules
Choose the algorithm from edge-weight assumptions
Prove that a locally cheap connection is globally safe
Recover an optimal decision, not just its score
Know exactly which local choice is safe
Practice lab: Prove a search and break a greedy rule
About 40 minutes. Use arrays indexed from zero, comparisons, loops, and integer division. Review the programming primer if these are new.
Search sorted array [2, 4, 7, 9, 13, 18, 21] for 13 using half-open bounds low = 0, high = 7. While low < high, let mid = floor((low + high)/2). If a[mid] < target, set low = mid + 1; otherwise set high = mid. On exit, check low < length and a[low] = target.
- Trace (low, high, mid) for target 13 and absent target 8. State what the exit index means.
- Explain why the array must be sorted and why the interval shrinks. Give the time bound in terms of n array entries.
- A greedy coin algorithm takes the largest available denomination. For coins {1, 3, 4}, find a target where it fails to minimize coin count. Write a recurrence for a dynamic-programming repair.
Hint
This binary search finds a lower bound: the first position whose value is at least the target. For coins, try a target just above 4.
Worked solution
For 13: (0,7,3), (4,7,5), (4,5,4), then low = high = 4, a match. For 8: (0,7,3), (0,3,1), (2,3,2), then index 3 contains 9, so 8 is absent. All indices below low hold values less than the target; all indices at or above high hold values at least the target. Sorted order makes each discarded region safe. The interval shrinks by about half: O(log n) comparisons and O(1) extra space. With target 6, greedy gives 4+1+1 (three coins), but 3+3 uses two. Let D(0)=0 and D(t)=1+min D(t−c) over coins c ≤ t; evaluate t in increasing order. For m denominations and target T this costs O(Tm) time and O(T) space.
- Check bounds before dereferencing the exit index.
- Name sortedness, the invariant, and the progress measure.
- Give a real greedy counterexample and meaningful DP base case.
Change one assumption
Trace an empty array and a target larger than every element. Then explain why a binary search over an unsorted array has no such guarantee.
Prove the algorithm, then account for its cost
Use explicit invariants and counterexamples. Count the work of the specified implementation, including resizing, collisions, and reconstruction.
1. Derive and compare · allow 35 minutes
A fast-looking loop with a quadratic bill
An algorithm appends n items to an array. Policy A increases capacity by one whenever full; policy B doubles capacity, starting at one. Copying one item costs one unit and writing the new item costs one unit. Derive the exact total cost for A. Bound B for arbitrary positive n, including an append that triggers resizing. Explain why a single expensive operation does not contradict amortized constant cost. Separately solve T(n)=2T(n/2)+n for powers of two with T(1)=1.
Get a starting hint
Draw the capacities at which copying occurs. For the recurrence, count the work at each depth.
Compare your reasoning with the worked solution
A copies 0+1+…+(n−1)=n(n−1)/2 items and performs n writes, for n(n+1)/2 units. B copies capacities 1,2,…,2^k, where 2^k is the last full capacity before n items have been inserted. For n>1 their sum is 2^(k+1)−1<2n; adding n writes gives fewer than 3n units. For n=1 the cost is one. A particular append can still cost Θ(n): amortization bounds the total of every prefix of the operation sequence, without making a probabilistic assumption.
The recurrence has log₂n non-leaf levels, each doing n combining work, and n leaves costing one each. Thus T(n)=n log₂n+n. This bound assumes the two recursive subproblems really have half the size and the combine stage is linear; it is not a license to call every recursive algorithm n log n.
Check your reasoning
- Count copies and writes separately.
- Bound arbitrary prefixes, not just a full power-of-two capacity.
- State the assumptions behind the recurrence.
2. Trace and prove · allow 40 minutes
Stability, heaps, and what a lower bound permits
Records arrive as (key, arrival): (2,A),(1,B),(2,C),(1,D). Show a stable ascending-key result. An in-place heapsort uses a max-heap and swaps its root with the last unsorted item. Explain why this does not guarantee stability, and give a concrete trace using just two equal-key records. Derive the comparison-tree lower bound for sorting n distinct keys. Why can counting sort escape it? When is a balanced search tree a better abstraction than a heap?
Get a starting hint
Equal keys are indistinguishable to the comparator but their records can still move. A binary decision tree needs enough leaves for every permutation.
Compare your reasoning with the worked solution
The stable result is (1,B),(1,D),(2,A),(2,C). With [(2,A),(2,C)], the array is already a valid max-heap; the root-to-end swap produces [(2,C),(2,A)]. The sorted keys are correct but arrival order is reversed. Stability can be obtained by comparing (key,arrivalIndex), at the cost of storing or retaining the index, or by choosing a stable algorithm.
There are n! possible total orders of distinct inputs. A comparison decision tree therefore needs at least n! leaves and height at least ⌈log₂(n!)⌉=Ω(n log n). Counting sort uses integer keys as array indices, so it is outside the comparison-only model; its Θ(n+k) time and Θ(k) count storage depend on the key range k. A heap efficiently exposes an extreme but does not keep all keys in search order. Use a balanced search tree when predecessor, range iteration, and arbitrary-key search are required, with suitable duplicate-key handling.
Check your reasoning
- Show a concrete stability failure.
- Specify distinct keys and comparison-only access in the lower bound.
- Choose a data structure by operations, not by a single complexity slogan.
3. Adversarial analysis · allow 30 minutes
When constant-time lookup becomes a chain
A chained hash table has m=8 buckets and h(k)=k mod 8. Insert 0,8,16,24,32,40,48,56 at the head of each chain. Count equality comparisons to find 0 and to reject 64. Explain why resizing alone may fail against a caller who knows the new modulus. Propose defenses for an Internet-facing map and state what each defense does not guarantee.
Get a starting hint
Compute the actual bucket occupancy. Distinguish an expected bound under a hash-family assumption from a worst-case bound.
Compare your reasoning with the worked solution
Every key occupies bucket zero. Head insertion leaves 56 at the front and 0 at the end, so finding 0 and rejecting 64 each take eight key comparisons. Generalizing to n colliding keys gives Θ(n) lookup and potentially Θ(n²) insertion work if duplicate checking scans the chain. A load factor of one says nothing about this skew.
After a predictable resize, a caller can select multiples of the new bucket count. A suitably keyed hash makes intentional collisions harder when the key remains secret, but does not create a deterministic constant bound and cannot stop oversized legitimate requests. A balanced-tree fallback can bound bucket search by O(log n) under a total-order comparator. Limits on key length, entry count, request CPU time, and per-client traffic bound other costs. Key comparison and hashing themselves may be linear in string length. Evaluate both random workloads and deliberately colliding or long inputs; document which randomness and attacker knowledge support the expected bound.
Check your reasoning
- Trace bucket order correctly.
- Separate average occupancy from collision distribution.
- Include input-size costs and a bounded-resource defense.
4. Trace and refute · allow 45 minutes
A dependency graph is not a shortest-path algorithm
Let directed edges be s→a (2), s→b (5), b→a (−4), a→t (2), b→t (10). Trace Dijkstra if it permanently finalizes the smallest tentative distance. Give the correct shortest s→t path. Show how a topological-order algorithm solves this graph despite the negative edge. Then add t→b (1): identify a negative cycle and explain the consequence for shortest walks. Distinguish BFS, topological sorting, and weighted shortest paths.
Get a starting hint
In the original graph, b must be processed before a in any topological ordering. Inspect the weight of b→a→t→b.
Compare your reasoning with the worked solution
Dijkstra finalizes s at 0, a at 2, then t at 4, before b at 5. The path s→b→a→t actually costs 5−4+2=3. The proof that a finalized distance cannot improve relies on nonnegative edges, so the −4 edge breaks it. A DAG order s,b,a,t relaxes b before a: distances become b=5, a=min(2,1)=1, t=min(15,3)=3. Acyclicity makes this method valid even with negative weights.
Adding t→b creates b→a→t→b with total −4+2+1=−1. It is reachable from s and can reach t. Repeating it makes the cost to t arbitrarily negative, so no minimum-cost walk exists. Bellman–Ford can detect a reachable negative cycle; merely returning one finite distance would be misleading. BFS minimizes edge count in an unweighted graph. Topological sorting orders a DAG and detects that cycles prevent such an order. Weighted shortest-path algorithms optimize a sum and require assumptions appropriate to their method.
Check your reasoning
- Show the failed finalization, not just the correct answer.
- Use a valid topological order.
- Explain why a reachable negative cycle affects this destination.
5. Prove and test · allow 35 minutes
The cut argument and equal-weight choices
An undirected graph has AB=1, AC=1, BC=1, BD=3, CD=2, AD=5. Run Kruskal with alphabetical tie-breaking, compute total weight, and give a different minimum spanning tree. Prove that a lightest edge crossing a cut is safe for some MST extending a compatible partial forest. Why does “safe” not mean “belongs to every MST”? What changes if the graph is disconnected?
Get a starting hint
Exchange the chosen edge with a crossing edge on the path between its endpoints in an existing tree.
Compare your reasoning with the worked solution
Kruskal accepts AB and AC, rejects BC because it closes a cycle, then accepts CD. Total weight is 1+1+2=4. AB,BC,CD is another MST of weight four. Every spanning tree on these four vertices has three edges. At least one is incident to D and costs at least two; each of the other two edges costs at least one. Therefore every spanning tree costs at least four, establishing the lower bound without assuming A,B,C are connected internally.
For the cut property, take an MST T containing the current forest, where the cut respects that forest. If the lightest crossing edge e is absent, adding it creates a cycle. The T-path between its endpoints crosses the cut at another edge f. No forest edge crosses this cut, so f is not required by the partial forest. Since w(e)≤w(f), replacing f by e preserves a spanning tree and cannot raise weight; minimality then gives an MST containing e. Equal weights allow distinct choices, so e need not occur in every MST. On a disconnected graph, the algorithm produces a minimum spanning forest, not a spanning tree of the whole vertex set.
Check your reasoning
- Respect the partial forest in the exchange proof.
- Handle ties without claiming uniqueness.
- State the disconnected-graph result.
6. Dynamic programming and exchange · allow 50 minutes
Recover the choices, not only the optimum value
Jobs have (start,finish,value): A=(0,3,5), B=(1,2,3), C=(2,4,4), D=(3,5,4), E=(4,6,6). Jobs ending exactly when another starts are compatible. Sort by finish time, compute predecessor p(j), fill M(j)=max(M(j−1),value(j)+M(p(j))), and reconstruct an optimal set. Give a counterexample to earliest-finish greedy for weighted scheduling using these jobs. Explain why earliest-finish is nevertheless correct for maximizing the number of intervals.
Get a starting hint
Keep the include/exclude decision or compare the two alternatives during backtracking. The unweighted exchange argument replaces an earliest selected interval with one ending no later.
Compare your reasoning with the worked solution
The finish order is B,A,C,D,E. With M(0)=0, predecessors are p(B)=0, p(A)=0, p(C)=B, p(D)=A, p(E)=C. Values are M(B)=3, M(A)=5, M(C)=7, M(D)=9, M(E)=13. Backtracking includes E because 6+7>9, includes C because 4+3>5, and includes B. The compatible set B,C,E has value 13.
Earliest-finish greedy also happens to choose B,C,E on this full instance, so this particular run is not a counterexample. Restrict to A and B: greedy chooses B with value three, while A is worth five. Recognizing the distinction between a successful example and a general proof is part of the exercise. For the unweighted objective, take any optimal schedule and replace its first interval by a globally earliest-finishing one. It ends no later, so all later intervals remain feasible and the number selected does not fall. Apply the same argument to the remaining compatible intervals. The exchange preserves cardinality, but it does not preserve total value; that is exactly where the weighted proof fails.
Check your reasoning
- Use endpoint compatibility consistently.
- Reconstruct B,C,E and value 13.
- Identify the objective that the exchange preserves.
Study the underlying methods
Section project: Build and justify a shortest-route toolkit
6 to 8 hours. Implement graph search with explicit correctness and cost evidence. Input is a directed graph encoded as JSON adjacency lists with nonnegative integer edge weights, a source, and a target. Output is either an unreachable result or a path, its total weight, and counters for explored vertices and relaxed edges. Implement breadth-first search for the special case where every edge has weight one, and Dijkstra’s algorithm using the standard-library heap for general nonnegative weights. Maintain predecessor information so the returned route is an actual witness, not merely a distance. Handle parallel edges deliberately and define how missing vertex identifiers are rejected. For tiny graphs, compare answers with a slower independent reference, such as exhaustive simple-path enumeration. Write a proof explaining why Dijkstra may finalize the smallest tentative distance and exactly where nonnegative weights are used. Benchmark sparse and dense generated graphs using operation counts as well as wall time. The goal is to connect representation, algorithm choice, invariant, output certificate, and measured cost. Use reproducible graph-generation seeds and publish the generated instance sizes. Explain why equal optimal costs can correspond to different valid paths, and avoid rejecting a correct implementation merely for a different tie choice.
Milestones
- Define graph validation and path-output formats, including unreachable and source-equals-target cases.
- Implement BFS and Dijkstra with predecessor reconstruction and stale-heap-entry handling.
- Write the central correctness argument and a counterexample for negative weights.
- Build a tiny independent oracle and compare generated instances.
- Measure sparse and dense graph families and relate counters to asymptotic bounds.
Acceptance criteria
- Every returned path starts and ends at the requested vertices, uses real edges, and sums to the reported cost.
- BFS and Dijkstra agree on distances for every tested unit-weight graph.
- All tiny generated graphs agree with the independent exhaustive reference on reachability and optimal cost.
- Negative weights are rejected before search rather than silently processed with an invalid proof assumption.
- An unreachable target returns an explicit unreachable result, while source equal to target returns a zero-cost one-vertex path.
- A graph that creates multiple tentative distances for one vertex is handled correctly despite stale priority-queue entries.
Add A* with a stated admissible heuristic and demonstrate both a valid heuristic and a deliberately invalid one that loses the optimality guarantee.
Practise Algorithms & data structures free →