R07 · Week 7 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

• S031 — Sorting — Merge, Quick, and When to Trust the Built-in
• S032 — Binary Search — the Pattern Behind 100 Problems
• S033 — Dynamic Programming — Memoisation & Tabulation
• S034 — Greedy & Backtracking — When to Use Each
• S035 — The Relational Model — Tables, Keys, Normalisation

By the end of this revision you can

1. Compare merge, quick, and heap sort on the three axes that actually decide the choice: worst case, auxiliary memory, and stability.

2. Write both binary search templates from memory and explain why their loop conditions and boundary updates differ.

3. Recognise the 'minimum X such that a predicate holds' phrasing as a binary search on the answer.

4. Apply the four-step DP recipe — state, transition, base case, fill order — and distinguish a valid state recurrence from merely adding a cache.

5. Give an exchange argument for activity selection, a coin-change counterexample and the choose-recurse-unchoose template for shared mutable state.

6. Normalise a denormalised table to third normal form and name the anomaly each step removes.

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

S031 · Sorting

1. Fill in the table for merge, quick, and heap sort: average time, worst-case time, auxiliary space, stable or not.
2. Define a stable sort and give one concrete case where stability changes the answer rather than just the ordering.
3. You have far more records than fit in memory. Describe how you sort them.

S032 · Binary Search

1. Write both templates from memory, and say why one uses hi = mid while the other uses hi = mid - 1.
2. Explain the overflow bug in the naive midpoint calculation and write the safe form.
3. Give one problem that is not "find a value in a sorted list" but is still solved by binary search.

S033 · Dynamic Programming

1. Describe state decomposition and repeated subproblems, distinguishing optimization, counting and feasibility recurrences.
2. State the four-step recipe, then apply it to the coin-change problem out loud.
3. Explain the trade-off between memoisation and tabulation, and when you would specifically want each.

S034 · Greedy & Backtracking

1. State the greedy-choice property in one sentence, and pair a problem where greedy works with a near-identical one where it fails.
2. Write the backtracking template as three ordered lines, and say when shared mutable state needs undo and when persistent state avoids it.
3. Give a sound pruning condition, its proof and a case where exponential worst-case search remains.

S035 · The Relational Model

1. Define primary key, foreign key, and referential integrity in one sentence each.
2. Explain an update anomaly with a concrete example, and say which normal form eliminates it.
3. Give one situation where you would deliberately denormalise a production system, and what you accept in exchange.

Hands-on drill · 30 min

Task: compare greedy with memoized and tabulated DP, write a separate backtracking search, then normalize a schema and let the database reject bad data.

Step 1 — coin change, three ways (12 min)

The coin set below is chosen specifically because greedy fails on it.

# coins.py
import functools
 
 
def greedy(coins: list[int], amount: int) -> int | None:
    """Take the biggest coin that fits, repeatedly. Fast, and sometimes wrong."""
    if amount < 0 or any(c <= 0 for c in coins):
        raise ValueError("nonnegative amount and positive coins required")
    remaining, used = amount, 0
    for c in sorted(coins, reverse=True):
        take, remaining = divmod(remaining, c)
        used += take
    return used if remaining == 0 else None
 
 
def memoised(coins: list[int], amount: int) -> int | None:
    """Top-down DP. State = remaining amount. Transition = subtract one coin."""
    if amount < 0 or any(c <= 0 for c in coins):
        raise ValueError("nonnegative amount and positive coins required")
    @functools.lru_cache(maxsize=None)
    def best(rem: int) -> float:
        if rem == 0:
            return 0
        if rem < 0:
            return float("inf")
        return 1 + min((best(rem - c) for c in coins), default=float("inf"))
 
    result = best(amount)
    return None if result == float("inf") else int(result)
 
 
def tabulated(coins: list[int], amount: int) -> int | None:
    """Bottom-up DP. Same recurrence, fill order inverted, no recursion depth."""
    if amount < 0 or any(c <= 0 for c in coins):
        raise ValueError("nonnegative amount and positive coins required")
    INF = float("inf")
    table = [0] + [INF] * amount
    for target in range(1, amount + 1):
        for c in coins:
            if c <= target and table[target - c] + 1 < table[target]:
                table[target] = table[target - c] + 1
    return None if table[amount] == INF else int(table[amount])
 
 
