COMP90038 · Algorithms And Complexity
The Complete Exam Bible · S1 2026Algorithms and Complexity
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. 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.
What COMP90038 covers
Ten technique families → one exam-ready map. Each links to its free chapter guide.
How COMP90038 is assessed
| Component | Weight | Format |
|---|---|---|
| Final examination | 60% | 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 quizzes | 10% | 10 Canvas quizzes across the semester (MCQ / short numeric) drilling the recurring hand-trace moves |
| Assignment 1 | 15% | Recurrence proofs + design-and-analyse — no AI tools permitted; confirm the exact rules in your subject guide |
| Assignment 2 | 15% | Algorithm design — later in the semester; confirm the exact dates in your subject guide |
Applying the Master Theorem — reading off the running time, case by case
- +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).
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.
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.
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.
