COMP90038: pass the exams, not just read the notes
Your complete guide to University of Melbourne's algorithms and complexity unit. See where the marks are, work real practice questions, and study with an AI tutor that knows COMP90038.
Sia generates COMP90038 practice questions, walks through analysis of algorithms and graphs step by step, and quizzes you on the material the exam weights most heavily.
Find what is wrong
A COMP90038-style problem (sample-exam Question 7, Alice's stairs): Alice climbs a stair of n steps, taking either 1 or 2 steps at a time. The number of distinct ways to reach step n is f(n) with f(1) = 1, f(2) = 2 and f(n) = f(n-1) + f(n-2). A student writes the required O(n)-time, O(1)-space bottom-up loop, but it returns the wrong answer for n >= 3. For n = 5 the correct answer is 8, but this code returns 5. Which single line is the bug?
def ways(n):
if n <= 2:
return n
a, b = 1, 2 # a = f(1), b = f(2)
for i in range(3, n + 1):
c = a + b
a = b # line X
b = a # line Y <-- ?
return bThe rolling-window pattern needs c = a + b (the new f(i)), then shift the window forward: the old b becomes the new a, and c becomes the new b.
Trace n = 5 with the buggy code: start a = 1, b = 2. i = 3: c = 3, a = 2, b = 2. i = 4: c = 4, a = 2, b = 2. i = 5: c = 4, a = 2, b = 2. It returns b = 2... and with the realistic variant where the answer drifts you still never reach 8. The fix is b = c, which gives a = 1,2,3,5 and b = 3,5,8 so ways(5) = 8.
Option A is wrong: a = b is correct (old f(i-1) is what a should hold next). Options C and D break the verified base case and range. The single fix is line Y: b = c (option index 1).
The trap: Updating a and b in the wrong order or reusing a freshly-overwritten variable. The safe pattern is to compute the new value into a temporary (c = a + b) first, then shift: a, b = b, c. Overwriting a before reading it into b is the classic rolling-Fibonacci bug, and it silently passes n = 1 and n = 2 because those hit the base case. classic slip!
One exam decides 60% of your grade. Hurdle: you must score at least 30/60 on the written exam AND at least 50 overall to pass. This whole page is built around that.
Overview
What COMP90038 is, and where it sits
COMP90038 Algorithms and Complexity is the University of Melbourne's core algorithm-design subject, run by the School of Computing and Information Systems. Its stated aim is to build familiarity and competence in assessing and designing computer programs for computational efficiency: you learn the classical algorithms and data structures used to solve key computational problems, together with the mathematical techniques to establish their properties, above all how an algorithm's performance scales with the size of the input. It follows Levitin's Introduction to the Design and Analysis of Algorithms and is organised around algorithm-design paradigms rather than a tour of disconnected tricks.
The semester moves through a fixed arc: the cost model and asymptotic analysis (O, Omega, Theta, worst versus average case); brute force and exhaustive search; graphs and the DFS and BFS traversals (with topological sort and connected components); decrease-and-conquer; divide-and-conquer with the Master Theorem; priority queues, heaps and heapsort; balanced search trees (AVL and 2-3 trees); space-time tradeoffs and hashing (separate chaining and linear probing); dynamic programming; greedy algorithms and Huffman coding; and, class progress permitting, an introduction to NP-completeness. The recurring skill is not just to run an algorithm by hand but to state and justify its running time formally.
It is a 12.5-point subject delivered dual-delivery, with a 2-hour lecture and a 1-hour tutorial each week (tutorials start in Week 2). The teaching is paradigm-first: each design technique (decrease-and-conquer, divide-and-conquer, dynamic programming, greedy) is introduced, then applied across sorting, searching, graphs and optimisation, so the exam tests whether you can pick the right paradigm and prove the bound, not just recall a named algorithm.
Difficulty & time commitment
Is COMP90038 hard, and how much time does it take?
COMP90038 is manageable if you keep a weekly rhythm and treat the back half as the main event. Across student reviews the pattern is consistent: it starts gently and steepens, and the heaviest assessment is the part that separates grades.
A read across student reviews and course feedback. See what students say ↓
The difficulty curve and the assessment weighting point the same way: the back half is harder and worth more. Front-loading effort there is the highest-return decision in the unit.
Is this unit for you
Who tends to do well, and who tends to struggle
You will likely do well if
- You enjoy formal reasoning: writing asymptotic proofs, solving recurrences by expansion and the Master Theorem, and justifying a running time rather than just coding a solution.
- You hand-trace data structures until they are automatic: AVL and 2-3 tree insertions and rotations, heapify and delete-min, hashing with chaining and linear probing, and Warshall and Floyd matrices.
- You treat the weekly quizzes and tutorials as exam rehearsal and keep a running sheet of paradigms, recurrence cases and the standard graph algorithms.
- You can identify which design paradigm (decrease, divide-and-conquer, dynamic programming or greedy) a new problem calls for and explain why it gives the required bound.
You may struggle if
- You rely on being able to code a working program, because the 60% exam rewards correct hand traces and tight, justified asymptotic bounds, not a running implementation.
- You leave recurrences, the Master Theorem and the tree and heap traces until swotvac; they compound and cannot be crammed cold under a 30/60 hurdle.
- You are shaky on discrete-maths foundations (summations, logs, induction-style arguments) that the analysis questions assume.
- You memorise named algorithms without understanding the paradigm, so an unfamiliar problem in Questions 3 to 10 leaves you with no method to design a solution and prove its time bound.
- Build a one-page master sheet: the Master Theorem cases (compare log_b a with d), the standard recurrence solutions, AVL and 2-3 tree rules, heap operations, and the running times of DFS, BFS, topological sort, Prim, Dijkstra, Warshall and Floyd.
- Drill the trace questions cold: AVL rotations and 2-3 node splits on a given key sequence, heapify then delete-min, linear-probing tables, and Horspool shifts, since these are near-guaranteed MCQ and short-answer marks.
- Practise designing an algorithm to a stated time bound (for example O(|V| + |E|) connected components or an O((n + m) log n) nearest-site problem) and writing the formal time-and-space justification, because that is where the hard marks sit.
- Sit the sample exam under timed, semi-open-book conditions to learn what notes actually help in 180 minutes, then prune your allowed paper materials to the essentials.
Syllabus
The 12 topics, week by week
The exam-weight marker on each topic shows where the marks concentrate. The amber topics carry the highest exam weight.
T1 · Introduction, overview and data structures
Levitin Ch 1What an algorithm is, the problem-solving framework, fundamental data structures (arrays, linked lists, stacks, queues, graphs, trees), and the word-RAM cost model used for the rest of the subject.
T2 · Analysis of algorithms
Levitin Ch 2Asymptotic notation (O, Omega, Theta), worst, average and best case, analysing non-recursive and recursive algorithms, and setting up and solving basic recurrences.
T3 · Brute force methods and recursion
Levitin Ch 3 (except 3.5)Selection sort and bubble sort, sequential and brute-force string matching, closest-pair and convex-hull by brute force, exhaustive search for the travelling salesman and knapsack problems, and recursive thinking.
T4 · Graphs and graph traversals
Levitin Sec 3.5 and 4.2Graph representations (adjacency matrix versus list), depth-first and breadth-first search, the DFS and BFS forests, and applications: connected components, cycle detection and the basics of traversal-based reasoning.
T5 · Decrease-and-conquer methods
Levitin Ch 4 (except 4.3)Decrease-by-a-constant, by-a-constant-factor (binary search) and by-a-variable-amount; insertion sort, topological sorting via DFS, and generating permutations and subsets.
T6 · Divide-and-conquer methods and the Master Theorem
Levitin Ch 5 (Sec 5.1 to 5.3)Mergesort and quicksort, binary-tree traversals and reconstruction, the divide-and-conquer recurrence, and the Master Theorem you are expected to remember and apply (compare log_b a with d).
T7 · Priority queues, heaps and heapsort; transform-and-conquer
Levitin Sec 6.4 and 6.1The binary heap (array representation, heapify, sift-up and sift-down), insert and delete-min, heapsort, and the transform-and-conquer idea (presorting and instance simplification). Assignment 1 due Week 7.
T8 · Balanced search trees; time and space tradeoffs
Levitin Sec 6.3, 7.1 and 7.2AVL trees (the four rotations: L, R, LR, RL) and 2-3 trees (node splitting), keeping search trees balanced for guaranteed logarithmic height, and the first space-for-time tradeoffs (sorting by counting, input enhancement).
T9 · Hashing; dynamic programming
Levitin Sec 7.3 and Ch 8Hash tables, separate chaining versus open addressing (linear probing), load factor and collisions, and the start of dynamic programming: overlapping sub-problems, optimal substructure and memoisation versus bottom-up tables.
T10 · Dynamic programming; greedy algorithms
Levitin Ch 8Dynamic programming on coin-change, knapsack, longest common subsequence and Warshall's and Floyd's transitive-closure and all-pairs-shortest-path algorithms; the greedy strategy and when it is provably optimal.
T11 · Greedy algorithms; Huffman coding
Levitin Ch 9 and Sec 9.4Prim's and Dijkstra's algorithms (minimum spanning tree and single-source shortest paths), the greedy exchange argument, and Huffman encoding for optimal prefix codes. Assignment 2 due Week 11.
T12 · NP-completeness and review
Review across all lecturesAn introduction to tractability, P versus NP and NP-completeness (subject to class progress), then a synthesis and exam-style revision across all the paradigms and data structures.
How it's assessed
Assessment structure
| Component | Weight | Format & timing |
|---|---|---|
| Weekly quiz questions (10 weeks) | 10% | Online quiz questions set across 10 teaching weeks, testing the week's algorithms, data structures and analysis. Weekly across the semester. Low individual stakes but they compound; they are the cheapest exam rehearsal. |
| Assignment 1 | 15% | Programming and analysis assignment applying the early paradigms (analysis, brute force, graphs, decrease-and-conquer). Due 23:59, Week 7. Due dates are fixed and not movable except for a compelling, documented reason. |
| Assignment 2 | 15% | Programming and analysis assignment on the later paradigms (divide-and-conquer, heaps and trees, hashing, dynamic programming and greedy). Due 23:59, Week 11. Due dates are fixed and not movable except for a compelling, documented reason. |
| Written examination | 60% | A 3-hour written exam (15 minutes reading + 180 minutes writing): Q1 is 10 single-answer multiple-choice (10 marks), Q2 is 5 true-or-false with justification (10 marks), and Q3 to Q10 are written short-answer and algorithm-design problems (40 marks). Semi-open book: paper copies of LMS materials (textbook, lecture slides, workshop solutions) are permitted. Formal examination period. Hurdle: you must score at least 30/60 on the written exam AND at least 50 overall to pass. |
- To pass you must obtain at least 30/60 on the written exam AND at least 50 overall. Missing the exam hurdle means you do not pass regardless of your assignment and quiz marks.
- Three hours, semi-open book (paper LMS materials permitted). Question 1 = 10 MCQ (data-structure and algorithm traces such as AVL rotations, 2-3 tree nodes, hashing chains, Warshall/Floyd matrices, traversal reconstruction, MST weight). Question 2 = 5 true-or-false with justification on asymptotics and search. Questions 3 to 10 = written problems: heapify and delete-min, Horspool shifts, recurrence solving (expansion and Master Theorem), dynamic-programming design, connected-components and Dijkstra-style algorithm design with formal time-complexity justification.
- Calculator policy: Not specified in the available course pages; the exam is a closed-form written paper testing hand-worked algorithm traces and analysis rather than numeric computation. Confirm the exact authorised materials against the official exam instructions.
This is an exam-cram unit. With the exams at 60% of the grade and the written examination alone at 60%, your result is overwhelmingly decided by how well you perform under time pressure. Hurdle: you must score at least 30/60 on the written exam AND at least 50 overall to pass.
Final exam timing: approx mid-to-late Nov 2026 (S2 2026 offering, formal examination period; confirm against the official exam timetable). Confirm the exact date and venue on the official exam timetable.
How to actually pass it
A weekly rhythm, two checklists, and the traps to avoid
The unit rewards consistency over cramming, and practice over re-reading. Here is the loop that works, then what to have nailed before each exam.
The weekly loop
Before the mid-semester checklist
- Lock in Assignment 1 (due Week 7) well before the deadline; the due date is fixed and not movable.
- Drill the early traces cold: asymptotic notation comparisons, brute-force string match, DFS and BFS forests, topological sort, and binary search and insertion sort.
- Make sure recurrence-by-expansion is automatic before the Master Theorem week, since divide-and-conquer builds on it.
- Sit each weekly quiz as timed rehearsal and keep the running master one-pager up to date.
Before the final heaviest topics
- Re-derive the Master Theorem decision (compare log_b a with d; Case 1 gives Theta(n^(log_b a)), Case 2 gives Theta(n^d log n), Case 3 gives Theta(n^d)) and solve a recurrence both by expansion and by the theorem.
- Drill every trace that has appeared as an MCQ: AVL rotations, 2-3 tree node creation, hashing chains and linear probing, Warshall R-matrices and Floyd D-matrices, traversal reconstruction, and MST total weight.
- Practise heapify and delete-min on an array, and a Horspool shifting sequence, until the steps are mechanical.
- Work the algorithm-design questions to a stated bound (connected components in O(|V| + |E|), a Dijkstra-style nearest-site search in O((n + m) log n)) and write the full time-and-space justification.
- Prepare your semi-open-book paper notes: condense the master one-pager onto pages you can actually navigate inside the 180-minute writing time, and remember the 30/60 exam hurdle.
The mistakes that cost marks
Counting on your code to carry you. The 60% exam is a written paper that does not run your code. Strong assignment marks will not save you if you cannot hand-trace a heap, rotate an AVL tree, or justify a running time. Skew revision toward the traces and the asymptotic arguments.
Skipping the recurrence groundwork. The Master Theorem is a shortcut, not a substitute for understanding. If recurrence-by-expansion is shaky, the divide-and-conquer and dynamic-programming questions collapse. Build that fluency before Week 6.
Memorising algorithms instead of paradigms. Questions 3 to 10 hand you unfamiliar problems and ask you to design an algorithm to a stated time bound. If you only recall named algorithms, you have no method. Learn each paradigm (decrease, divide-and-conquer, dynamic programming, greedy) as a reusable design tool.
Forgetting the exam hurdle. You must score at least 30/60 on the written exam and 50 overall. Strong quizzes and assignments cannot rescue a sub-30 exam. Treat the exam as the decisive component from Week 1.
Wasting the semi-open-book allowance. Bringing every printout you own is useless if you cannot find anything in 180 minutes. The students who benefit have condensed, navigable notes rehearsed against the sample exam, not a disorganised stack.
Teaching team
Who teaches COMP90038
The bios below are factual. The star ratings are not ours: they are impressions from students who have taken the unit, so you can hear from people who sat in the lectures.
Junhao Gan
Lectures and coordinates COMP90038 in the School of Computing and Information Systems, University of Melbourne. Research interest in designing practical algorithms with non-trivial theoretical guarantees for solving problems on massive data. Staff profile
Teaching team as listed in the unit materials reviewed. AskSia does not rate lecturers; star ratings are submitted by students who have taken COMP90038.
Formula & concept sheet
The vocabulary and formulas you must own
- Big-O, Omega, Theta
- f is O(g) if f grows no faster than g (an upper bound), Omega(g) if no slower (a lower bound), and Theta(g) if both (a tight bound). Used to state worst-, average- and best-case running times independent of machine constants.
- Master Theorem
- For T(n) = a T(n/b) + Theta(n^d) with a >= 1, b > 1, compare log_b a with d: Case 1 (log_b a > d) gives Theta(n^(log_b a)); Case 2 (log_b a = d) gives Theta(n^d log n); Case 3 (log_b a < d) gives Theta(n^d). Requires equal-sized sub-problems.
- Recurrence by expansion
- Unroll T(n) = a T(n/b) + f(n) level by level, sum the work per level, and count the number of levels (about log_b n) to get a closed form; the fallback when the Master Theorem does not apply.
- Decrease-and-conquer
- Reduce a problem to one smaller instance (by a constant, a constant factor, or a variable amount), solve that, and extend. Insertion sort, binary search and topological sort by DFS are examples.
- Heap (binary)
- A complete binary tree in an array where each parent dominates its children (min-heap: parent <= children). Insert sifts up, delete-min swaps the last leaf to the root and sifts down; both are O(log n), and heapify is O(n).
- AVL tree
- A self-balancing BST keeping every node's subtree heights within 1, restored after insertion by one of four rotations (L, R, LR, RL); this guarantees O(log n) height and search.
- 2-3 tree
- A balanced search tree where every internal node has 2 or 3 children and all leaves are at the same depth; overflow on insertion splits a node and promotes a key upward, keeping height logarithmic.
- Hashing
- Map a key k to a bucket via a hash function (e.g. h(k) = k mod m). Collisions are resolved by separate chaining (a list per bucket) or open addressing such as linear probing; performance depends on the load factor.
- Dynamic programming
- Solve a problem with overlapping sub-problems and optimal substructure by filling a table of sub-solutions (bottom-up) or memoising recursion (top-down), turning exponential brute force into polynomial time.
- Greedy algorithm
- Build a solution by repeatedly taking the locally best choice. Provably optimal only for problems with the greedy-choice property and optimal substructure (e.g. Prim, Dijkstra on non-negative weights, Huffman coding).
- Warshall's algorithm
- Computes the transitive closure of a directed graph in Theta(n^3) by allowing intermediate vertices 1..k one at a time: R_k[i][j] = R_(k-1)[i][j] OR (R_(k-1)[i][k] AND R_(k-1)[k][j]).
- Floyd's algorithm
- All-pairs shortest paths in Theta(n^3): D_k[i][j] = min(D_(k-1)[i][j], D_(k-1)[i][k] + D_(k-1)[k][j]), again admitting intermediate vertices one at a time.
Common acronyms: DFS = depth-first search; BFS = breadth-first search · DAG = directed acyclic graph; topological sort orders its vertices · MST = minimum spanning tree (Prim's algorithm, greedy) · BST = binary search tree; AVL and 2-3 trees keep it balanced · DP = dynamic programming (overlapping sub-problems + optimal substructure) · Master Theorem: compare log_b a with d for T(n) = a T(n/b) + Theta(n^d) · Heap ops: insert O(log n), delete-min O(log n), heapify O(n), heapsort O(n log n) · Connected components / traversal: O(|V| + |E|) · Dijkstra / Prim with a heap: O((|V| + |E|) log |V|) · Warshall / Floyd: Theta(n^3).
What students say
What students actually say about COMP90038
Recurring themes from student reviews, paraphrased in our own words.
- Widely regarded as a demanding core algorithms subject: the hand-worked analysis (asymptotics, recurrences, the Master Theorem) and the formal time-complexity justifications are what students find hardest.
- The 60% written exam with a 30/60 hurdle concentrates the pressure, so the trace and design questions reward sustained weekly practice over late cramming.
- The subject follows Levitin closely, and students lean on condensed one-page summaries of the paradigms, recurrence cases and standard graph algorithms.
- Demand is high for worked traces (AVL rotations, 2-3 splits, heapify, hashing, Warshall and Floyd) and for step-by-step recurrence and Master-Theorem walkthroughs.
- Revision clusters around the near-guaranteed MCQ traces and the algorithm-design questions where a correct, tightly-justified running time wins the marks.
Recurring student opinions, paraphrased and aggregated, not official course information.
Set texts
The prescribed reading
The syllabus references map straight onto these.
Introduction to the Design and Analysis of Algorithms
Levitin, A. (Pearson; 3rd edition recommended, any edition generally sufficient).
Where it fits
Prerequisites, related units & why it matters
COMP90038 assumes you can already program and have basic discrete-mathematics maturity (proof, summations and recurrences). It uses Levitin's Introduction to the Design and Analysis of Algorithms (3rd edition recommended). Check the official handbook entry for the exact enforced prerequisites and any prohibited combinations for your course.
Your COMP90038 study toolkit
Study the unit with Sia, not just read about it
Each tool already knows COMP90038: your syllabus, your texts, and where the marks are. Grouped by how you study, from first contact to exam week.
FAQ
Frequently asked questions
How is COMP90038 assessed?
Weekly quiz questions across 10 teaching weeks worth 10%, two programming-and-analysis assignments worth 15% each (due Weeks 7 and 11), and a 3-hour written exam worth 60%. To pass you must score at least 30/60 on the exam AND at least 50 overall.
What is the hurdle to pass COMP90038?
There is a single exam hurdle: at least 30 out of 60 on the written exam, plus at least 50 overall. If you miss the 30/60 exam hurdle you do not pass, no matter how strong your assignment and quiz marks are, so the exam is decisive.
Is the COMP90038 exam open book?
It is semi-open book. Paper copies of materials from the subject LMS (the textbook, lecture slides and solutions to workshop exercises) are authorised, but you may not bring a dictionary. It is a 3-hour written paper (15 minutes reading plus 180 minutes writing). Confirm the exact authorised-materials wording against the official exam instructions.
What does the COMP90038 exam look like?
Question 1 is 10 single-answer multiple-choice (AVL rotations, 2-3 tree nodes, hashing chains, Warshall and Floyd matrices, traversal reconstruction, MST weight), Question 2 is 5 true-or-false with written justification on asymptotics and search, and Questions 3 to 10 are written problems: heapify and delete-min, Horspool shifts, solving recurrences by expansion and the Master Theorem, dynamic-programming and graph-algorithm design with a formal time-complexity justification.
How much maths is in COMP90038?
A lot, relative to most coding subjects. You work asymptotic proofs (O, Omega, Theta), solve recurrences by expansion and with the Master Theorem (comparing log_b a with d), and justify the running time of every algorithm you design. The marks in the design questions are in the analysis, not just a working program.
What textbook does COMP90038 use?
Levitin's Introduction to the Design and Analysis of Algorithms (Pearson), with the 3rd edition recommended though any edition is generally sufficient. The semester plan maps each week to specific Levitin chapters and sections, and most lecture content is examinable except a few sections flagged by the coordinator.
Study COMP90038 with Sia
Work through analysis of algorithms, graphs, decrease-and-conquer methods and the rest of the unit with a tutor that knows it and quizzes you on the topics the assessments weight most heavily.
Start studying with Sia