if __name__ == "__main__":
    COINS = [1, 3, 4]
    for amount in (6, 8, 11):
        print(
            f"amount={amount:>3}  greedy={greedy(COINS, amount)}  "
            f"memo={memoised(COINS, amount)}  table={tabulated(COINS, amount)}"
        )

Expected outcome: the two DP columns always agree with each other. At amount 6 greedy reports a worse (larger) count than the DP columns, because taking the 4 first strands you on two 1s, while two 3s is better. That divergence is the entire lesson: greedy does not solve the stated exact optimization problem here (no approximation guarantee was established), and nothing in the greedy code can tell you so. Work out by hand which amounts should diverge before running it.

Step 2 — binary search on the answer (8 min)

Coin change required comparing competing choices; the shipping problem offers a different shortcut. Increasing capacity cannot make the required number of days increase, so feasibility changes only from false to true as capacity rises. That monotonic boundary, not the success of a locally greedy choice, licenses binary search. The tell is the phrasing "minimum capacity such that the job finishes in D days".

# capacity.py
def min_capacity(weights: list[int], days: int) -> int:
    if not weights or days < 1 or any(w <= 0 for w in weights):
        raise ValueError("nonempty positive weights and positive days required")
    def days_needed(cap: int) -> int:
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used += 1
                load = 0
            load += w
        return used
 
    lo, hi = max(weights), sum(weights)   # bounds, not guesses
    while lo < hi:                        # Template B: hi = mid, never mid - 1
        mid = lo + (hi - lo) // 2
        if days_needed(mid) <= days:
            hi = mid                      # feasible — try smaller
        else:
            lo = mid + 1                  # infeasible — must go bigger
    return lo
 
 
if __name__ == "__main__":
    w = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    for d in (1, 5, 10):
        print(f"days={d:>2}  min capacity={min_capacity(w, d)}")

Expected outcome: with one day the answer is the total of all weights, since everything must ship at once. With as many days as there are items the answer is the largest single weight, since nothing can be split. The middle case lands strictly between those two bounds. Those two endpoints are checkable by hand, which is exactly why they make good tests — and note that lo and hi are derived bounds, not guesses.

Step 3 — let the schema reject bad data (10 min)

The last step moves from algorithms to the relational model. In the shipping search, correctness depended on preserving a feasible boundary; here it depends on preserving valid relationships between stored rows. Uniqueness, foreign keys, and checks put those rules in the database, so each deliberately bad insert tests a rule without relying on every caller to remember it.

import sqlite3
con = sqlite3.connect(":memory:")
con.execute("PRAGMA foreign_keys = ON")     # sqlite needs this switched on
 
con.executescript("""
CREATE TABLE instructors (
    id    INTEGER PRIMARY KEY,
    name  TEXT NOT NULL,
    email TEXT NOT NULL UNIQUE
);
 
CREATE TABLE courses (
    id            INTEGER PRIMARY KEY,
    title         TEXT NOT NULL,
    instructor_id INTEGER NOT NULL REFERENCES instructors(id),
    credits       INTEGER NOT NULL CHECK (credits BETWEEN 1 AND 6)
);
""")
 
con.execute("INSERT INTO instructors VALUES (1, 'Ada', 'ada@example.com')")
con.execute("INSERT INTO courses VALUES (1, 'Compilers', 1, 4)")
 
for label, sql in [
    ("duplicate email",   "INSERT INTO instructors VALUES (2,'Bob','ada@example.com')"),
    ("missing instructor","INSERT INTO courses VALUES (2,'Ghost',99,3)"),
    ("bad credits",       "INSERT INTO courses VALUES (3,'Huge',1,99)"),
]:
    try:
        con.execute(sql)
        raise AssertionError(f"{label}: constraint missing")
    except sqlite3.IntegrityError as e:
        print(f"{label:<20} rejected: {type(e).__name__}")
con.close()

