University of Melbourne · S1 2026 · FACULTY OF INFORMATION TECHNOLOGY

COMP90038 Algorithms and Complexity

- one subject, every graph, every model, every mark
10 Chapters75-page Bible
Our own words - no uploaded lecturer files
Built to mirror S1 2026 · updated this semester
The Complete Exam Bible · S1 2026

COMP90038 Overview

Algorithms and Complexity
— name the technique, run the trace, state and justify the bound
  • University of Melbourne
  • S1 2026
  • 10 chapters
  • Information Technology

Algorithms and Complexity is the University of Melbourne's core algorithms subject — it builds the analysis toolkit (the RAM cost model, big-O / Ω / Θ, recurrences and the Master Theorem) and then works through the design paradigms in order: brute force, graph traversal, decrease-and-conquer, divide-and-conquer, the transform-and-conquer structures (heaps, balanced trees, hashing), dynamic programming and greedy.

  • Assessed by Final examination 60% · Weekly quizzes 10% · Assignment 1 15% · Assignment 2 15%
  • Key terms Big-O / Ω / Θ, Master Theorem, Amortised analysis, Heap
  • How to prepare Treat hand-tracing speed and the design-technique decoder as the grade-deciders…
  • Most asked What is on the COMP90038 final exam?
Why read this guide

What you get in the full COMP90038 Exam Bible

  1. 10 chapters, 75 pages — every examinable topic
  2. 18 original practice questions, each with a model answer in the Final examination format
  3. 10 worked examples, solved the way COMP90038 marks
  4. 20 computed figures, redrawn from the course’s own numbers
  5. Exam-morning plan for the Final examination (60%) — what to revise last, where marks are lost

Free on this page: assessment table, chapter map, one worked example, key terms, FAQ. The rest is in the full exam bible.

COMP90038 · University of Melbourne
An independent, AskSia-authored study guide. AskSia is not affiliated with, endorsed by, or sponsored by University of Melbourne; the course code and name are used for identification only.
Assessment

How COMP90038 is assessed

ComponentWeightFormat
Final examination60%In-person, open-book (paper based) · 15 min reading + ~180 min writing · Q1 = MCQ hand-traces, Q2 = True/False with justification, Q3–Q10 = design-and-analyse
Weekly quizzes10%10 Canvas quizzes across the semester (MCQ / short numeric) drilling the recurring hand-trace moves
Assignment 115%Recurrence proofs + design-and-analyse — no AI tools permitted; confirm the exact rules in your subject guide
Assignment 215%Algorithm design — later in the semester; confirm the exact dates in your subject guide
Other students are asking · COMP90038

What other students are asking about COMP90038

Where can I find lecture notes or study guides for COMP90038 at UniMelb?
The COMP90038 study guide in AskSia Library covers Algorithms and Complexity in 10 chapters, with the assessment table, a chapter-by-chapter topic map, key terms and a worked example, free to read on this page.
Is there a final exam in COMP90038, and how much is it worth?
Yes. In the offering this AskSia Library guide is built from, Final examination carries 60% of the COMP90038 mark; the full split is Final examination 60%, Weekly quizzes 10%, Assignment 1 15%, Assignment 2 15%.
What does COMP90038 cover on brute force and exhaustive search?
In AskSia Library's COMP90038 guide, the Brute Force and Exhaustive Search chapter explains selection sort · brute string match · closest pair · TSP / knapsack generate-and-test.
What does COMP90038 cover on graphs and traversal?
In AskSia Library's COMP90038 guide, the Graphs and Traversal chapter explains matrix vs list · DFS / BFS · topological sort · connected components in O(V+E).
What does COMP90038 cover on decrease-and-conquer?
In AskSia Library's COMP90038 guide, the Decrease-and-Conquer chapter explains decrease by constant / factor / variable · insertion sort · binary search · quickselect.
Weights, dates and every chapter are set out with their sources further down this page.
Contents · every chapter, one map

What COMP90038 covers

Ten technique families → one exam-ready map. Each links to its free chapter guide.

01

Foundations: the Cost Model and Asymptotics

