Week 7 Student Exercises

Set up and run

Extract the lab code ZIP and work in its code folder. Use Python 3.11+ and the standard library.

python trace_lab.py --case rob
python verify.py
python verify.py --student

Predict the small example and its states on paper first. trace_lab.py traces the actual solutions.py implementation. before L… shows values immediately before that line executes: identify what the preceding executed line changed. Linked lists display a chain; tree nodes display their value and child values. Exclude tracing, copying, and printing overhead from the algorithm’s complexity.

Implement the functions and methods in student_week_07.py, then run verify.py --student. An initial NotImplementedError identifies work still to implement. Without --student, the verifier checks the supplied solutions. Use python trace_lab.py --case FUNCTION --student to inspect your implementation.

For each task record the input/output meaning, state invariant, one state transition, final answer, time, auxiliary space, and output space. Passing one small example does not establish correctness for all inputs.

This week’s problems

Worked solutions

198 322 62 1143

What information is needed to maximize inspection value when adjacent items cannot both be selected? Grid paths and common order in two event logs can also be divided into smaller problems.

Store and reuse previously computed optima or counts. The meaning of the state determines whether to add, minimize, or maximize.

DP state meaning and evaluation order

Dynamic programming stores and reuses answers to repeated subproblems. Define what one table entry means before choosing base cases and transitions.

Dependency directions in path-count and common-subsequence tables

Problem Meaning of a state Combination
Maximum nonadjacent sum Best value for a prefix max(select,skip)
Coins Minimum count for an amount min over final coins
Grid paths Number of paths reaching a cell top+left
Common subsequence Best length for two prefixes diagonal+1 on match; otherwise max

Time counts states times work per state. Space counts states retained simultaneously. The nonadjacent-sum problem needs only two prior states, but a table implementation is not automatically constant-space.

LeetCode 198: House Robber · Medium

Maximize selected value without selecting adjacent positions.

1 <= n <= 100; values 0..400.

Predict before implementing

At each house compare skip=current_best with take=best_two_back+value. Compute the new best before shifting the two states. Prefix optima are 2,7,11,11,12; the last answer selects 2+9+1.

rob([2, 7, 9, 3, 1],)
# 12

Idea and state transitions

198 · Idea and execution trace

LeetCode 198: House Robber · Medium

Maximize selected value without selecting adjacent positions.

Selecting the current value excludes its immediate predecessor. The best prefix value is therefore the larger of skipping the current value or adding it to the best prefix ending two positions earlier. Only those two prior results are needed for the next decision.

nums=[3,1,4,2]. Evaluate the entire right-hand side using old values before assignment.

value Old previous_two Old previous_one New previous_one
3 0 0 max(0,0+3)=3
1 0 3 max(3,0+1)=3
4 3 3 max(3,3+4)=7
2 3 7 max(7,3+2)=7

A recurrence table and its two variables

Let D[i] be the maximum sum from the first i values. For [3,1,4,2], the empty prefix has D[0]=0.

i and current value Skip current Take current D[i]
1, value 3 0 0+3 3
2, value 1 D[1]=3 D[0]+1=1 3
3, value 4 D[2]=3 D[1]+4=7 7
4, value 2 D[3]=7 D[2]+2=5 7

Before processing 4, previous_two=D[1] and previous_one=D[2]. After the update they become D[2] and D[3], preserving their roles for the next iteration. Taking the current value with D[i−1] could also take its neighbor, violating the constraint.

The branch taking 4 adds it to the already computed prefix optimum 3. Reusing that optimum rather than solving the prefix again is the DP step.

198 · Why it works; time and memory

Every optimum either selects the current item or skips it. Each case leaves an optimal prefix, so the recurrence covers all optima.

For each of n values, perform one addition, one max comparison, and a fixed number of assignments. With constant-cost arithmetic for the input range, time is O(n). Prior prefix optima are already computed rather than searched again.

Only two optima and the current value are retained, independent of n, giving O(1) auxiliary space. A full prefix table would use O(n); this implementation retains only the two dependencies. Reconstructing selected positions requires additional information.

