COMPSCI220: pass the exams, not just read the notes
Your complete guide to University of Auckland's algorithms and data structures course. See where the marks are, work real practice questions, and study with an AI tutor that knows COMPSCI220.
Sia generates COMPSCI220 practice questions, walks through algorithm analysis and merge sort step by step, and quizzes you on the material the exam weights most heavily.
Worked example
An algorithm has running time described by T(n) = 2T(n/2) + n, with T(1) = 1. What is the tightest asymptotic bound for T(n)?
Recognise the shape. Each call splits the problem into two halves and does linear work to combine them. This is the merge sort recurrence.
Continue to the base case. After k levels you have 2^k subproblems of size n/2^k, and the recursion stops when n/2^k = 1, so k = log base 2 of n. There are therefore log n levels.
Total the work. Each of the log n levels contributes n units of combine work, giving n log n, plus n units for the base cases. The dominant term is n log n, so T(n) is Theta(n log n).
The trap: Adding the per-level cost instead of multiplying by the number of levels, which yields Theta(n) and option B. The linear term n in the recurrence is the work done at each level, not the total. The other frequent error is assuming that any recurrence with a factor of 2 must be quadratic, which gives option C. classic slip!
One exam decides 50% of your grade. Theory component. Invigilated. This whole page is built around that.
Overview
What COMPSCI220 is, and where it sits
COMPSCI 220 is the University of Auckland's compulsory second-year algorithms course and the point at which computer science stops being about making programs work and starts being about proving how well they work. the prescription covers the analysis of algorithms and data structures, common abstract data types and their implementations, asymptotic complexity analysis, sorting and searching, depth-first and breadth-first search with applications, and graph optimisation problems.
The course is built on a single habit: counting. Almost every question reduces to counting elementary operations, expressing that count as a function of input size, and then classifying the function with Big-O, Big-Omega or Big-Theta. Once sorting arrives you also need to write and solve recurrences, and once graphs arrive you need to execute traversal and optimisation algorithms by hand on a drawn graph.
Assessment is heavily weighted toward invigilated work. The final exam alone is 50%, two timed tests add another 35%, and the remaining 15% of coursework is marked for completion rather than quality. That structure is generous with the coursework and unforgiving in the exam room, and it is compounded by a dual-pass rule requiring you to pass both the theory and the practical halves as well as the course overall.
Always treat your own course outline and the exam timetable as authoritative.
Difficulty & time commitment
Is COMPSCI220 hard, and how much time does it take?
COMPSCI220 is manageable if you keep a weekly rhythm and treat the back half as the main event. The pattern is consistent: it starts gently and steepens, and the heaviest assessment is the part that separates grades.
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 course.
Is this course for you
Who tends to do well, and who tends to struggle
You will likely do well if
- You can count elementary operations in a loop nest without hand-waving, and express the count as a function of n before reaching for a complexity class.
- You are willing to solve recurrences by unrolling on paper repeatedly until the pattern is instinctive rather than looked up.
- You execute algorithms by hand. Running heapsort, quicksort, breadth-first search and a shortest-path algorithm on a drawn example is the actual exam skill.
- You build your A4 cheat sheet progressively through the semester instead of assembling it the night before a test.
You may struggle if
- You treat the completion-marked assignments as the course and arrive at the tests having never worked a problem unaided.
- You recognise complexity classes by memory rather than deriving them, which fails as soon as the exam gives an unfamiliar recurrence.
- You leave the graph material until the exam period. It arrives late, it is only examined in the final, and it carries real weight.
- You rely on a calculator or an IDE to check your reasoning. Neither is available in the tests.
- Master recurrence solving early. It is the single highest-leverage skill in the course, it appears in both tests and the exam, and it is method-based so it can be made reliable.
- Keep a worked-example notebook: one clean hand-execution of each major algorithm on a small input, which you can revise from directly.
- Learn to prove asymptotic relations formally, not just to state them. The learning outcomes ask you to express a precise relation between two functions using Big-O, Big-Omega and Big-Theta.
- Practise under the real constraint: 45 minutes, one A4 sheet, no calculator. Timing failure, not knowledge failure, is what costs marks in the tests.
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 · Algorithm analysis and running time
Lectures L1 to L3Worst-case and average-case running time, input size, elementary operations, and how to compare two algorithms honestly.
T2 · Selection sort and insertion sort
Lectures L4 to L5The two quadratic sorts, their exact operation counts, and the cases where insertion sort beats its worst case.
T3 · Merge sort and divide and conquer
Lecture L6Splitting, sorting and merging, and the recurrence that describes the cost of doing so.
T4 · Quicksort
Lecture L7Partitioning, pivot choice, and why the average and worst cases differ so sharply.
T5 · Solving recurrences
Lecture L8Unrolling, substitution and recursion trees to turn a recurrence into a closed-form complexity.
T6 · Sorting lower bound and algorithmic hardness
Lecture L9The decision-tree argument that no comparison sort can beat n log n, and what that tells you about hardness.
T7 · Binary heaps and heapsort
Lecture L10The heap property, sift up and sift down, building a heap, and sorting with one.
T8 · Search trees and self-balancing trees
Lectures L11 to L12Binary search trees, why unbalanced trees degrade to linear cost, and the selection problem.
T9 · Asymptotic notation formalised
Lectures L14 to L15Big-O, Big-Omega and Big-Theta as precise relations between functions, and proving one function bounds another.
T10 · Hashing and dictionaries
Lecture L16Hash functions, collision resolution by chaining and open addressing, load factor, and expected lookup cost.
T11 · Graph representations and traversal
Prescription and CLO 6Adjacency lists and matrices, depth-first and breadth-first search, and their standard applications.
T12 · Graph optimisation problems
Prescription and CLO 6Shortest-path and minimum-spanning-tree algorithms executed by hand on a given graph.
How it's assessed
Assessment structure
| Component | Weight | Format & timing |
|---|---|---|
| Final exam | 50% | Invigilated final examination covering the full course, including graph algorithms. University of Auckland Semester 1 examination period. Theory component. Invigilated. |
| Test 1 | 17.5% | 45-minute invigilated test. One A4 cheat sheet permitted; no calculators or electronic devices. Around Week 5. Theory component. Invigilated. |
| Test 2 | 17.5% | 45-minute invigilated test. One A4 cheat sheet permitted; no calculators or electronic devices. Around Week 10. Theory component. Invigilated. |
| Written assignments | 5% | Four written assignments at 1.25% each, marked for completion on an honest attempt. Across the semester. Practical component. |
| Programming assignments | 5% | Four programming assignments at 1.25% each, submitted through the automarker and marked for completion. Across the semester. Practical component. |
| Tutorial presentations | 4% | Two tutorial presentations at 2% each. Across the semester. Practical component. |
| Mathematical prerequisites quiz | 1% | A short quiz confirming the logs, exponents, summations and proof techniques the course assumes. Week 1. Practical component. |
- You are required to pass the practical component (coursework) and the theory component (tests and exam) as well as achieving an overall pass. All three conditions must be met independently.
- The two tests are 45 minutes each with one A4 cheat sheet and no calculator, so they reward compact, well-organised notes and fast hand execution. The final exam is the only assessment that reaches the graph material, which arrives late in the semester and carries substantial weight.
This is an exam-cram course. With the exams at 50% of the grade and the final exam alone at 50%, your result is overwhelmingly decided by how well you perform under time pressure. Theory component. Invigilated.
Final exam timing: During the University of Auckland Semester 1 examination period. Confirm the exact date and venue on your exam timetable.
How to actually pass it
A weekly rhythm, two checklists, and the traps to avoid
The course 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
- Count elementary operations for nested loops and express the result in asymptotic notation.
- Execute selection sort, insertion sort, merge sort and quicksort by hand on a small array and state each one's best, average and worst case.
- Write and solve the recurrences for merge sort and quicksort, including the unbalanced quicksort worst case.
- Perform heap operations by hand: sift up, sift down, build heap and extract, and run a full heapsort on a small input.
Before the final heaviest topics
- Cover the graph material thoroughly. Depth-first and breadth-first search, their applications, shortest paths and minimum spanning trees are only examined here.
- Be able to prove asymptotic bounds formally, not just recognise them.
- Revise hashing properly: collision resolution strategies, load factor, and expected versus worst-case lookup cost.
- Redo both tests under timed conditions, then work every unfamiliar recurrence you can find until the method is automatic.
The mistakes that cost marks
Confusing per-level work with total work in a recurrence. In T(n) = 2T(n/2) + n, the n is the combine cost at each level, not the total. Multiply it by the number of levels. Treating it as the total is the most common route to a wrong complexity.
Quoting average case when the question asks worst case. Quicksort is Theta(n log n) on average and Theta(n squared) in the worst case. Hashing is constant expected and linear worst case. The exam is specific about which it wants and marks accordingly.
Skipping the completion-marked coursework. It is only 15% of the grade, but it is a separately assessed component under the dual-pass rule and it is where the hand fluency comes from. Skipping it costs twice.
Building an unusable cheat sheet. A sheet transcribed from slides is unsearchable in a 45-minute test. Build it from the things you repeatedly get wrong and the derivations you do not want to redo under pressure.
Formula & concept sheet
The vocabulary and formulas you must own
- Big-O
- An asymptotic upper bound. f(n) is O(g(n)) when f grows no faster than a constant multiple of g beyond some input size.
- Big-Omega
- An asymptotic lower bound. f(n) is Omega(g(n)) when f grows at least as fast as a constant multiple of g beyond some input size.
- Big-Theta
- A tight asymptotic bound, holding when f is both O(g) and Omega(g), so the two functions grow at the same rate.
- Elementary operation
- The unit of work counted in the analysis, chosen so that its cost does not depend on input size, typically a comparison or an assignment.
- Recurrence relation
- An equation defining an algorithm's cost on input n in terms of its cost on smaller inputs, which must be solved to obtain a closed-form complexity.
- Merge sort recurrence
- T(n) = 2T(n/2) + n, which resolves to Theta(n log n): log n levels of recursion each doing n units of merge work.
- Comparison sort lower bound
- No sorting algorithm based solely on comparisons can do better than Omega(n log n) in the worst case, proved by counting leaves in the decision tree.
- Heap property
- In a max-heap every parent is at least as large as its children, which makes the maximum available in constant time and restoration logarithmic.
- Load factor
- In hashing, the ratio of stored elements to table slots. It governs expected collision cost and therefore expected lookup time.
- Collision resolution
- The strategy for storing two keys that hash to the same slot, either by chaining them in a list or by probing for another open slot.
- Breadth-first search
- Graph traversal that visits all vertices at the current distance before moving further, which yields shortest paths in an unweighted graph.
- Minimum spanning tree
- A subset of edges connecting every vertex of a weighted graph with no cycles and the smallest possible total edge weight.
Common acronyms: ADT · BFS · BST · DFS · MST.
Set texts
The prescribed reading
The syllabus references map straight onto these.
COMPSCI 120 online textbook (mathematical prerequisites)
University of Auckland School of Computer Science.
Where it fits
Prerequisites, related courses & why it matters
Prerequisite: COMPSCI 120 and COMPSCI 130. Restriction: COMPSCI 717 and SOFTENG 284. The course assumes the discrete mathematics from COMPSCI 120, particularly logs, exponents, summations and proof techniques, and confirms this with a Week 1 quiz.
Your COMPSCI220 study toolkit
Study the course with Sia, not just read about it
Each tool already knows COMPSCI220: your syllabus, your texts, and where the marks are. Grouped by how you study, from first contact to exam week.
FAQ
Frequently asked questions
Is COMPSCI 220 hard?
Yes. It rates hard on our six-factor scale, at the same level as our frozen hard anchor. The difficulty is not conceptual novelty so much as the fact that 85% of the grade is decided in invigilated papers where you must execute analysis by hand, quickly and correctly, with only one A4 sheet to help you.
What is the dual-pass rule?
You must pass the theory component (the two tests plus the final exam), pass the practical component (the coursework), and achieve an overall pass. Because the coursework is marked for completion, the practical half is straightforward to pass if you submit honest attempts, but it is not automatic and skipping it will fail you.
The assignments are marked for completion. Should I still take them seriously?
Yes, but for a different reason than usual. They contribute only 15% and an honest attempt earns full marks, so they are not where your grade is won. They are where you build the hand fluency that the tests and exam demand. Students who submit minimum-effort work to collect the completion marks arrive at the tests without the skill.
How do I prepare a cheat sheet for the tests?
You get one A4 sheet and no calculator, for 45 minutes. Put the recurrence-solving patterns, the standard complexity classes, the sorting algorithm invariants and the heap operations on it. Do not transcribe lecture slides. The sheet should hold the things you would otherwise waste minutes deriving.
Is there a textbook?
No printed textbook is formally prescribed. The course is slide-driven with annotated lecture slides and summary videos. For the Week 1 mathematical prerequisites the course points to the COMPSCI 120 online textbook, and the course provides its own detailed mathematical prerequisites resource covering logs, exponents, summations, recurrences and proof techniques.
What is the hardest part of the course?
For most students it is recurrences and the graph material. Recurrences are hard because they require a method rather than recall, and graph optimisation is hard because it arrives late, carries real exam weight, and is only assessed in the final. Both reward practice on paper rather than reading.
Study COMPSCI220 with Sia
Work through algorithm analysis, merge sort, quicksort and the rest of the course with a tutor that knows it and quizzes you on the topics the assessments weight most heavily.
Start studying with Sia
