Week 6 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 can_finish
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_06.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

207 210 78 39

A pipeline stops when its jobs wait on each other. Find a feasible execution order, then enumerate the choices that can be made from a given set of items.

Use remaining prerequisites to schedule jobs. Choose, recurse, and restore to keep one search branch from changing the next.

Edge direction and adjacency lists

[after,before] means before must finish before after can begin. Store the edge before → after. indegree counts unfinished prerequisites.

Tasks 1 and 2 follow 0, and both precede task 3

Stored item Value in this graph Meaning
graph [[1,2],[3],[3],[]] Tasks affected when each task finishes
indegree [0,1,1,2] Remaining prerequisite counts
Initial queue [0] Tasks ready now

The graph stores E edge entries. Unlike a V-by-V matrix, an adjacency list uses storage proportional to V+E.

LeetCode 207: Course Schedule · Medium

Decide whether all courses can be completed under prerequisite constraints.

1 <= V <= 2000; 0 <= E <= 5000; pairs [after,before], no duplicate pairs.

Predict before implementing

Build prerequisite→course edges and incoming counts. Only zero-indegree vertices enter the queue. This cycle has no initial ready course; processed count stays zero. Remove [0,2] to make all three processable.

can_finish(3, [[1, 0], [2, 1], [0, 2]])
# False

Idea and state transitions

207 · Idea and execution trace

LeetCode 207: Course Schedule · Medium

Decide whether all courses can be completed under prerequisite constraints.

If no remaining course can start, look for circular waiting. Repeatedly remove zero-prerequisite courses and check whether all courses were removed. Any nonempty remainder contains a directed cycle.

n=3, prerequisites=[[1,0],[2,1],[1,2]]: 0 → 1, 1 → 2, 2 → 1

Stage indegree queue Processed
Initial [0,2,1] [0] []
Complete 0 [0,1,1] [] [0]
Stop 1 and 2 wait on each other [] 1 course < 3

course_order returns [] rather than a partial order; can_finish returns False.

Implement and execute

from collections import deque
import heapq

def can_finish(n, prerequisites):
    return len(course_order(n, prerequisites)) == n
python trace_lab.py --case can_finish

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 210: Course Schedule II · Medium

Return any prerequisite-respecting order, or an empty list if impossible.

1 <= V <= 2000; 0 <= E <= V(V-1); distinct endpoints and unique [after,before] pairs.

Predict before implementing

Append each ready course to the order before reducing its successors’ indegrees. Course 3 becomes ready only after both 1 and 2. Validate every edge using positions; [0,2,1,3] is also valid.

course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
# [0, 1, 2, 3]

Idea and state transitions

210 · Idea and execution trace

LeetCode 210: Course Schedule II · Medium

Return any prerequisite-respecting order, or an empty list if impossible.

Instead of rechecking every prerequisite repeatedly, store each task’s remaining prerequisite count. A count of zero means it can run now. Completing a task decrements only the counts of tasks that depend on it.

n=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]. Edges point before → after.

Completed node indegree (0,1,2,3) queue order
Initial [0,1,1,2] [0] []
0 [0,0,0,2] [1,2] [0]
1 [0,0,0,1] [2] [0,1]
2 [0,0,0,0] [3] [0,1,2]
3 [0,0,0,0] [] [0,1,2,3]

210 · Why it works; time and memory

A course enters only after all prerequisites were removed, so every before precedes after in the result. A short result cannot be a complete order.

Initialization stores V vertices and E edges in O(V+E) work. Each vertex enters the queue once; each edge is read once when its source is processed. Degrees vary, but their sum is E, giving total O(V+E) time.

There are V adjacency lists with E entries, plus up to V entries in indegree, queue, and order. Total extra space is O(V+E), including O(V) output order. Although 207 returns only a bool, this implementation calls the same order routine and uses O(V+E) space.

Reading [[1,0]] as 1→0 reverses the dependency. Validate edges instead of comparing with one chosen valid order.

n=4, prerequisites=[[2,0],[2,1],[3,2]] → [0,1,2,3]

[[] for _ in range(n)] creates a separate neighbor list per vertex. [[]]*n shares one list, so graph[0].append(1) would add 1 to every vertex’s neighbors. An indegree reaches zero only once, which prevents duplicate queue insertion on valid inputs.

Implement and execute

from collections import deque
import heapq