Word-RAM · O / Ω / Θ · worst / expected / amortised · recurrences

Every later technique is judged against the toolkit built here.

  • The Word-RAM cost model and the basic O(1) operations
  • Big-O, Ω and Θ — upper, lower and tight asymptotic bounds
  • Worst-case vs expected vs amortised — always state which
  • Common growth-rate hierarchy: 1 < log n < n < n log n < n² < 2ⁿ
  • Setting up recurrences from recursive code; priming the Master Theorem
02

Brute Force and Exhaustive Search

Selection sort · brute string match · closest pair · TSP / knapsack generate-and-test

The honest baseline: solve a problem straight from its definition, with no cleverness, and measure what that costs.

  • Selection sort — the Θ(n²) min-finding baseline
  • Brute-force string matching — sliding the pattern, Θ(nm)
  • Closest pair by checking all pairs — Θ(n²)
  • Exhaustive search / generate-and-test as the general pattern
  • TSP (Θ(n!)), knapsack (Θ(2ⁿ)) and Hamiltonian circuits
03

Graphs and Traversal

Matrix vs list · DFS / BFS · topological sort · connected components in O(V+E)

Graphs are the data model behind a third of the subject, so the vocabulary and the two traversals have to be automatic.

  • Graph vocabulary: directed / undirected, weighted, paths, cycles, connectivity
  • Adjacency matrix (Θ(V²)) vs adjacency list (Θ(V+E)) — dense vs sparse
  • The unified traversal framework: stack → DFS, queue → BFS, O(V+E)
  • DFS / BFS forests and edge classification (tree / back / cross)
  • Topological sort two ways; connected components
04

Decrease-and-Conquer

Decrease by constant / factor / variable · insertion sort · binary search · quickselect

The first design paradigm: solve a problem by reducing it to one smaller instance, solving that, and extending the answer — in contrast to divide-and-conquer, which splits into several sub-problems.

  • Decrease-by-constant: insertion sort (Θ(n²) / Θ(n) best)
  • Decrease-by-constant-factor: binary search, fast exponentiation → Θ(log n)
  • Decrease-by-variable-size: quickselect, Euclid's GCD
  • Why halving the input gives a logarithmic cost
  • Choosing the single smaller sub-instance and extending its answer
05

Divide-and-Conquer and the Master Theorem

Mergesort · quicksort · the four-parameter ritual · tree rebuild from traversals

The paradigm that splits a problem into several sub-problems of (usually) equal size, solves them recursively, and combines the results.

  • Mergesort — the guaranteed Θ(n log n) merge
  • Quicksort — Θ(n log n) expected, Θ(n²) worst-case pivots
  • The Master Theorem and the watershed exponent log<sub>b</sub>a vs d
  • The four-parameter ritual: write a, b, d &rarr; name the case &rarr; justify
  • Binary-tree traversals; reconstruct from two, read off the third
06

Heaps and Priority Queues

Array ↔ complete tree · bubble up / down · heapify in O(n) · heapsort

The first transform-and-conquer structure: a priority queue — an abstract type that hands you the most-urgent element on demand — implemented as a binary heap.

  • The priority-queue ADT and what a heap provides
  • Array layout of a complete tree: children 2i / 2i+1, parent &lfloor;i/2&rfloor;
  • The heap property; bubble-up (insert) and bubble-down (delete) in O(log n)
  • Bottom-up heapify in O(n) &mdash; why it beats n inserts
  • Heapsort: heapify then extract, &Theta;(n log n) in place
07

Balanced Search Trees: AVL and 2-3

Balance factor · the four rotations · 2-3 split & promote · height = O(log n)

A binary search tree gives O(log n) search only if it stays short — and a plain BST can degenerate to a linked list (height n) on sorted input, the trap this chapter exists to fix.

  • BST recap and the height = O(log n)? degeneration trap
  • AVL balance factor and when an insert breaks it
  • The four rotations: single LL / RR, double LR / RL
  • 2-3 trees: 2-nodes and 3-nodes, all leaves at the same depth
  • Split-and-promote insertion; guaranteed O(log n) operations