Expected outcome: all three inserts are rejected, each by a different constraint — the unique index, the foreign key, and the check. Inspect PRAGMA foreign_keys to verify enforcement on your connection. A build with enforcement enabled by default need not behave like one where it defaults off. That is not a database quirk to memorise, it is the general lesson — a constraint you did not enable is a constraint you do not have, and the application layer will not notice.

Sorting, search and schema derivations

Typical stable array mergesort uses O(n log n) worst-case time and O(n) auxiliary storage; ordinary in-place quicksort is expected O(n log n) with suitable pivots, O(n²) worst case and a recursion stack whose depth depends on partition balance; ordinary heapsort is O(n log n) worst case, O(1) auxiliary storage and unstable. For the standard versions just described, mergesort and heapsort also take O(n log n) average time. Quicksort's usual partitioning is unstable; its recursion stack is O(log n) for balanced partitions and can reach O(n) for a naive degenerate recursion. Mergesort is stable only when equal keys are merged in original order. These describe implementations, not immutable properties of every variant. Python sorting is stable: sorting records by secondary key then primary key preserves secondary order among equal primaries. External sorting makes bounded sorted runs, then merges them; disk/network I/O and merge fan-in matter. For a concrete stability-dependent answer, first order candidates by arrival time, then stably sort by descending score and select the first winner. With Ada arriving before Bob and both scoring 9, Ada must win; an unstable second sort could choose Bob, violating the tie policy. Sorting once by (-score, arrival_time) is an alternative that makes both keys explicit.

A closed exact-match search keeps candidates in [lo,hi] and removes mid after a failed comparison. A lower-bound search keeps a possible insertion boundary in [lo,hi] and uses hi=mid when mid might be the answer. Both must decrease the interval. Python integers do not overflow at a machine-word boundary, but lo+(hi-lo)//2 is a useful fixed-width habit under appropriate bounds. The shipping predicate is monotone for nonnegative capacities and positive ordered weights: increasing capacity cannot increase the minimum days required. Its greedy packing puts the longest feasible prefix into each day; an earlier cut cannot pack more into the remaining days.

Coin DP state is remaining amount; transition takes one positive coin; base is zero coins for amount zero; tabulation follows increasing amount. Cached recursion avoids repeated reachable states but can hit Python depth limits. Choose top-down memoization when the reachable subset is sparse or its recurrence is easiest to express recursively; tabulation avoids that call stack and permits predictable fill order and rolling storage when dependencies allow it, but may fill states never needed by a query. “Optimal substructure” is the optimization form of a valid recurrence; counting and feasibility DPs need correct state/transition decomposition without an optimization objective. Memoizing a pure computation does not become incorrect merely because subproblems do not overlap; it may simply provide no speedup. Backtracking chooses, recurses and restores shared mutable state; persistent state can avoid explicit undo. Pruning must prove the removed branch cannot contain a needed solution, not merely seem unpromising.

The greedy-choice property means at least one optimal solution begins with the proposed local choice; a valid residual subproblem then lets that argument repeat. For unweighted activity selection, exchange the first activity of an optimal schedule with one finishing no later: the remaining compatible schedule still fits. Repeating proves earliest-finish greedy is optimal under that contract. Weighted activity selection invalidates that objective argument. Sorting by start time can choose [0,10) and block both [1,2) and [2,3); earliest finish instead selects the latter two. Assume nonempty half-open intervals, with touching endpoints compatible, and maximize the number selected rather than their total duration or value. Coin denominations [1,3,4] similarly show that a plausible local choice is insufficient proof.

For an enrollment table keyed by (student_id,course_id), student_name depends only on student_id and course_title/instructor_id only on course_id; instructor_email depends on instructor_id. Split into Students, Enrollments, Courses and Instructors with foreign keys. Partial dependencies violate 2NF; the transitive non-key dependency motivates the instructor split for 3NF. More precisely, each nontrivial dependency X→A in 3NF has X a superkey or A a prime attribute. These decompositions reduce repeated facts and associated insert/update/delete anomalies; there is not a one-to-one anomaly assigned to each normal form. Denormalized analytical tables still need refresh and consistency rules, not a claim that anomalies become impossible. Partial unique indexes can encode active-email uniqueness where supported, but account reuse is a product/security decision, not a mandatory consequence of soft deletion.

