R06 · Week 6 Recall & Drill

Assessment scope

Attempt the recall prompts before reading the worked drill and answer explanations. The worked examples below restore the combined teaching task, with explicit contracts and checks; a local model is distinguished from a reproduced external service. The minute allocations are adjustable practice suggestions, not evidence of learning speed.

Sessions covered

• S026 — Stacks & Queues — LIFO/FIFO in Practice
• S027 — Recursion — Call Stack, Base Case, Worked Examples
• S028 — Trees & BSTs — Traversal (BFS/DFS)
• S029 — Heaps & Priority Queues
• S030 — Graphs — Representation, BFS, DFS, Shortest Path

By the end of this revision you can

1. Distinguish LIFO and FIFO removal policies from their possible storage implementations and explain the shortest-hop guarantee of queue-based BFS.

2. Write the monotonic-stack pattern and say why it turns a quadratic next-greater scan into a linear one.

3. Identify the base case, recursive case, and shrinking argument in a specified recursion, and explain why cached Fibonacci has only linearly many states while other memoized problems may not.

4. Traverse a tree four ways and say which order each problem needs — in-order for sorted BST output, post-order for bottom-up aggregation, level-order for depth.

5. State the heap invariant precisely and explain why it says nothing about siblings or array order beyond the root.

6. Choose BFS, Dijkstra, or topological sort correctly, and explain why BFS still finds shortest hops but need not find minimum total weight.

90-min structure

Treat this as an adjustable practice budget: 5 minutes to recall the five subjects, 30 for the blank-page questions, 30 for the worked drill, 15 to compare answers and test a counterexample, and 10 to record a gap and plan an unseen retest. The solutions and transfer exercises can take longer; the goal is correct reasoning, not racing a timer.

Blank-page reconstruction · 30 min

S026 · Stacks & Queues

1. State LIFO and FIFO in one sentence each, and name the correct Python container for each.
2. Explain the monotonic-stack pattern in two sentences, and say what invariant the stack maintains.
3. Implement a queue using two stacks, and state the amortised cost per operation.

S027 · Recursion

1. Name the three ingredients of every correct recursion, and identify each one in a factorial implementation.
2. Explain why naive Fibonacci is exponential, and how a cache decorator collapses it to linear.
3. Inspect Python's configured recursion limit, explain bounded-depth recursion and compare an explicit stack with the risks of raising the limit.

S028 · Trees & BSTs

1. State the BST invariant in one sentence, precisely enough that it excludes the common wrong version.
2. Name the four traversal orders and give one problem that specifically needs each.
3. Explain why databases use B-trees rather than binary search trees.

S029 · Heaps & Priority Queues

1. State the min-heap invariant, then say what it does not tell you.
2. Explain why a binary heap lives in a flat array, and write the index arithmetic for parent and children.
3. Explain why finding the top K of n items with a size-K heap beats sorting everything.

S030 · Graphs

1. Name the three representations and say which is the default in real code, with the density argument.
2. Explain when a traversal needs visited state, including a cyclic graph and a child-only tree traversal as contrasting cases.
3. Outline Kahn's algorithm for topological sort, and say what it produces when the graph has a cycle.

Hands-on drill · 30 min

Task: build one small graph and attack it with every algorithm from this week — BFS, DFS, Dijkstra, topological sort — writing each from memory.

Step 1 — the graph (5 min)

# graph.py
# Weighted directed acyclic graph. A -> F has one direct edge that is
# expensive, and a longer chain that is cheaper. This is the case that
# separates "fewest edges" from "lowest cost".
GRAPH: dict[str, list[tuple[str, int]]] = {
    "A": [("B", 1), ("C", 4), ("F", 20)],
    "B": [("C", 2), ("D", 5)],
    "C": [("D", 1), ("E", 3)],
    "D": [("E", 1), ("F", 6)],
    "E": [("F", 2)],
    "F": [],
}

Step 2 — BFS and DFS from memory (8 min)

# traverse.py
from collections import deque
 
 
def bfs_fewest_edges(start: str, goal: str) -> list[str] | None:
    """Fewest EDGES, ignoring weight entirely."""
    queue = deque([(start, [start])])
    visited = {start}
    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path
        for nxt, _weight in GRAPH[node]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, path + [nxt]))
    return None
 
 
def dfs_all_reachable(start: str) -> set[str]:
    """Iterative DFS with an explicit stack — no recursion limit to hit."""
    stack, visited = [start], set()
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for nxt, _weight in GRAPH[node]:
            if nxt not in visited:
                stack.append(nxt)
    return visited
 
 
if __name__ == "__main__":
    print("bfs A->F :", bfs_fewest_edges("A", "F"))
    print("reachable:", sorted(dfs_all_reachable("A")))

