COMPSCI130 Cheatsheet · Introduction to Software Fundamentals

University of Auckland · Cheatsheet for the final exam. Semester Two examination period, 29 October – 16 November 2026 (check your personal exam timetable). Full COMPSCI130 study guide →

A4 landscape · two-side technical revision sheet · 6 columns per sideCOMPSCI130 · S2 2026 · Auckland
COMPSCI130
Introduction to Software Fundamentals
School of Computer Science · The University of Auckland · EXAM REVISION SHEET · SIDE 1 OF 2
COMPSCI130 cheatsheet QR code – open the full COMPSCI130 study guide
Full guide + ask Sia about COMPSCI130
SIDE 1/2   DEFINITIONS → INVARIANTS → OPERATION COST → TRACE → BOUNDARY TESTS2 2026 · 50% examinationMethods and rules · check each precondition

0 · Exam Mapcourse.json · brief

Labs + Assign. 30%   Test 20%Examination 50%     

Permitted materials: not confirmed for this offering in the course materials we hold — check the exam instructions on the LMS.

ComponentFormat / target
Labs + AssignmentsIndividual practical coursework
TestIndividual CodeRunner; programming
ExaminationIndividual 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.

x, y[2,4,6]y = y + [8]new y → [2,4,6,8]
Alias trace: mutation changes the shared object; concatenation creates a new list and rebinds y.
Line kindTrace question
AssignmentWhich name now refers to which object?
MutationWhich aliases observe the changed object?
Branch / loopWhich predicate values select the path?
CallWhat 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₀.

define ncount opsgrowth termexact count → bound → comparekeep preconditions and scale visible
Source redraw: input size leads through operation count to a defensible complexity class.
Code shapeCount / recurrenceGrowth
Fixed workcO(1)
One full passan+bO(n)
Repeated halvingT(n)=T(n/2)+cO(log n)
Two independent full loopsn+nO(n)
Nested full loopsn·nO(n²)
Triangular nestingΣᵢ₌₀ⁿ⁻¹i=n(n−1)/2Θ(n²)
One-step recursionT(n)=T(n−1)+cO(n)

How to justify, not guess

  1. Choose the operation being counted.
  2. Write each loop's actual iteration count; sequential costs add, nested costs multiply only when independent.
  3. Solve the sum/recurrence; then discard constants and lower terms for the asymptotic class.
  4. 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.

