W02: From invariants to algorithm design

Prerequisites and observable goals#

One pattern underneath several algorithms#

An algorithm is not a list of code lines to memorize. It is a way to move from a state where little is known to a state where the requested property is established. An invariant records the knowledge preserved between steps. A dependency order tells us when a subanswer is ready to use. A decreasing measure or acyclic order explains why the process ends. These ideas connect loops, recursive functions, dynamic programming, and graph algorithms.

Choose the mathematical specification first. “Return the first index whose value is at least the target” is more precise than “do binary search.” It handles duplicates and a target larger than every element. A half-open array interval $[\ell,r)$ includes $\ell$ but excludes $r$; its length is $r-\ell$. That representation lets an empty search range satisfy $\ell=r$ without inventing a valid element at that index.

Deriving a boundary search#

For a sorted array $a$ of length $n$ and target $t$, maintain

Only valid array indices are quantified in the last two statements. Initially $\ell=0,r=n$; the two known regions are empty. With $\ell<r$, choose $m=\ell+\lfloor(r-\ell)/2\rfloor$. If $a_m<t$, sortedness proves all indices through $m$ too small, so set $\ell=m+1$. Otherwise all indices from $m$ onward are large enough, so set $r=m$. Each branch discards a region justified by sortedness and keeps the invariant true.

At termination $\ell=r$. Every earlier valid index is too small, and every later valid index is large enough. Thus $\ell$ is exactly the requested boundary, possibly $n$. The nonnegative measure $r-\ell$ decreases on every iteration. This establishes termination separately from the boundary property. Removing sortedness destroys the implication that permits discarding half the array; extensive testing on unsorted arrays cannot repair that missing proof assumption.

Trace $a=[1,3,3,8]$, $t=3$. Start $[0,4)$, midpoint 2 has 3, so $r=2$. Midpoint 1 has 3, so $r=1$. Midpoint 0 has 1, so $\ell=1$. The final interval is empty at 1, the first position with value at least 3. Returning an arbitrary matching midpoint would answer a different specification.

A dynamic program is a recurrence plus an evaluation order#

Consider a directed acyclic graph (DAG) with edge weight $w(u,v)$ and source $s$. The shortest distance is

for reachable nonsource vertices, with unreachable predecessors ignored. In a DAG no path returns to the source, so initialization is consistent even if the source has incoming edges from unreachable vertices. The empty path gives distance zero at $s$. A vertex with no reachable predecessor has no finite distance.

The recurrence is not yet an algorithm: using an unfinished predecessor could propagate a wrong answer. A topological order places the start of every edge before its end. Process vertices in that order, relaxing outgoing edges. When processing $u$, all paths reaching $u$ end in predecessors already processed. An inductive argument therefore establishes that its current distance is final. Negative edges are allowed because the proof uses acyclicity, not nonnegativity. Cycles invalidate this evaluation order, even if a particular cyclic graph has well-defined shortest paths.

Worked counterexample: when method selection matters#

Take vertices $s,a,b,t$ and edges

A valid topological order is $s,b,a,t$. Process $s$ to obtain tentative $d(a)=2,d(b)=5$. Process $b$ to improve $d(a)$ to $5-4=1$. Process $a$ to set $d(t)=3$. The path is $s,b,a,t$.

A usual Dijkstra implementation that finalizes the smallest tentative vertex might finalize $a$ at 2 and $t$ at 4 before processing $b$ at 5. The negative edge later reveals a better route to a supposedly final vertex. This is not proof that Dijkstra is poor software; it is a proof that its nonnegative-edge hypothesis matters. Bellman–Ford offers a different method for general weighted directed graphs, with a different complexity and negative-cycle reasoning. Selecting a DAG method is both simpler and more efficient when the acyclicity premise is available.

Representation affects the implemented work#

An adjacency list visits each vertex and edge a bounded number of times in topological sorting and relaxation, giving $O(V+E)$ graph-operation work. Constructing and checking input also costs work. If weights and distances are unbounded integers, arithmetic cost grows with bit length; constant-time addition is an explicit machine-word model, not a mathematical truth. Sorting the ready queue after every step would add unnecessary cost. A queue suffices for any valid topological order; a heap buys a specific tie-breaking order at extra cost.

A returned path adds a second specification. Store the predecessor that achieved a strict improvement, then walk backward from the target. An unreachable target should return no path rather than a fabricated empty route that looks like success. The path’s edges, summed weight, and endpoints supply an independent certificate of a feasible route. Optimality still depends on the invariant or a valid comparison algorithm; a path of weight 3 alone does not prove no path weighs 2.

Amortized cost is a bound on a sequence#

A dynamic array that doubles capacity may copy $1,2,4,\ldots,2^k$ elements across many appends. Their sum is $2^{k+1}-1$, not $n$ copies on every append. Including ordinary writes, $n$ appends cost $O(n)$ total under fixed-size elements and a conventional allocator model. That gives constant amortized cost per append, while an individual resizing append can still cost $\Theta(n)$. A real-time frame deadline cares about the expensive individual event, not just the amortized average. Reserving capacity or choosing another structure changes latency at the cost of memory or complexity.

Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

Complete solutions: W02#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""W02: shortest paths on a DAG, allowing negative integer edge weights."""
from collections import deque


def shortest_paths(n, edges, source):
    if type(n) is not int or not 1<=n<=10000 or type(source) is not int or not 0<=source<n:
        raise ValueError("bounded valid vertices required")
    edges=list(edges)
    if len(edges)>100000:
        raise ValueError("too many edges")
    adjacent=[[] for _ in range(n)]
    incoming=[0]*n
    seen=set()
    for u,v,w in edges:
        if any(type(x) is not int for x in (u,v,w)) or not 0<=u<n or not 0<=v<n:
            raise ValueError("valid integer endpoints and weight required")
        if (u,v) in seen: raise ValueError("parallel edges excluded in this lab")
        seen.add((u,v));adjacent[u].append((v,w));incoming[v]+=1
    ready=deque(i for i in range(n) if incoming[i]==0)
    order=[]
    while ready:
        u=ready.popleft();order.append(u)
        for v,_ in adjacent[u]:
            incoming[v]-=1
            if incoming[v]==0:ready.append(v)
    if len(order)!=n:raise ValueError("graph is not acyclic")
    distance,previous=[None]*n,[None]*n
    distance[source]=0
    for u in order:
        if distance[u] is None:continue
        for v,w in adjacent[u]:
            candidate=distance[u]+w
            if distance[v] is None or candidate<distance[v]:
                distance[v]=candidate;previous[v]=u
    return distance,previous,order


def path(previous, source, target):
    if not 0<=source<len(previous) or not 0<=target<len(previous):
        raise ValueError("invalid endpoint")
    result=[];seen=set();current=target
    while current is not None:
        if current in seen:raise ValueError("invalid cyclic predecessor data")
        seen.add(current);result.append(current)
        if current==source:return list(reversed(result))
        current=previous[current]
    return None


if __name__=='__main__':
    d,p,order=shortest_paths(4,[(0,1,2),(0,2,5),(2,1,-4),(1,3,2)],0)
    print(d,order,path(p,0,3))

Retention and readiness#

Derive one invariant from a final specification without looking at code. Explain why DAG shortest paths permits negative edges while standard Dijkstra requires nonnegative weights. Distinguish total, worst-case individual, and measured operation costs in your own engine examples.