Expected outcome: BFS returns the two-node path ['A', 'F'], because that is genuinely the fewest edges — and it is also the most expensive route at cost 20. Reachable is all six nodes. Note what just happened: BFS gave a correct answer to the question it was asked and a wrong answer to the question you probably meant.

Step 3 — Dijkstra, which asks the right question (10 min)

# dijkstra.py
import heapq
 
 
def dijkstra(start: str, goal: str) -> tuple[int, list[str]] | None:
    # (cost, counter, node, path) — the counter is the tiebreaker that stops
    # Python from comparing arbitrary node payloads when costs tie.
    if any(w < 0 for edges in GRAPH.values() for _, w in edges):
        raise ValueError("nonnegative weights required")
    counter = 0
    heap = [(0, counter, start, [start])]
    best: dict[str, int] = {}
    while heap:
        cost, _c, node, path = heapq.heappop(heap)
        if node in best:          # lazy deletion: first pop wins, rest are stale
            continue
        best[node] = cost
        if node == goal:
            return cost, path
        for nxt, weight in GRAPH[node]:
            if nxt not in best:
                counter += 1
                heapq.heappush(heap, (cost + weight, counter, nxt, path + [nxt]))
    return None
 
 
if __name__ == "__main__":
    print("dijkstra A->F:", dijkstra("A", "F"))

Expected outcome: Dijkstra returns a cost strictly below 20 along a multi-hop path, not the single direct edge. Work the arithmetic by hand before running it and confirm the program agrees with your paper answer — that manual check is the drill. The lesson to write down: BFS was not slower here, it was answering a different question.

Step 4 — topological sort and cycle detection (7 min)

# toposort.py
from collections import deque
 
 
def kahn(graph: dict[str, list[tuple[str, int]]]) -> list[str] | None:
    indeg = {n: 0 for n in graph}
    for node in graph:
        for nxt, _w in graph[node]:
            indeg[nxt] += 1
    queue = deque(sorted(n for n, d in indeg.items() if d == 0))
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt, _w in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)
    # Fewer nodes emitted than exist means something never reached in-degree 0.
    return order if len(order) == len(graph) else None
 
 
if __name__ == "__main__":
    print("topo order:", kahn(GRAPH))
 
    cyclic = {k: list(v) for k, v in GRAPH.items()}
    cyclic["F"] = [("A", 1)]          # close the loop
    print("topo on cyclic graph:", kahn(cyclic))

Expected outcome: the first call emits all six nodes in a dependency-respecting order starting at A. The second returns None. That None is the important half: Kahn's algorithm is a cycle detector as well as a sorter, and the detection is free — if the queue empties before every node is emitted, the remaining nodes include cycle vertices and may also include acyclic descendants blocked by a cycle. This is how a build system tells you that your dependencies are circular.

Independent checks, queue and monotonic frontier

Read the graph, traversal, Dijkstra and topological-sort Python fences as consecutive sections of one file; their original module boundaries no longer require imports from uncreated files. All vertices must be dictionary keys and edges point to declared vertices. The original graph's cheapest path is A→B→C→D→E→F with cost 1+2+1+1+2=7; BFS instead returns the one-edge cost-20 path. The following checks also cover the simpler cost-six fixture from the assessment version, an isolated vertex and a cycle with a blocked acyclic descendant.

assert bfs_fewest_edges("A", "F") == ["A", "F"]
assert dijkstra("A", "F") == (7, ["A", "B", "C", "D", "E", "F"])
assert dfs_all_reachable("A") == set(GRAPH)
order = kahn(GRAPH); pos = {v: i for i, v in enumerate(order)}
assert all(pos[u] < pos[v] for u, edges in GRAPH.items() for v, _ in edges)
assert kahn({"a": [("b", 1)], "b": [("a", 1), ("c", 1)], "c": []}) is None
GRAPH = {"A": [("F", 20), ("B", 2)], "B": [("C", 2)],
         "C": [("F", 2)], "F": [], "isolated": []}
assert dijkstra("A", "F")[0] == 6
assert dijkstra("A", "isolated") is None
assert len(kahn(GRAPH)) == 5
 
class TwoStackQueue:
    def __init__(self):
        self.incoming, self.outgoing = [], []
    def put(self, value):
        self.incoming.append(value)
    def get(self):
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())
        if not self.outgoing:
            raise IndexError("empty queue")
        return self.outgoing.pop()
 
q=TwoStackQueue()
for x in [1, 2, 3]: q.put(x)
assert q.get() == 1
q.put(4)
assert [q.get(), q.get(), q.get()] == [2, 3, 4]
 
def next_greater(values):
    answers = [None]*len(values); stack = []
    for i, value in enumerate(values):
        while stack and values[stack[-1]] < value:
            answers[stack.pop()] = value
        stack.append(i)
    return answers
assert next_greater([2, 2, 1, 3]) == [3, 3, 3, None]