08

Space-Time Tradeoffs and Hashing

Counting sort · Horspool · chaining vs probing · universal hashing · load factor

The transform-and-conquer idea that you can spend extra memory to buy time. Three techniques carry the chapter.

  • Counting sort &mdash; O(n) and beating the comparison lower bound
  • Horspool's algorithm &mdash; shift tables (Boyer-Moore / KMP / Rabin-Karp NOT examinable)
  • Hash functions and collisions
  • Chaining vs open addressing (linear probing); the load factor
  • Universal hashing and the pigeonhole principle
09

Dynamic Programming

Overlapping sub-problems · the table · coin-row · knapsack · Warshall · Floyd

The optimisation paradigm for problems with two properties: overlapping sub-problems (the same smaller question is asked many times) and optimal substructure (an optimal whole is built from optimal parts).

  • Overlapping sub-problems and optimal substructure &mdash; the two DP preconditions
  • Bottom-up table vs top-down memoisation; coin-row warm-up
  • 0/1 knapsack as a weight&times;item table
  • Warshall's transitive closure (R<sup>(k)</sup>) &mdash; &Theta;(n<sup>3</sup>)
  • Floyd's all-pairs shortest paths (D<sup>(k)</sup>); O(1)-space DP tricks
10

Greedy Algorithms

Prim · Dijkstra · Huffman · the super-source trick · when greedy is wrong

The last paradigm: build a solution by repeatedly taking the locally best choice available right now and never reconsidering — fast and simple, but only correct when the problem has the right structure, which is the chapter's recurring theme.

  • The greedy strategy: locally best, never reconsidered
  • Prim's MST &mdash; cheapest edge leaving the tree, O(E log V)
  • Dijkstra's shortest paths (non-negative weights); the super-source trick
  • Huffman coding &mdash; merge the two least-frequent symbols
  • When greedy fails (0/1 knapsack, negative edges) and how to justify it

The final exam is 60% of your grade, in-person and open-book (paper) — but “open book” is a trap: you cannot out-flip hundreds of pages of Levitin in three hours, and the marks live in hand-tracing speed and method, not in lookup.

This guide drills exactly that — every technique on one recurring answer shape: name the technique → run the trace / set up the recurrence → state AND justify the time and space bound → decide.

Worked example · free

Applying the Master Theorem — reading off the running time, case by case

Q [6 marks]. For each divide-and-conquer recurrence, identify the parameters a, b, d and use the Master Theorem to state Θ(·): (i) mergesort T(n) = 2T(n/2) + Θ(n); (ii) binary search T(n) = T(n/2) + Θ(1); (iii) the naive recursion T(n) = 4T(n/2) + Θ(n).
costinput size ncase 1: n^(log_b a)case 2: n^d log ncase 3: n^d (root wins)log_b a vs d
  • +1Set up the comparison. For T(n) = aT(n/b) + Θ(nd), compute the watershed exponent logba and compare it with d (the exponent of the combine cost). Three cases follow from which side wins.
  • +2(i) Mergesort: a = 2, b = 2, d = 1, so logba = log22 = 1 = d → Case 2 (a tie): T(n) = Θ(nd log n) = Θ(n log n).
  • +1(ii) Binary search: a = 1, b = 2, d = 0, so log21 = 0 = d → Case 2: T(n) = Θ(n0 log n) = Θ(log n).
  • +2(iii) Four-way naive recursion: a = 4, b = 2, d = 1, so log24 = 2 > d = 1 → Case 1 (leaves dominate): T(n) = Θ(nlogba) = Θ(n2).
(i) Θ(n log n); (ii) Θ(log n); (iii) Θ(n2). The case is decided by comparing logba (cost of the leaves) with d (cost of the combine): leaves win → Case 1; tie → Case 2 with an extra log n; root wins → Case 3.
Sia tip — Always write the three parameters a, b, d explicitly before quoting a case — the marks are in showing logba vs d, not just the final Θ. And remember the Master Theorem only applies when the sub-problems are equal-sized; an uneven split (e.g. T(n) = T(n−1) + Θ(n)) needs the recurrence-tree method instead.
Glossary

