0 · Exam Mapcourse.json · brief
Permitted materials: not confirmed for this offering in the course materials we hold — check the exam instructions on the LMS.
| Component | Format / target |
|---|---|
| Labs + Assignments | Individual practical coursework |
| Test | Individual CodeRunner; programming |
| Examination | Individual CodeRunner; data-structure concepts + programming |
The final rewards a repeated method: name the required operations → state the invariant → choose a representation → trace state → justify cost → test normal, boundary and failure paths.
1 · Program StateC1 · final tracing
Program state = current values plus control position. Assignment binds a name/location to a value; it is not mathematical equality. Control flow is the executed order of statements, branches, loops and calls.
State transitionsₜ₊₁ = F(sₜ, xₜ)
Executed statement + current input transform current state.
| Line kind | Trace question |
|---|---|
| Assignment | Which name now refers to which object? |
| Mutation | Which aliases observe the changed object? |
| Branch / loop | Which predicate values select the path? |
| Call | What frame, arguments and return value exist? |
Check → A trace is valid only for stated inputs, types and evaluation order; never generalise past an untested branch.
2 · Modules, Tests, ExceptionsC2 · code quality
Module: named unit grouping related definitions behind an interface. Test case: input + expected behaviour + observation, aimed at one rule. Exception: runtime event interrupting ordinary control flow; propagate or handle explicitly.
Observed pass rater = npass / nrun · says nothing about untested behaviour or test quality.
3 · Complexity: Count FirstC3 · explain efficiency
Input size n must be defined. Time complexity tracks growth of relevant operations. Big O is an asymptotic upper bound.
Upper-bound ruleT(n) ∈ O(g(n)) when constants c,n₀ exist such that T(n) ≤ c·g(n) for n ≥ n₀.
| Code shape | Count / recurrence | Growth |
|---|---|---|
| Fixed work | c | O(1) |
| One full pass | an+b | O(n) |
| Repeated halving | T(n)=T(n/2)+c | O(log n) |
| Two independent full loops | n+n | O(n) |
| Nested full loops | n·n | O(n²) |
| Triangular nesting | Σᵢ₌₀ⁿ⁻¹i=n(n−1)/2 | Θ(n²) |
| One-step recursion | T(n)=T(n−1)+c | O(n) |
How to justify, not guess
- Choose the operation being counted.
- Write each loop's actual iteration count; sequential costs add, nested costs multiply only when independent.
- Solve the sum/recurrence; then discard constants and lower terms for the asymptotic class.
- Name worst/average/best case if the path varies.
Limit → Big O suppresses constants and lower-order terms: it does not predict exact runtime, hardware effects or every small input.
4 · Search/Sort Trade-offC4 · choose by workload
Binary-search recurrenceT(n)=T(n/2)+c · each comparison discards about half the ordered interval.
| Representation | Insert | Membership | Use when |
|---|---|---|---|
| Unsorted array | O(1) append | O(n) | few queries, many appends |
| Sorted array | O(n) movement | O(log n) | read-heavy, order maintained |
Binary search needs ordered data and random access. Its search cost excludes creating/maintaining order. Fix one interval convention: inclusive bounds use while low ≤ high; failure is low > high.
5 · ADT Before ClassC5 · design questions
Abstract data type defines values and permitted operations independently of implementation. Abstraction separates essential behaviour from representation. A Python class stores object state and supplies methods, but is only an implementation mechanism.
Operation contractS′ = op(S,x), I(S) ⇒ I(S′)
Every public operation, including rejection, must preserve invariant I.
| Contract item | Question to answer |
|---|---|
| Domain | Which values/states are valid? |
| Operations | Inputs, outputs and state changes? |
| Failure | Which exception; is state unchanged? |
| Invariant | What must be true before/after every call? |
| Ownership | Can callers alias internal storage? |
Bounded stack example: owned storage contains exactly the logical items in order; 0 ≤ len(items) ≤ capacity; positive immutable capacity; no public alias. Overflow checks occur before mutation.
Trap → A class does not itself prove useful abstraction, encapsulation or invariant preservation.
6 · Stack vs QueueC6 · choose removal rule
| Need | Choose | Invariant / warning |
|---|---|---|
| Undo / reverse arrival | Stack | Most recent item at top |
| Arrival order | Queue | Oldest item at front |
| Smallest key first | Min-priority queue | Minimum pending key removed |
| Largest key first | Max-priority queue | Maximum pending key removed |
Successful size update|S′|=|S|+1 for insert; |S′|=|S|−1 for removal, with ordering discipline preserved.
7 · Recursion: Proof + TraceC7 · calls and returns
Base case solves a terminating input directly. Recursive case reduces the instance and combines returned results. Correct small outputs are insufficient: prove progress.
| Proof obligation | What to write |
|---|---|
| Domain | Inputs for which the definition applies |
| Base | Condition and direct return |
| Progress | Recursive argument is smaller |
| Lower bound | Measure cannot decrease forever |
| Combine | How returned value solves caller |
One-step recurrenceT(n)=T(n−1)+c → linear work, provided one smaller call and constant local work.
Digit-sum termination: for integers n≥10, 0 ≤ n//10 ≤ n−1; non-negative n strictly decreases until a single digit.
Trace → One row per frame. Do not add local work until the deeper call has returned to that frame.
8 · Linked ListsC8 · pointer safety
Node stores an element and link(s). The link invariant keeps the structure connected and well formed. Relinking may be O(1) after the target is known; finding it may require O(n) traversal.
| Operation | Safe pointer order |
|---|---|
| Insert X after A | old=A.next; X.next=old; A.next=X |
| Delete B after X | target=X.next; X.next=target.next; target.next=None |
TraversalT(n)=T(n−1)+c: following one next link per node is linear.
9 · Trees + TraversalC9 · output order
A tree is hierarchical and acyclic from a root; a subtree is one node plus all descendants. Choose traversal by when the root is visited.
| Traversal | Rule | Result above |
|---|---|---|
| Preorder | root-left-right | A B D E C F |
| Inorder | left-root-right | D B E A C F |
| Postorder | left-right-root | D E B F C A |
| Level order | breadth by depth | A B C D E F |
Binary-tree width boundwd ≤ 2ᵈ; sparse trees may contain fewer nodes at depth d.
Inorder is sorted only if the tree is also a BST. A traversal order does not itself provide search efficiency, balancing or key ordering.
10 · Binary Search TreesC10 · preserve order
Invariant: for every node, smaller keys occupy the designated left subtree and larger keys the right subtree (under the chosen duplicate policy). Search follows one branch per comparison.
| Operation | Method | Cost |
|---|---|---|
| Search | compare, take one child | O(h) |
| Insert | search to empty link | O(h) |
| Delete leaf | detach | O(h) |
| Delete one child | splice child upward | O(h) |
| Delete two children | copy successor; delete its old node | O(h) |
Height-dependent searchT(h)=T(h−1)+c ⇒ O(h). Balanced height is logarithmic; a highly unbalanced insertion order can make h linear.
Invariant check → Inorder traversal after an update must retain strict key order and contain exactly the intended keys.
11 · Hashing + CollisionsC11 · trace probes
A hash function deterministically maps a key to an integer candidate position. A collision means distinct keys share a candidate; correctness therefore requires an explicit resolution strategy.
Load factorα = n/m · entries n divided by capacity m; interpret collision pressure with distribution, resizing and strategy.
| Key | Home | Probe sequence | Final |
|---|---|---|---|
| 10 | 3 | 3 | 3 |
| 17 | 3 | 3,4 | 4 |
| 24 | 3 | 3,4,5 | 5 |
| 5 | 5 | 5,6 | 6 |
Without deletion, unsuccessful lookup stops at the first never-used slot, not at the first different key. Average constant-time claims depend on key distribution, resizing and collisions; worst case is not guaranteed constant.
12 · Priority Queue + HeapC12 · restore invariants
Priority queue removes by priority, not arrival. A binary heap is complete (shape) and obeys parent-child order; it is not a fully sorted sequence.
Zero-indexed heapparent(i)=⌊(i−1)/2⌋ for every non-root index i.
| Operation | Restore order | Exam check |
|---|---|---|
| Insert | append; sift up | compare with parent |
| Remove min | move last to root; sift down | compare both children; swap with smaller |
| Peek min | read root | does not imply sorted remainder |
During sift-down, compare both existing children. Choosing the left automatically may leave a smaller right child above its parent. Equal priorities are not necessarily stable.