R07 · Week 7 Recall & Drill

Weekly revision · Week 7 · Covers 5 sessions from Mon–Fri.

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

90-min structure

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.

Gotcha you probably forgot: quicksort's worst case is quadratic, and it is triggered by already-sorted input under a naive pivot choice — the exact case people assume is easiest. Real implementations defend with randomised or median-of-three pivots, and hybrid sorts fall back to heapsort once recursion goes too deep. This is a large part of why you should use the language's built-in rather than your own.

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.

Gotcha you probably forgot: the two failure modes are an infinite loop and an off-by-one, and they come from the same place — a boundary update that fails to shrink the search space. If lo can equal mid and you assign lo = mid, the range stops shrinking and the loop spins forever. Pick one template, memorise it exactly, and stop improvising the boundaries.

S033 · Dynamic Programming

1. Name the two properties a problem must have before DP applies at all.
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.

Gotcha you probably forgot: in the one-dimensional knapsack optimisation you must iterate capacity backwards. Going forwards lets the same item be used more than once, because you would read a cell that has already been updated in this item's pass — silently solving the unbounded problem instead of the zero-or-one problem. The direction of the loop is the constraint.

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 why the undo step is mandatory.
3. Explain why pruning is the difference between backtracking being feasible and being useless.

Gotcha you probably forgot: in activity selection you sort by end time, not start time. Sorting by start time seems intuitive and is wrong — an activity that starts early but runs long blocks everything after it. Ending earliest leaves the most remaining room, and that is exactly the structural property the exchange argument uses to prove the greedy optimal.

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.

Gotcha you probably forgot: with soft deletes, a plain uniqueness constraint on email breaks — a user who deletes their account and signs up again collides with their own tombstoned row. The standard fix is a partial unique index that applies only where the deleted timestamp is null, so uniqueness is enforced among live rows only.

Hands-on drill · 30 min

Task: attack one problem with all three paradigms, watch greedy fail on real input, then normalise 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.

mkdir -p ~/projects/w7-drill && cd ~/projects/w7-drill

# coins.py
import functools
 
 
def greedy(coins: list[int], amount: int) -> int | None:
    """Take the biggest coin that fits, repeatedly. Fast, and sometimes wrong."""
    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."""
    @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."""
    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 is not an approximation here, it is simply wrong, 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)

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:
    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)

python - <<'PY'
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)
        print(f"{label:<20} ACCEPTED  <-- constraint missing!")
    except sqlite3.Error as e:
        print(f"{label:<20} rejected: {type(e).__name__}")
PY

Expected outcome: all three inserts are rejected, each by a different constraint — the unique index, the foreign key, and the check. Now comment out PRAGMA foreign_keys = ON and rerun: the orphan course is accepted. 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.

Gap analysis + next week preview · 10 min

• Did you predict which coin amounts would make greedy diverge before running Step 1? If not, you are pattern-matching on "greedy looks reasonable" rather than checking the greedy-choice property.
• Did both binary search endpoint cases come out as you expected? Endpoint reasoning is the fastest available check on a search you just wrote.
• Which constraint in Step 3 would you have forgotten to write? That is the one that will reach production in a real schema.

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.

Part of the 6-month evergreen learning plan.