Independent finite oracles

# Continue after the coin and capacity definitions above.
import itertools
for amount in range(13):
    brute = min((sum(counts) for counts in itertools.product(range(13), repeat=3)
                 if sum(c*n for c,n in zip([1,3,4], counts)) == amount), default=None)
    assert memoised([1,3,4], amount) == tabulated([1,3,4], amount) == brute
assert greedy([1,3,4], 6) == 3 and tabulated([1,3,4], 6) == 2
assert tabulated([2], 3) is None
for weights in ([1], [1,2,3], [3,1,2,4]):
    for days in range(1, len(weights)+1):
        # Independent oracle: enumerate every placement of cuts between items.
        possible=[]
        for bits in itertools.product([0,1], repeat=len(weights)-1):
            groups=[weights[0]]
            for cut, w in zip(bits, weights[1:]):
                if cut: groups.append(w)
                else: groups[-1]+=w
            if len(groups)<=days: possible.append(max(groups))
        assert min_capacity(list(weights), days) == min(possible)
items=[(2,3),(3,4),(4,5)]
for capacity in range(10):
    dp=[0]*(capacity+1)
    for weight,value in items:
        for c in range(capacity,weight-1,-1):
            dp[c]=max(dp[c],dp[c-weight]+value)
    brute=max(sum(items[i][1] for i in range(3) if mask>>i&1)
              for mask in range(8)
              if sum(items[i][0] for i in range(3) if mask>>i&1)<=capacity)
    assert dp[capacity]==brute

The oracle enumerates subsets rather than repeating the capacity recurrence. Reverse capacity order reads the previous-item row; forward order would permit reuse. These bounded checks do not establish performance at arbitrarily large amount/capacity.

Two complete search templates and a backtracking solution

Both searches require sorted nondecreasing input. Exact match returns any matching index or None; lower bound returns the first insertion position whose value is at least the target, possibly len(values). Duplicates make the contract distinction visible.

def exact_match(values, target):
    lo, hi = 0, len(values)-1
    while lo <= hi:
        mid = lo + (hi-lo)//2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid+1
        else:
            hi = mid-1
    return None
 
def lower_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = lo + (hi-lo)//2
        if values[mid] < target:
            lo = mid+1
        else:
            hi = mid
    return lo
 
assert exact_match([], 2) is None
assert exact_match([1,2,2,4], 2) in (1,2)
assert exact_match([1,2,2,4], 3) is None
assert lower_bound([1,2,2,4], 2) == 1
assert lower_bound([1,2,2,4], 5) == 4
assert lower_bound([], 5) == 0
 
def subsets_with_sum(values, target):
    # Contract: distinct positive integers; return combinations, not permutations.
    if len(set(values)) != len(values) or any(v <= 0 for v in values):
        raise ValueError('distinct positive values required')
    choices = sorted(values)
    result, path = [], []
    def visit(start, remaining):
        if remaining == 0:
            result.append(tuple(path))
            return
        for i in range(start, len(choices)):
            value = choices[i]
            if value > remaining:
                break  # sorted positives: every later choice is also too large
            path.append(value)       # choose
            visit(i+1, remaining-value)  # recurse, each position used at most once
            path.pop()               # unchoose before exploring the sibling
    visit(0, target)
    return result
 
assert subsets_with_sum([1,2,3,4], 5) == [(1,4), (2,3)]
assert subsets_with_sum([], 0) == [()]
assert subsets_with_sum([2,4], 3) == []

For exact match, all possible matches remain in the closed interval; each nonmatching midpoint is removed. For lower bound, all positions before lo are too small and all positions at or beyond hi are large enough; hi itself may be the answer, so hi=mid preserves it. Both ranges shrink. A half-open empty interval correctly gives insertion position zero.

