COMPSCI320 Applied Algorithmics

How COMPSCI320 is assessed

Weights come from the Semester 2 2026 assessment overview and total 100%. To pass, students need at least 50% of the total marks and a pass in both the practical component (the assignments) and the written component (the test plus the exam). The printed header of the 2026 midterm question paper states 10%, while the answer version of the same paper, the assessment overview, the schedule and the course home page give 20%. Confirm permitted exam materials on your exam timetable in SSO.

Current COMPSCI320 dates

Dates are as published in the Semester 2 2026 Canvas course summary and exam page. Confirm exact deadlines and submission settings in the live LMS.

What COMPSCI320 covers

The course moves from asymptotic analysis and a review of graph algorithms through stable matching, greedy algorithms, divide and conquer and dynamic programming to network flow and NP-completeness. The chapter order follows the published teaching schedule, so each technique arrives after the analysis tools it relies on.

Its prescription covers fundamental design techniques for efficient problem solving, methods that are provably correct and efficient, the efficiency analysis that decides which algorithm suits a job, and the limits of computation through NP-completeness.

The learning outcomes ask students to define a computational problem precisely, design an algorithm with a named technique, estimate its big-Theta running time, choose the most promising technique for a new problem, and map a hard problem onto an NP-hard one with a formal reduction.

How the semester is organised

The Semester 2 2026 schedule runs in two-week blocks.

Weeks 1 and 2 introduce algorithm analysis and review graph algorithms from the prerequisite course, with stable matching and a case study on Perrin numbers. Weeks 3 and 4 cover greedy algorithms, Weeks 5 and 6 divide and conquer, Weeks 7 and 8 dynamic programming, Weeks 9 and 10 network flow, and Weeks 11 and 12 NP-completeness.

Six programming assignments run alongside, one per technique, submitted to an automated marker.

What the assessment asks for

The assignments carry 30%, the midterm test 20% and the final exam 50%. The final is an in-person invigilated exam on paper. To pass, a student needs at least half of the total marks and a pass in both the practical and the written components.

The 2026 midterm shows the written style: definitions with explicit constants, an algorithm trace, counterexamples to greedy rules, and recurrence work with an induction proof.

How to use this guide

Each chapter opens with a computed figure and the definitions you need, works one original example in full, and ends with practice questions whose model answers show the structure a marker expects.

Rebuild every example without looking, then change one feature of the instance and decide whether the technique still works.

Worked example · free

Trace Dijkstra and read off the shortest-path tree

Key terms

Algorithmics

The study of how algorithms are designed and how their correctness and efficiency are analysed.

Big-Theta Bound

A statement that a running time is bounded above and below by constant multiples of the same function.

Greedy Algorithm

An algorithm that builds a solution through a sequence of locally best, irrevocable choices.

Exchange Argument

A proof that rearranges any optimal solution into the greedy one without making it worse.

Divide and Conquer

A design technique that splits a problem into smaller instances, solves them recursively and combines the answers.

Master Theorem

A rule giving the Theta class of a recurrence of the form aT(n/b) plus a power of n.

Dynamic Programming

A design technique that stores the answers of overlapping subproblems so each is solved once.

Edit Distance

The cheapest total penalty of an alignment between two strings.

Negative Cycle

A directed cycle whose edge lengths add to less than zero.

Residual Graph

A graph of the spare and cancellable capacity left by a flow.

Minimum Cut

A source-sink split of the vertices with the smallest total capacity of edges leaving the source side.

Polynomial-Time Reduction

A transformation that solves one problem using polynomially many steps and calls to a solver for another.

NP-Complete Problem

A problem in NP to which every problem in NP reduces in polynomial time.

Certificate

A short piece of evidence that a certifier can check to confirm a yes answer.

COMPSCI320 FAQ

Questions students ask in each COMPSCI320 chapter

Why does a proof of Big-O need the constants written out?

Big-O is defined by the existence of a constant multiplier and a threshold beyond which the inequality holds. Naming them, for example c = 17 and n0 = 1, turns the claim into something a marker can check line by line. A sentence saying the leading term dominates states the intuition but proves nothing about the definition. Chapter 01 · Asymptotic Analysis and Algorithm Efficiency

Why can Dijkstra not revisit a permanent vertex?

It makes a vertex permanent only when its tentative distance is the smallest among unfinished vertices. With non-negative edge weights, any other route must pass through a vertex whose distance is already at least as large, so it cannot be shorter. That argument fails once negative edges are allowed, which is why a different algorithm is needed for them. Chapter 02 · Graph Traversal, Shortest Paths and Spanning Trees

Is a matching stable if one person would like to switch?