RepresentationInsertMembershipUse when
Unsorted arrayO(1) appendO(n)few queries, many appends
Sorted arrayO(n) movementO(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.

client sees: values + operations + errorscontract preserves invariant Ihidden representation
Source redraw: define the ADT contract before selecting class storage.
Contract itemQuestion to answer
DomainWhich values/states are valid?
OperationsInputs, outputs and state changes?
FailureWhich exception; is state unchanged?
InvariantWhat must be true before/after every call?
OwnershipCan 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

STACK · LIFOA · B · C↑toppop → CQUEUE · FIFOfront A · B · C reardequeue → A
Removal discipline decides the ADT: latest item for stack; earliest item for queue.
NeedChooseInvariant / warning
Undo / reverse arrivalStackMost recent item at top
Arrival orderQueueOldest item at front
Smallest key firstMin-priority queueMinimum pending key removed
Largest key firstMax-priority queueMaximum 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.

f(2043): 3 + …f(204): 4 + …f(20): 0 + …f(2) → 2CALL ↓RETURN ↑2 → 26 → 9
Source redraw: expand one frame per call; combine values only while unwinding returns.
Proof obligationWhat to write
DomainInputs for which the definition applies
BaseCondition and direct return
ProgressRecursive argument is smaller
Lower boundMeasure cannot decrease forever
CombineHow 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.

ABCXsave B first
Source redraw: set X.next to the saved successor before overwriting A.next.
OperationSafe pointer order
Insert X after Aold=A.next; X.next=old; A.next=X
Delete B after Xtarget=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.

ABCDEF
Worked tree: A root; B has D,E; C has right child F.
TraversalRuleResult above
Preorderroot-left-rightA B D E C F
Inorderleft-root-rightD B E A C F
Postorderleft-right-rootD E B F C A
Level orderbreadth by depthA 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.

0 childrendetach leaf1 childsplice child2 childrensuccessorright-subtree min
BST deletion: classify structural case before changing links.
OperationMethodCost
Searchcompare, take one childO(h)
Insertsearch to empty linkO(h)
Delete leafdetachO(h)
Delete one childsplice child upwardO(h)
Delete two childrencopy successor; delete its old nodeO(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.

index01234561017245lookup 24: 3→4→5
Worked linear probing with h(k)=k mod 7 after inserting 10,17,24,5.
KeyHomeProbe sequenceFinal
10333
1733,44
2433,4,55
555,66

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.

array[2, 5, 4, 9, 7, 8]254978
Min-heap: complete shape; every parent is no greater than either child.
OperationRestore orderExam check
Insertappend; sift upcompare with parent
Remove minmove last to root; sift downcompare both children; swap with smaller
Peek minread rootdoes 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.

https://www.asksia.ai/cheatsheet/auckland-compsci130 · Full COMPSCI130 study guide →
Forward this to your tutorial group
AskSiav2 · 2026-10-25 · Shared by ________
Semester Two examination period, 29 October – 16 November 2026 (check your personal exam timetable).
Check your exam instructions on the LMS for what you may bring; use this sheet to revise and self-test.
COMPSCI130
Worked Drills, Traps & Fast Recall
Introduction to Software Fundamentals · EXAM REVISION SHEET · SIDE 2 OF 2
COMPSCI130 cheatsheet QR code – open the full COMPSCI130 study guide
Full guide + ask Sia about COMPSCI130
SIDE 2/2   FIVE WORKED DRILLS · JUDGEMENT CARDS · CLASSIC TRAPS · EXAM-MORNING RETRIEVALshow state + invariant + costAnswers include the reasoning path

Drill 1 · Aliases + LoopC1 · 6 marks

Prompt. x=[2,4]; y=x; x.append(6); y=y+[8]; total=0. For each v in x, add v only if v%4==0. Find x, y, total; name the alias-breaking line.

1x,y → object [2,4]2append mutates → [2,4,6]3y+[8] creates new object4predicate: 2✗ 4✓ 6✗x=[2,4,6] · y=[2,4,6,8] · total=4
Answer path: preserve object identity until concatenation constructs a new list.
StepState after stepWhy
y=xboth names share one objectassignment does not copy
append(6)x,y both see [2,4,6]in-place mutation
y=y+[8]y gets [2,4,6,8]new list + rebinding
looptotal=4only 4 has remainder 0

Trap → “Assignment copies the list” is false here. Draw names and objects; distinguish mutation from construction.

Test Card · Boundary ParserC2

Contract: decimal strings for ages 0–130; invalid syntax or out-of-range values raise ValueError.

try: age = int(text)
except (TypeError, ValueError) as exc:
  raise ValueError("age must be a decimal integer") from exc
if age not in range(0,131): raise ValueError("age out of range")
return age

InputPathResult
"20"convert; range passes20
"" / "twenty"conversion failsValueError
"−1" / "131"converts; range failsValueError

Test evidence + exception scope

Test case = input, expected behaviour and observation checking one rule. State the expectation first; a mismatch then localises the defect.

CaseExpected evidence
Normal"20" returns 20
Boundary0 / 130 return the boundary ages
Syntax failure"" / "twenty" raise ValueError
Range failure"−1" / "131" raise ValueError

Trap → Catch only conversion errors being translated; a blanket catch can hide defects. Passing tests shows observed behaviour, not absence of defects.

Drill 2 · Exact Count → ΘC3 · 7 marks

Prompt. for i in range(n): for j in range(i): count += 1. Derive exact count; evaluate n=1000; state tight bound.

i=0 → 0 incrementsi=1 → 1 incrementi=2 → 2 incrementsΣᵢ₌₀ⁿ⁻¹ i = n(n−1)/2n=1000 → 499,500 → Θ(n²)
Triangular nesting: varying inner bounds must be summed, not copied as n×n.
  1. Inner loop executes exactly i times: 0,1,2,…,n−1.
  2. Total = 0+1+…+(n−1)=n(n−1)/2.
  3. At n=1000: 1000×999/2=499,500.
  4. Leading term n²/2 has upper and lower constant multiples of n², so Θ(n²).

Trap → range(i) has i iterations ending at i−1. Using i+1 creates an off-by-one sum.

Binary Search TraceC4 · worked values

Find 42 in [3,11,19,27,42,58,73], inclusive low/high.

(0,6,3): a[3]=27 → low=4(4,6,5): a[5]=58 → high=4(4,4,4): found 42
Inclusive interval: continue while low ≤ high; absence ends at low > high.
DesignDaily leading work for n=10,000
Unsorted2 appends O(1) + 100 membership queries O(n)
Sorted array2 insertions O(n) + 100 queries O(log n)

For the stated read-heavy day, maintaining order is the better of these two designs, while constants and batching should still be measured.

Inclusive-bound audit

Observed comparisonNext state
a[mid] < targetlow = mid + 1
a[mid] > targethigh = mid − 1
a[mid] = targetreturn mid
low > hightarget absent

Preconditions: ordered data, random access and one consistent interval convention.

Trap → Do not mix half-open and inclusive bounds. Here high remains a candidate, so continue while low ≤ high.

Drill 3 · Recursive Digit SumC7 · 7 marks

Definition. Single digit → n; otherwise n%10 + digit_sum(n//10). Trace digit_sum(2043) and prove termination.

expand3 + f(204)3 + 4 + f(20)3 + 4 + 0 + f(2)returnf(2)=2 → f(20)=2f(204)=6 → f(2043)=9
Unwind in caller order: 0+2=2, 4+2=6, 3+6=9.
Frame nLocal digitDeeper callReturn
2base—2
20022
204426
2043369

Termination: on the stated non-negative integer domain, for n≥10, 0≤n//10≤n−1. Thus n strictly decreases and is bounded below until the single-digit base case.

Pointer Drill · Insert + DeleteC8 · 7 marks

Start A→B→C→None. Insert X after A; then delete B without losing C.

startA → B → C → NoneinsertA → X → B → C → NonedeleteA → X → C → None
Read or save each successor before detaching the only link that reaches it.

old_next=A.next; X.next=old_next; A.next=X
target=X.next; X.next=target.next; target.next=None

Trap → If A.next is overwritten before B is saved or linked from X, the old suffix can become unreachable.

Link-invariant check

Link invariant keeps node references connected and well formed. Before overwriting a link, name every node reachable only through it.

CheckpointEvidence
Before insertsave successor B
Before deleteread B.next first
After updatehead still reaches the suffix

Cost → Relinking is O(1) only after the target position is known; a traversal needed to find it remains O(n).

Drill 4 · BST DeleteC10 · 9 marks

Insert [8,3,10,1,6,14,4,7,13]. Search 7; delete 3 with its inorder successor.

831016471413
Constructed BST; search 7 follows 8→3→6→7.
  1. Node 3 has two children. Its successor is the minimum in its right subtree: 4.
  2. Copy 4 into 3's position; delete the original 4 leaf.
  3. Final inorder: [1,4,6,7,8,10,13,14].
CheckEvidence
Search pathone comparison and branch per level
Successorleftmost node of right subtree
Key setonly 3 removed
Orderinorder remains strictly sorted

Trap → The successor is not automatically the immediate right child.

Hash Drill · Linear ProbingC11 · 8 marks

Size 7, h(k)=k mod 7; insert 10,17,24,5.

10: 317: 3→424: 3→4→55: 5→63:10 · 4:175:24 · 6:5α=4/7
Lookup 24 probes indices 3,4,5; home-slot mismatch does not prove absence.

Successful lookup: compare 10 at 3, 17 at 4, find 24 at 5. With no deletion, unsuccessful lookup can stop only at a never-used slot.

Probe + performance audit

Collision = distinct keys sharing a candidate position; the stated resolution strategy gives the next probe. Home-slot mismatch does not prove absence.

CheckWhat to report
Table staten=4, m=7, α=n/m=4/7
Successful lookupprobe 3,4,5 until key 24
Absent, no deletionstop at first never-used slot

Limit → Average constant-time claims depend on key distribution, resizing and collision handling; they do not guarantee constant worst-case time.

Drill 5 · Min-HeapC12 · 9 marks

Start [2,5,4,9,7,8]. Insert priority 1; then remove the minimum.

append[2,5,4,9,7,8,1]swap ↑[2,5,1,9,7,8,4][1,5,2,9,7,8,4]removeroot←4: [4,5,2,9,7,8]sift ↓: [2,5,4,9,7,8]
Insertion restores order upward; removal restores order downward while shape stays complete.
  1. Append 1 at i=6; parent is (6−1)//2=2. Swap with 4.
  2. At i=2, parent is 0. Swap with 2 → [1,5,2,9,7,8,4].
  3. Remove 1; move last key 4 to root.
  4. Compare children 5 and 2; swap with smaller 2 → [2,5,4,9,7,8].
InvariantAfter each operation
Shapearray represents a complete tree
Min-orderevery parent ≤ each child
Removalroot is minimum; remainder need not be sorted

Integrated ADT Drillcourse worked example

Commands arrive A,B,C; jobs arrive (draft,4),(exam,1),(notes,3).

ServiceADT + invariantFirst two removals
Undostack; LIFOC, then B
Print servicemin-priority queue; minimum key(exam,1), then (notes,3)

Choose from the removal rule. Both services insert items, but reverse arrival demands a stack while smallest numeric priority demands a min-priority queue.

Heap operation audit

Priority queue removes by priority; a heap is a complete tree with parent–child order.

Zero-based parentparent(i)=⌊(i−1)/2⌋, for every non-root index i

ChangeRequired check
Insertappend; restore order upward
Remove minlast to root; compare both children; restore downward
Auditcomplete shape; every parent ≤ each child

Trap → Compare both children; choosing left automatically may miss a smaller right. A heap exposes the extreme, not a sorted or stable sequence.

Judgement CardsC1–C12

If you see X…→ do Y
two names, one mutable objectdraw identities; classify mutation vs rebinding
nested loops with varying boundwrite a sum before naming Big O
binary searchverify order + random access + bound convention
public class methodstate contract; check invariant after success/failure
reverse arrival orderstack / LIFO
first arrival firstqueue / FIFO
recursive functionbase, smaller call, decreasing lower-bounded measure
link overwritesave the successor first
tree output orderidentify when root is visited
BST delete with two childrenuse successor = min(right subtree)
hash collisionfollow the stated resolution strategy
heap sift-downcompare both existing children
What output / removal rule is required?ordering disciplinekey / shape rulestack/queueBST/hash/heap
Method chooser: derive structure from required behaviour, not surface syntax.

Classic Trapssource limits

Wrong shortcutRepair
Assignment always copiestrack object identity
Tests prove correctnessclaim only observed behaviours
O(n²) means exact n² workseparate exact count from growth
Binary search is always fastestinclude ordering/maintenance cost
Class = abstractionwrite ADT contract + invariant
List means queue or stackstate logical discipline and cost
Recursion works on sample, so doneprove termination; inspect repeated work
Relinking is always O(1)include traversal to target
Inorder is always sortedonly under BST invariant
BST operations are always log ncost depends on height
Hash lookup is guaranteed O(1)state average-case assumptions
Heap array is sortedonly parent-child order is guaranteed

Exam-Morning Planretrieval, not rereading

  1. Recite the 12 bold decisions in the judgement table without looking.
  2. Trace one alias, one recursion and one structural update on paper.
https://www.asksia.ai/cheatsheet/auckland-compsci130 · Full COMPSCI130 study guide →
Forward this to your tutorial group
AskSiav2 · 2026-10-25 · Shared by ________
Semester Two examination period, 29 October – 16 November 2026 (check your personal exam timetable).
Check your exam instructions on the LMS for what you may bring; use this sheet to revise and self-test.

Want one for YOUR exact syllabus?

Sia is your free desktop study agent. Drop your University of Auckland COMPSCI130 slides — Sia builds a sheet tailored to YOUR exam. Better than this library because it knows YOUR materials.

↓ Download Sia · Free