Summing only even or only odd positions misses optimum 4 for [2,1,1,2].

nums=[3,1,4,2] → 7

Implement and execute

from collections import deque
import heapq

def rob(nums):
    previous_two = previous_one = 0
    for value in nums:
        previous_two, previous_one = previous_one, max(previous_one, previous_two + value)
    return previous_one
python trace_lab.py --case rob

Compare the trace return value with your prediction. Make the input change proposed above, find the first line where the state differs, and explain its effect on the answer.

LeetCode 322: Coin Change · Medium

Return the minimum coin count for amount, or -1 if impossible.

1..12 coins, values 1..231-1; amount 0..104; unlimited reuse.

Predict before implementing

Let dp[a] be the minimum coins for amount a; set dp[0]=0 and other entries unreachable. Evaluate increasing amounts from smaller predecessors. The table is 0,1,2,1,1,2,2; 3+3 beats greedy 4+1+1.

coin_change([1, 3, 4], 6)
# 2

Idea and state transitions

322 · Idea and execution trace

LeetCode 322: Coin Change · Medium

Return the minimum coin count for amount, or -1 if impossible.

If the last coin for amount a is c, the preceding coins must form an optimum for a-c. Compare every possible final coin. Choosing the largest coin first fails for amount 6 with [1,3,4]: 4+1+1 uses more coins than 3+3.

coins=[1,3,4], amount=6. Values are finalized after checking every coin for that total.

total Candidates dp[total-coin]+1 Final dp[total]
0 No coins needed 0
1,2 0+1 / 1+1 1,2
3 2+1, 0+1 1
4 1+1, 1+1, 0+1 1
5 1+1, 2+1, 1+1 2
6 2+1, 1+1, 2+1 2

322 · Why it works; time and memory

Removing the last coin c from an optimum leaves an optimum for a-c. Comparing all final coins finds the minimum; positive values ensure dependencies were filled earlier.

Each of A amount states checks m coins, giving at most A·m transitions. Each uses constant-time indexing, addition, and comparison, so time is O(Am). The outer bound is the numeric target A, not the number of coins.

The table has A+1 entries and other variables are constant-size, giving O(A) auxiliary space. Since A takes only O(log A) input bits, this is pseudopolynomial time in that bit length. The input coin list is not counted again as workspace.

Largest-first chooses 4+1+1 instead of 3+3 for [1,3,4],6. [2],3 gives -1; amount zero gives zero.

coins=[1,3,4], amount=6 → 2

Implement and execute

from collections import deque
import heapq