Yes, it can still be stable. Stability only fails when two people would both rather be matched to each other. If a hospital prefers another student but that student prefers her current partner, the pair does not block, so the matching survives. The definition protects mutual preference, not the happiness of every individual. Chapter 03 · Stable Matching and the Gale-Shapley Algorithm

What must a greedy counterexample contain to earn full marks?

It needs a specific instance, the solution the greedy rule actually produces on it with its value, and a strictly better feasible solution with its value. A sentence saying the rule can fail earns nothing. Small instances work best because the marker can verify each solution at a glance, and one line explaining why greedy missed the better answer completes it. Chapter 04 · Greedy Algorithms and Exchange Arguments

Why can greedy colouring never need more than maximum degree plus one colours?

When a vertex is coloured, at most d of its neighbours already have colours, where d is the maximum degree. So at most d colours are blocked, and one of the colours from 1 to d + 1 is always free. The rule therefore never reaches colour d + 2, whatever order the vertices are visited in. Chapter 05 · Greedy Graph Colouring and Interval Partitioning

Which constants must I state when applying the Master theorem?

Name a, the number of recursive calls, b, the factor by which the input shrinks, and c, the exponent of the combining work. Then compute the logarithm of a to base b, say which of the three cases holds and give the Theta class. Mergesort, with a = 2, b = 2 and c = 1, falls in the middle case and gives n log n. Chapter 06 · Divide and Conquer Recurrences and Inversions

Why does saving one multiplication change the exponent?

The number of recursive calls sets the number of leaves in the recursion tree. Four half-size calls give four to the power log n leaves, which is n squared. Three calls give three to the power log n, which is n to about 1.585. The extra additions cost only linear time per level and cannot outweigh the smaller leaf count. Chapter 07 · Fast Multiplication and the Fast Fourier Transform

What should come first in a dynamic programming answer?

The state definition, written in words. Say exactly what one entry means, for example the best weight using the first i vertices, and check that the original problem is one of the entries. The transition, base cases and running time all follow from that sentence, and a wrong or vague state is the most common reason a recurrence fails. Chapter 08 · Dynamic Programming Foundations

Why are the first row and column of the table not zero?

They align a prefix of one string with the empty string, so every character of that prefix is left unmatched and pays the gap penalty. The entry for a prefix of length i is therefore i times the gap penalty. Writing zeros there is the most common slip on these tables and shifts every later entry. Chapter 09 · Sequence Alignment, Edit Distance and Linear Space

Why does adding a constant to every edge not fix Dijkstra?

Adding the same amount to each edge penalises a path once per edge, so paths with many edges grow more than paths with few. The shortest path can therefore change after the shift. The lecture shows a small graph where the true shortest route uses three edges but becomes longer than a one-edge route once every length is increased. Chapter 10 · Shortest Paths with Negative Weights

Why does a cut's capacity ignore edges pointing back to the source side?

Capacity measures the most flow that could leave the source side, so only edges from the source side to the sink side count. Flow on edges coming back is subtracted when computing the net flow across the cut, but it never adds capacity. Counting those edges is a frequent slip and makes a cut look larger than it is. Chapter 11 · Maximum Flow and Minimum Cut

How many phases does capacity scaling use?

The threshold starts at the largest power of two not exceeding the largest capacity C and halves until it reaches 1, so there are one plus the floor of log base two of C phases. The lecture shows each phase uses at most 2m augmentations, giving a total running time of m squared times log C. Chapter 12 · Faster Flow Algorithms and Flow Modelling

Which way should a hardness reduction go?

From the known hard problem to the new one. To show a new problem Y is hard, take an arbitrary instance of a known NP-complete problem X and build an instance of Y with the same answer, proving X ≤p Y. Reducing Y to X only shows Y is no harder than X, which says nothing about its difficulty. Chapter 13 · NP-Completeness and Polynomial-Time Reductions

How to study for the exam

Revise in three passes. In the first, make each technique fluent on its own: write the definitions with their constants, trace Dijkstra, Gale-Shapley, Ford-Fulkerson and Bellman-Ford on new instances, solve recurrences with the Master theorem, and fill dynamic programming tables with their tracebacks.

In the second, rehearse the proofs: stays ahead, exchange, clique lower bounds, induction on recurrences, the max-flow min-cut certificate and two-direction reductions, each written with labelled steps. In the third, mix problems so that choosing the technique becomes part of the question, which is what the learning outcomes demand.

Time yourself at the midterm pace of one and a half minutes per mark, and end every design answer with a running time. Keep the integrity rules of the course in mind: this guide is for study and revision, not for completing assessed work.

Your AI Computer Science tutor for COMPSCI320

Stuck on a hard COMPSCI320 question? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Applied Algorithmics question and get a clear, step-by-step explanation grounded in how the course is actually taught and assessed. Read this whole study guide free, then take your hardest questions to Sia.