Key terms

Big-O / Ω / Θ
Asymptotic bounds on a function's growth: O(g) is an upper bound (grows no faster than g), Ω(g) a lower bound, and Θ(g) a tight bound (both at once). They describe behaviour as n → ∞, ignoring constants and lower-order terms — so 3n2 + 5n is Θ(n2).
Master Theorem
A formula for solving divide-and-conquer recurrences of the form T(n) = aT(n/b) + Θ(nd). Compare the watershed exponent logba with d: if logba > d the leaves dominate (Case 1); a tie gives an extra log factor (Case 2); if d wins the root dominates (Case 3). It only applies to equal-sized sub-problems.
Amortised analysis
The average cost per operation across a worst-case sequence, even when individual operations vary wildly. A dynamic array's append is O(n) on the resize step but O(1) amortised, because expensive resizes are rare enough to spread their cost. Distinct from average-case, which averages over random inputs.
Heap
A complete binary tree stored in a plain array that maintains the heap property (every parent dominates its children). It gives O(log n) insert and delete-min/max and O(1) peek, and can be built in O(n) by heapify — the engine behind heapsort and the priority queue.
Dynamic programming
An optimisation technique for problems with overlapping sub-problems and optimal substructure: solve each sub-problem once, store its answer in a table, and build up the final answer instead of re-solving. Bottom-up (fill the table) and top-down memoisation are the two styles; Warshall's and Floyd's algorithms are the classic graph examples.
FAQ

COMP90038 FAQ

Is COMP90038 hard?

It is conceptually rich and trace-heavy. The difficulty is precision and speed under exam time: the same moves — hand-tracing an AVL insert, filling a Floyd matrix, identifying a Master-Theorem case, designing an algorithm to a target complexity — recur on fresh inputs, so the work is making each one automatic.

The 60% open-book final concentrates the stakes on one paper, and open-book lulls students into not practising the very speed it tests.

How is COMP90038 assessed?

The final exam is 60% — in-person, open-book on paper. The rest is 10 weekly Canvas quizzes (10%), Assignment 1 on recurrences and design (15%, no AI tools permitted) and Assignment 2 on algorithm design (15%). Confirm this year's exact weights, dates and the open-book rules in your subject guide and on Canvas.

What is on the COMP90038 final exam?

A fixed structure: Q1 is around ten 1-mark MCQ hand-traces (AVL inserts, 2-3 build, linear probing, Warshall and Floyd matrices, DFS topological sort, MST weight); Q2 is True/False with justification (state the constants or a counterexample, not just the verdict); and Q3–Q10 are design-and-analyse questions worth most of the marks, where you must state AND justify both time and space.

Is the exam really open-book, and does that make it easier?

It is open-book on paper — you may bring paper copies of the textbook, lecture slides and workshop solutions, but no devices. It does not make it easier: Q1's hand-traces and Q3–Q10's designs are the work itself, not something you can look up, and flipping hundreds of pages in three hours costs time you do not have. The win is a concise per-technique reference plus the design-technique decoder.

Confirm the current rules on your own LMS.

Is using AskSia for COMP90038 cheating?

No. AskSia is a study reference written in our own words — we host none of your lecturer's files, our pseudocode and hand-traces are our own, and every worked example uses our own invented inputs, never the assessed assignment datasets or the exam. Sia teaches you the method to earn the marks; it does not complete or sit your assessments, and Assignment 1 prohibits AI tools — follow that rule.

Chapter questions

Questions students ask in each COMP90038 chapter