Two concrete nontermination checks explain the original quiz without claiming measured “most likely” bug frequencies. In lower_bound([1,2], 2), replacing lo=mid+1 by lo=mid eventually leaves lo=0, hi=1, mid=0 forever. Keeping hi=mid but changing the guard to lo<=hi also loops on [2], target 2 at lo=hi=mid=0. A bounds invariant and strict progress justify a template; memorization alone is not its proof. For shipping, sum(weights) is a feasible upper bound because days≥1; the loop does not detect an all-infeasible domain on its own.

Backtracking copies a solution only when remaining reaches zero. Advancing the start index prevents reuse and permutation duplicates. Its oversize pruning is sound because choices are sorted and positive; with negative values, a later choice could repair an overshoot, so this proof fails. Undo restores the shared path for sibling calls. Worst-case work/output can remain exponential (there can be exponentially many subsets); pruning is not a polynomial-time guarantee.

The coin and shipping functions above have integer-domain preconditions: positive integer denominations/weights, nonnegative integer amount, and positive integer days. Their value checks are not a complete runtime type validator; callers still must honor the domain. Empty coins solve amount zero and no positive amount. Shipping preserves input order and cannot split an item. Its middle sample answer is 15 for five days, not merely an unspecified value between 10 and 55.

Normalization as a worked dependency exercise

Suppose enrollment rows repeat (student_id, student_name, course_id, course_title, instructor_id, instructor_email, grade) and the key is (student_id, course_id). Assume one instructor per course and one current name/email per person. A candidate normalized design is:

• Students(student_id primary key, student_name).
• Instructors(instructor_id primary key, instructor_email unique and not null).
• Courses(course_id primary key, course_title, instructor_id foreign key).
• Enrollments(student_id foreign key, course_id foreign key, grade, composite primary key).

The dependencies are student_id → student_name, course_id → course_title,instructor_id, instructor_id → instructor_email, and (student_id,course_id) → grade. Atomic values and no repeating groups establish the intended 1NF representation; separating attributes dependent on only part of the enrollment key removes partial dependencies (2NF); separating instructor email removes the transitive dependency from course ID (3NF). Joining on the declared keys reconstructs each enrollment without spurious combinations under these assumptions.

Before decomposition, changing Ada's email in only one enrollment creates inconsistent facts; deleting her last enrollment can lose the only instructor record; adding an instructor without an enrollment is awkward. Afterward, edit one Instructors row, retain it independently, and let foreign keys reject unknown IDs. A primary key uniquely identifies a row and cannot be NULL under the intended schema; a foreign key requires a referenced key for non-NULL references. In SQLite use explicit NOT NULL where needed, because historical non-INTEGER primary-key behavior has exceptions. Deliberate reporting denormalization exchanges simpler reads for refresh, staleness and reconciliation responsibilities.

Answer constraints and corrections

At amount six greedy uses three coins, while 3+3 uses two. Knapsack direction enforces single use; changing the recurrence or base values changes the problem. A database constraint must express the actual invariant, and foreign-key enforcement is engine/configuration-specific.

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 (S036–S040) goes deep into SQL: the basic select-where-order shape; joins including the anti-join; aggregations with grouping, filtering on aggregates, and subqueries; window functions; and common table expressions including recursive ones. The relational model you just normalised is the thing all of that syntax operates on — keys and dependencies are why joins work at all.

Corrective source notes

• Third Normal Form — University of Winnipeg database notes — For nontrivial dependencies in 3NF, the determinant is a superkey or the dependent attribute is prime; the lesson applies this to explicit enrollment dependencies. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• Sorting Techniques — Python 3.14.8 documentation — Python stable sorting preserves equal-key relative order. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• Binary Search - Algorithms for Competitive Programming — Binary search applies to a monotone Boolean transition; lesson derives shipping feasibility. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• Knapsack Problem - Algorithms for Competitive Programming — Descending 0/1-knapsack capacity prevents reusing the current item. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• SQLite Foreign Key Support — Foreign key enforcement is connection/configuration dependent and should be explicitly enabled/checked. Source retrieved 2026-10-07; passage and applicability reviewed 2026-10-07.
• sqlite-constraints official reference — SQLite CHECK permits NULL, unlike NOT NULL; the lesson uses both. 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.