Each queue item moves incoming→outgoing once, so the total transfer work over N items is O(N), even though one dequeue can take linear time. Each next-greater index is pushed once and popped at most once; the stack retains unresolved nonincreasing values. Equal values are not strictly greater, hence the strict comparison. A maximum queue can keep a separate nonincreasing deque of candidate values, discard smaller tail candidates on arrival, and discard a front candidate when that value departs; keep duplicate maxima or store counts so one departure does not erase another equal maximum.

Maximum queue: finish the amortization argument

Keep the ordinary FIFO queue as well as the candidate deque: candidates alone cannot identify every departing item. This implementation assumes totally ordered values (not NaN), retains equal maxima, and raises IndexError on empty get/max.

class MaxQueue:
    def __init__(self):
        self.items, self.candidates = deque(), deque()
    def put(self, value):
        self.items.append(value)
        while self.candidates and self.candidates[-1] < value:
            self.candidates.pop()
        self.candidates.append(value)
    def get(self):
        value = self.items.popleft()
        if value == self.candidates[0]:
            self.candidates.popleft()
        return value
    def maximum(self):
        return self.candidates[0]
 
mq = MaxQueue()
for value in [3, 3, 1]: mq.put(value)
assert mq.get() == 3 and mq.maximum() == 3
assert mq.get() == 3 and mq.maximum() == 1
assert mq.get() == 1

A smaller tail candidate is dominated by a newer, larger value that leaves the FIFO no earlier; it cannot become the maximum before that newer value departs. Each occurrence enters each deque once and leaves at most once. Thus N operations take O(N) total deque work and O(N) worst-case storage, although one put can remove many candidates. Changing < to <= without counts loses duplicate maxima: after inserting 3,3 and removing one 3, another maximum must remain.

Recursion, trees and heap answer key

Factorial on nonnegative integers stops at 0, multiplies by n in the recursive case, and decreases n by one; reject negatives instead of recursing forever. Naive Fibonacci recomputes fib(n−2) both directly and inside fib(n−1); its call-count recurrence is T(n)=T(n−1)+T(n−2)+1, giving exponential growth. Cached Fibonacci computes each reachable argument once: for n≥2 these are 0 through n. It has O(n) distinct states but O(n) call depth and growing-integer arithmetic costs. Memoization does not turn every exponential recursion into linear work: the number and size of states matter. Inspect sys.getrecursionlimit() rather than treating 1,000 as a language constant. Prefer an iterative algorithm for unbounded depth; raising the limit is platform-sensitive and not a universal fix.

For the tree root 2 with children 1 and 3: preorder is 2,1,3; inorder 1,2,3; postorder 1,3,2; level order 2,1,3. Preorder helps serialize with null markers; postorder computes subtree heights from children; inorder is sorted only for a BST with a specified duplicate policy; BFS exposes levels. A BST's entire left/right subtrees must obey its bounds, not only direct children. Balanced multiway B/B+ trees reduce page accesses through high fanout; not every database index uses that structure.

A binary heap is a complete binary tree: levels are filled left to right, so breadth-first positions occupy a contiguous array without explicit child pointers or internal gaps. A zero-index min-heap has parent index (i-1)//2 and children 2i+1,2i+2; each existing child is no smaller than its parent. It is not a sorted array. For 1≤k≤n, a size-k heap can retain k largest items with O(n log(k+1)) worst-case comparison cost and O(k) heap storage; k=0 needs an explicit empty answer, and sorting may be competitive for large k. Producing sorted top-k output adds O(k log k). A tie-break counter avoids comparing payload objects.

Adjacency lists use O(V+E), matrices O(V²), and edge lists are convenient for algorithms scanning all edges. For sparse graphs, adjacency lists are a common default because neighbor iteration costs the vertex’s degree rather than V; for dense graphs or frequent edge-existence queries, a matrix can be suitable. This is a workload choice, not a universal claim about real implementations. Visited state prevents repeated exploration in general cyclic graphs; trees traversed only toward children do not need a set, so “every traversal needs one” is false. BFS remains correct for shortest hops even with weighted edges present; it need not minimize total weight. Standard Dijkstra finalization needs nonnegative weights (zero is allowed). A DAG can use topological relaxation even with negative edges; Bellman–Ford handles general negative edges and detects reachable negative cycles, where finite shortest walks may not exist. A* additionally needs appropriate heuristic and reopening assumptions.

The demonstrative BFS/Dijkstra code copies whole paths. Their storage and time therefore exceed the usual parent-pointer implementations; this teaching version does not claim the optimized textbook bounds. Kahn's initial sorting adds O(V log V) here; removing the deterministic sort yields O(V+E) with ordinary queue operations.

Traversal implementations and memoized recursion