Why count operations instead of timing the code?
Because wall-clock time depends on the machine, the language and the compiler, none of which are intrinsic to the algorithm. Counting basic operations as a function of n gives a hardware-independent measure that predicts how the cost scales — which is what the exam and real engineering decisions care about. Chapter 01 · Foundations: the Cost Model and Asymptotics
If brute force is slow, why study it?
Because it is always available, easy to implement and easy to prove correct, so it is the baseline that defines the problem and the yardstick a faster algorithm must beat. Several exam designs ask you to give the brute-force cost first, then improve it — you cannot show the improvement without the baseline. Chapter 02 · Brute Force and Exhaustive Search
When should I use a matrix versus a list?
Use an adjacency list for sparse graphs (E far below V²) and whenever you traverse, because traversal is O(V+E) on a list. Use a matrix for dense graphs or when you need O(1) edge-existence tests — for example Warshall's and Floyd's algorithms, which are inherently Θ(V²)/Θ(V³) and matrix-shaped anyway. Chapter 03 · Graphs and Traversal
How is decrease-and-conquer different from divide-and-conquer?
Decrease-and-conquer recurses on a single smaller instance (binary search throws away half and recurses once); divide-and-conquer splits into several sub-problems and combines their answers (mergesort splits into two halves and merges). The number of recursive calls per step is the giveaway. Chapter 04 · Decrease-and-Conquer
How do I apply the Master Theorem step by step?
Write the recurrence as T(n) = aT(n/b) + Θ(nd), identify a, b and d, compute logba, and compare it with d. logba > d → Case 1 (Θ(nlogba)); equal → Case 2 (Θ(nd log n)); less → Case 3 (Θ(nd)). Always show a, b, d — the marks are in the comparison, not the final symbol. Chapter 05 · Divide-and-Conquer and the Master Theorem
Why is a heap stored in an array instead of with nodes and pointers?
Because a heap is always a complete tree, its shape is fixed, so the array index encodes the tree structure: child = 2i / 2i+1, parent = ⌊i/2⌋. That removes all pointer overhead, gives cache-friendly contiguous storage, and makes the index arithmetic the whole of the implementation. Chapter 06 · Heaps and Priority Queues
Why isn't a plain BST good enough?
Because a plain BST's height depends on insertion order. Insert sorted keys and it degenerates into a linked list of height n, making search O(n). Self-balancing trees guarantee height Θ(log n) no matter the order, which is the whole point of AVL and 2-3 trees. Chapter 07 · Balanced Search Trees: AVL and 2-3
How can counting sort be faster than O(n log n) if that's the sorting lower bound?
The Ω(n log n) bound applies only to comparison sorts. Counting sort never compares keys — it indexes them directly into an occurrence array — so the bound does not apply. The catch is it only works when keys come from a small, bounded universe; otherwise the |U| term dominates. Chapter 08 · Space-Time Tradeoffs and Hashing
When can I use dynamic programming?
When the problem has overlapping sub-problems (the same smaller instances recur) and optimal substructure (an optimal solution is composed of optimal sub-solutions). If sub-problems do not overlap, plain divide-and-conquer is already efficient; if substructure fails, DP gives the wrong answer. Chapter 09 · Dynamic Programming
When is a greedy algorithm guaranteed correct?
When the problem has optimal substructure and the greedy-choice property: a locally optimal choice is always part of some globally optimal solution. Prim, Dijkstra (non-negative weights) and Huffman satisfy this and have exchange-argument proofs; 0/1 knapsack and negative-weight shortest paths do not. Chapter 10 · Greedy Algorithms
Study strategy

How to study for the exam

Treat hand-tracing speed and the design-technique decoder as the grade-deciders, because that is exactly what the 60% open-book paper tests and exactly what flipping the textbook cannot buy you.

Drill the Q1 moves until they are automatic: insert keys into an AVL tree and rebalance, build a 2-3 tree, run linear probing, fill a Warshall R2 and a Floyd D1 matrix, and reconstruct a tree from its traversals.

For Q3–Q10, practise reading the required complexity off the prompt and naming the technique — bounded universe → counting sort; O(n log n) → presort + scan; shortest-from-source → Dijkstra with a heap; all-pairs → Floyd Θ(n3); overlapping sub-problems → dynamic programming — then state and justify both time and space, because that is where the marks sit.

Open-book is a trap: print a concise reference, but bank the method beforehand.

A+Everything unlocked
Unlocks this Bible + all 185 of your subjects at University of Melbourne, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP90038 tutor, unlimited, worked the way the exam marks it
The full 75-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works