def course_order(n, prerequisites):
    graph, indegree = [[] for _ in range(n)], [0] * n
    for after, before in prerequisites:
        graph[before].append(after)
        indegree[after] += 1
    queue = deque(v for v in range(n) if indegree[v] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == n else []
python trace_lab.py --case course_order

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 78: Subsets · Medium

Return every subset of an array of distinct values.

1 <= n <= 10; values -10..10; all distinct.

Predict before implementing

At each search node, save a copy of path. Choose an element, recurse on later positions, then pop it. Saving path itself aliases one changing list. With n=2, there are four outputs including the empty subset.

subsets([1, 2],)
# [[], [1], [1, 2], [2]]

Idea and state transitions

78 · Idea and execution trace

LeetCode 78: Subsets · Medium

Return every subset of an array of distinct values.

Restrict each next selection to a later index. This generates [2,5] once rather than also generating [5,2]. Every current path is itself a subset, so record it starting with the empty path.

nums=[2,5]. A snapshot is stored immediately on entering visit.

Execution path Snapshot stored
visit(0) [] []
append(2), visit(1) [2] [2]
append(5), visit(2) [2,5] [2,5]
pop(), pop() [] None
append(5), visit(2) [5] [5]

Output order: [[],[2],[2,5],[5]].

78 · Why it works; time and memory

Every subset has one increasing index sequence. start permits exactly that sequence, and restoration returns the parent path to its prior state.

Each element can be included or excluded, giving 2n subsets. For n>=1, each element occurs in half of them, so snapshots copy n·2n−1 elements in total. Materializing the output takes O(n·2n) time and output space.

The current path and recursion depth are each at most n, so auxiliary space excluding output is O(n). Time counts all work; space counts paths and calls alive at the same moment, not every call ever made.

result.append(path) stores one shared object; later pops can turn multiple results into empty lists.

nums=[2,5] → [[],[2],[2,5],[5]]

Implement and execute

from collections import deque
import heapq

def subsets(nums):
    result, path = [], []

    def visit(start):
        result.append(path.copy())
        for index in range(start, len(nums)):
            path.append(nums[index])
            visit(index + 1)
            path.pop()

    visit(0)
    return result
python trace_lab.py --case subsets

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 39: Combination Sum · Medium

Return unique combinations reaching target with unlimited candidate reuse.

1..30 distinct candidates, each 2..40; target 1..40; fewer than 150 answer combinations.

Predict before implementing

Track remaining target and the first allowed candidate index. Reuse the chosen index to permit repeats, but never return to smaller indices. Stop at remaining=0. Explain why [3,2,2] is not a second answer.

combinations([2, 3, 6, 7], 7)
# [[2, 2, 3], [7]]

Idea and state transitions

39 · Idea and execution trace

LeetCode 39: Combination Sum · Medium

Return unique combinations reaching target with unlimited candidate reuse.

Choose positive candidates to decrease the remaining sum. Reuse is allowed, so recurse from the selected index again. Never return to earlier indices; this avoids permutation duplicates such as [2,3] and [3,2].

candidates=[2,3], target=5. remaining is the sum still required.

path remaining Next action
[] 5 Choose 2
[2] 3 Reuse 2
[2,2] 1 2 > 1 → return
[2,3] 0 Save snapshot; return
[3] 2 3 > 2 → stop

Output: [[2,3]].

Returning to the parent’s next choice

For candidates [2,3] and target 5, each call owns its start and remaining variables; only path is shared. Returning from a child resumes the parent’s loop at the next statement.

Execution point Shared path This call’s remaining
Parent visit(0,3), append 2 [2,2] 3
Child visit(0,1), stop because 2>1 [2,2] 1
Resume parent, path.pop() [2] still 3
Parent’s next index=1, append 3 [2,3] 3
Child visit(1,0), save a copy and return [2,3] 0
Resume parent, path.pop() [2] 3

The parent in the first row has already selected the first 2. pop undoes the last shared path choice. The parent’s remaining was never changed, so it needs no addition to restore it. An implementation that mutates a global remaining would have to restore that value too.

39 · Why it works; time and memory

Positive choices decrease remaining and ensure termination. Nondecreasing indices avoid permutations while representing every combination.

With m candidates, target T, and smallest candidate c, path length is at most L=floor(T/c). Let B be visited calls and S the total output elements. Sorting costs O(m log m), each call checks at most m choices, and copying costs O(S): total O(m log m+mB+S). B depends strongly on the input; this is not a linear scan.

A conservative bound is B=O((m+1)L+1). The sorted candidates plus the path and call stack use O(m+L) auxiliary space. Output uses O(S); the full search tree is not stored simultaneously.

Recursing at index+1 misses [2,2] for [2], target=4. Zero is outside the contract and breaks termination.

candidates=[2,5], target=7 → [[2,5]]

For m=2,T=5,c=2, depth is at most L=2. The loose bound of at most m children per call gives at most 1+m+m²=7 calls. Ordering and sum pruning reduce the actual count; copying the S output elements is counted separately.

Implement and execute

from collections import deque
import heapq

def combinations(candidates, target):
    values, result, path = sorted(candidates), [], []

    def visit(start, remaining):
        if remaining == 0:
            result.append(path.copy())
            return
        for index in range(start, len(values)):
            value = values[index]
            if value > remaining:
                break
            path.append(value)
            visit(index, remaining - value)
            path.pop()

    visit(0, target)
    return result
python trace_lab.py --case combinations

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.