The three-node traversal answers are a start, not an implementation. Represent a finite, child-only binary tree as (value, left, right) with None for an empty child. These routines assume no shared subtrees or cycles. All four traversals visit n nodes in O(n) time plus output storage; recursion uses O(height) stack and level order uses O(maximum width) queue space.

from functools import cache
import sys
 
@cache
def fib(n):
    if type(n) is not int or n < 0:
        raise ValueError('nonnegative integer required')
    return n if n < 2 else fib(n-1) + fib(n-2)
 
def depth_order(root, order):
    if order not in ('pre', 'in', 'post'):
        raise ValueError('unknown traversal')
    result = []
    def walk(node):
        if node is None:
            return
        value, left, right = node
        if order == 'pre': result.append(value)
        walk(left)
        if order == 'in': result.append(value)
        walk(right)
        if order == 'post': result.append(value)
    walk(root)
    return result
 
def level_order(root):
    if root is None:
        return []
    result, queue = [], deque([root])
    while queue:
        value, left, right = queue.popleft()
        result.append(value)
        if left is not None: queue.append(left)
        if right is not None: queue.append(right)
    return result
 
tree = (4, (2, (1, None, None), (3, None, None)), (5, None, None))
assert depth_order(tree, 'pre') == [4,2,1,3,5]
assert depth_order(tree, 'in') == [1,2,3,4,5]
assert depth_order(tree, 'post') == [1,3,2,5,4]
assert level_order(tree) == [4,2,5,1,3]
assert depth_order(None, 'in') == level_order(None) == []
fib.cache_clear()
assert fib(10) == 55 and fib.cache_info().currsize == 11
assert sys.getrecursionlimit() > 0  # inspect; do not raise it as a fix

Preorder is node-left-right, inorder left-node-right, and postorder left-right-node. BFS processes a level before the next. A general tree need not yield sorted inorder; the global BST bounds make that claim possible. In a plain BST, lookup costs O(height), which can be O(n) after sorted inserts. Balancing is an additional algorithm, not a property of the word 'tree'.

LIFO removes the most recently added item (list append/pop is a common implementation); FIFO removes the earliest remaining item (deque append/popleft). The storage need not be identical. In recursive factorial the base is n=0, the smaller problem n−1, and the combination n times its result; the domain must exclude negative n. General recursion can be simulated with explicit frames containing both pending work and partial results. This moves state rather than eliminating memory use; not every recursion needs the same frame structure.

Retest with solution: on the graph A→B cost 0 and A→C cost 2, B→C cost 1, BFS reaches C in one hop but Dijkstra returns cost 1 via B. Zero-weight edges do not break Dijkstra's nonnegative-weight proof. A negative-edge input is rejected by this implementation before even returning a start-equals-goal result. In Kahn's method a cycle A↔B with B→C blocks C too, although C itself is not on a cycle.

Answer constraints and corrections

Shortest hop count and shortest weighted cost are different objectives. Dijkstra here assumes nonnegative weights. A valid topological order contains every declared vertex once and respects every directed edge; a short Kahn output detects a cycle. Queue amortization counts each element transfer, not nested loop syntax.

Gap analysis + next week preview · 10 min

Score each original recall question separately: explain unaided; explain with a hint; or not yet. A fluent verbal answer is not a successful implementation. Choose one failed concept, write a counterexample that distinguishes the mistaken rule from the correct one, and schedule an unseen retest. Keep successes as well as failures in the log so the plan does not become a list of increasingly familiar problems.

For the drill, require an explicit input contract, a correctness argument or domain assumption, one ordinary case, one boundary case and an independent expected result. A chart, compile success or passing sample alone does not meet that rubric. Use the stated input contracts and named runtime when interpreting a result; finite tests and timing samples are not universal correctness or performance guarantees.

Next week (S031–S035) finishes DSA and opens databases: sorting with merge and quicksort and when to trust the built-in; binary search as the pattern behind a whole family of problems; dynamic programming with memoisation and tabulation; greedy versus backtracking; and then the relational model with tables, keys, and normalisation. The memoisation instinct you drilled in S027 is precisely the bridge into dynamic programming.

Corrective source notes

• Breadth First Search - Algorithms for Competitive Programming — BFS gives shortest edge-count paths, not general minimum-weight paths. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• Dijkstra - finding shortest paths from given vertex - Algorithms for Competitive Programming — The standard Dijkstra proof requires nonnegative weights, including zero. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• Topological Sorting - Algorithms for Competitive Programming — Topological ordering exists precisely for directed acyclic graphs. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• heapq — Heap queue algorithm — Python 3.14.8 documentation — Heap ordering is parent-child, not total array or sibling ordering. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization avoids repeated subproblem computation; the lesson counts Fibonacci states, not a universal speedup. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.

The cited passages support these named claims. The algebra, counterexamples and executable fixtures supply the lesson-specific reasoning; finite checks are not universal benchmarks.