AX26-CS-101 · 2026-27

Algorithm Design

Specify a problem, design an algorithm, prove partial correctness, and give a complexity bound that matches the model of computation used.

Course topics

Detailed syllabus and learning aims

Produce examination-style arguments that keep specification, invariant, and runtime in one chain rather than as disconnected slogans.

01 Specifications and proof 20h

Learning result Write preconditions, postconditions, and a correctness claim that can fail if either is dropped.

Formative check Four-option check
02 Invariants 20h

Learning result Propose an invariant, prove initialisation, maintenance, and termination.

Formative check Written derivation
03 Complexity 20h

Learning result Give a worst-case bound with an explicit cost model and a matching family of inputs.

Formative check Written derivation
04 Recursive design 15h

Learning result Turn a recurrence into a runtime bound using a tree or Master-method case that applies.

Formative check Written derivation
05 Divide and conquer 15h

Learning result Identify divide, combine, and the size of subproblems on a standard problem such as mergesort.

Formative check Four-option check
06 Greedy algorithms 20h

Learning result Give an exchange or stay-ahead argument, or a counterexample showing greed fails.

Formative check Counterexample
07 Dynamic programming 20h

Learning result State the subproblem, the recurrence, and the evaluation order.

Formative check Written derivation
08 Examination synthesis 20h

Learning result Produce one end-to-end argument: specify, design, prove, analyse.

Formative check Written derivation

For a stated computational problem, give a specification, an algorithm, an invariant or induction, and a big-O bound with a cost model.

Loop invariants, induction, recurrences, greedy exchange, dynamic-programming substructure.

Separate “it worked on examples” from a proof; name the model when quoting a runtime.

State the specification, invariant and complexity measure before writing detailed code.

Design and analyse algorithms on concrete instances with explicit correctness claims.

Prove correctness and transfer the complexity argument to a related problem.