def coin_change(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total:
                dp[total] = min(dp[total], dp[total - coin] + 1)
    return -1 if dp[amount] == float("inf") else dp[amount]
python trace_lab.py --case coin_change

Compare the trace return value with your prediction. Make the input change proposed above, find the first line where the state differs, and explain its effect on the answer.

LeetCode 62: Unique Paths · Medium

Count grid paths using only right and down moves.

1 <= R,C <= 100; supplied inputs have answer at most 2×109.

Predict before implementing

A cell receives paths from above and left. In a one-row buffer, dp[col] still means above while dp[col-1] already means left. Rows become [1,1,1,1], [1,2,3,4], [1,3,6,10].

unique_paths(3, 4)
# 10

Idea and state transitions

62 · Idea and execution trace

LeetCode 62: Unique Paths · Medium

Count grid paths using only right and down moves.

With only right and down moves, the last move into a cell comes either from above or from the left. These cases have different last moves and are disjoint, so add their path counts rather than taking a maximum.

rows=3, cols=3. The first row and column have one possible route.

Cell processed Calculation Current dp rows
Initialize Boundary values 1 [1,1,1] / [1,1,1] / [1,1,1]
(1,1) 1+1=2 [1,1,1] / [1,2,1] / [1,1,1]
(1,2) 1+2=3 [1,1,1] / [1,2,3] / [1,1,1]
(2,1) 2+1=3 [1,1,1] / [1,2,3] / [1,3,1]
(2,2) 3+3=6 [1,1,1] / [1,2,3] / [1,3,6]

62 · Why it works; time and memory

Every path arrives from top or left. These disjoint classes cover all paths, so counts add; row order respects dependencies.

Initialization touches R·C cells; transitions fill (R-1)(C-1) cells. Two lookups and one addition per cell give O(RC) time. Paths are counted rather than enumerated, so runtime is not proportional to the number of paths.

Keeping the whole dp table uses O(RC) auxiliary space. This implementation is not the one-row O(C) optimization. Arithmetic is treated as constant within the official bounded-answer contract; unrestricted large grids would add large-integer bit costs.

[[1]*C]*R aliases rows; use a comprehension creating each row.

rows=2, cols=4 → 4

Implement and execute

from collections import deque
import heapq

def unique_paths(rows, cols):
    dp = [[1] * cols for _ in range(rows)]
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = dp[r-1][c] + dp[r][c-1]
    return dp[-1][-1]
python trace_lab.py --case unique_paths

Compare the trace return value with your prediction. Make the input change proposed above, find the first line where the state differs, and explain its effect on the answer.

LeetCode 1143: Longest Common Subsequence · Medium

Return the length of a longest common subsequence preserving order.

Each length 1..1000; lowercase English letters.

Predict before implementing

Define dp[i][j] for the two prefixes. Equal final characters extend the diagonal by one; unequal characters take the larger value after dropping one final character. Highlight the a,c,e diagonal extensions.

lcs('abcde', 'ace')
# 3

Idea and state transitions

1143 · Idea and execution trace

LeetCode 1143: Longest Common Subsequence · Medium

Return the length of a longest common subsequence preserving order.

Store answers for pairs of prefixes. If their final characters match, pair them and add one to the shorter-prefix answer. Otherwise they cannot be paired with each other, so take the better result from omitting either final character.

first="abc", second="ac". Rows and columns are prefixes of the two strings.

Completed row Empty prefix a ac
Empty prefix 0 0 0
a 0 1 (=0+1) 1 (=max(0,1))
ab 0 1 (=max(1,0)) 1 (=max(1,1))
abc 0 1 (=max(1,0)) 2 (=1+1)

The answer 2 is the length of ac. Skipping b distinguishes a subsequence from a contiguous substring.

1143 · Why it works; time and memory

Equal final characters can be paired in an optimum. Unequal ends cannot both be the final match, so at least one is skipped; maximize over both cases.

For lengths n and m, there are (n+1)(m+1) prefix pairs. Each interior cell uses one character comparison and an addition or max, giving O(nm) time. It becomes O(n2) only when the two lengths have the same scale.

The full table uses O(nm) auxiliary space, while the returned length occupies O(1). Reconstructing an actual common subsequence would require traceback and output-character storage.

A subsequence preserves character order while allowing characters to be skipped. Skipping b in “abc” gives “ac”, so their longest common subsequence has length 2.

first="abca", second="aca" → 3

When both final characters are c, an optimal subsequence can be chosen to match those final positions. A subsequence using neither final position can be extended by c; a match using an earlier c can move to the final c without changing order. This is why the matching case needs only the diagonal optimum plus one.

Implement and execute

from collections import deque
import heapq

def lcs(first, second):
    rows, cols = len(first), len(second)
    dp = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(1, rows + 1):
        for c in range(1, cols + 1):
            if first[r-1] == second[c-1]:
                dp[r][c] = dp[r-1][c-1] + 1
            else:
                dp[r][c] = max(dp[r-1][c], dp[r][c-1])
    return dp[rows][cols]
python trace_lab.py --case lcs

Compare the trace return value with your prediction. Make the input change proposed above, find the first line where the state differs, and explain its effect on the answer.

Lab report

Include the small-input state table, completed code, your own boundary input and expected result, and verification results. Explain time by total operation counts and space by simultaneously live state. Include any input copying or sorting costs.