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.
| 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 subsets. For n>=1, each element occurs in half of them, so snapshots copy n· elements in total. Materializing the output takes O(n·) 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(). 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.