University of Nottingham Ningbo China
The design, analysis and rigorous communication of efficient algorithms: translating problem statements into computational models, selecting suitable design paradigms, proving correctness, and analysing time and space complexity — from stable matching and graph algorithms through greedy design, divide and conquer, dynamic programming, network flow, reductions and computational intractability.
This module introduces the design, analysis and rigorous communication of efficient algorithms. Students learn to translate problem statements into computational models, select suitable design paradigms, prove correctness, and analyse time and space complexity. The course develops core methods in stable matching, graph algorithms, greedy design, divide and conquer, dynamic programming, network flow, reductions and computational intractability. It also provides an introductory treatment of linear programming, approximation algorithms and lower-bound reasoning.
Algorithmic problem solving requires more than implementing code. Students must be able to justify why an algorithm is correct, understand when it is efficient, recognise when a natural approach fails, and explain the consequences of modelling choices. The module therefore emphasises pseudocode, mathematical proof, counterexamples, reductions, and clear written reasoning alongside selected programming exercises.
| Learning Activity | Indicative Hours | Purpose |
|---|---|---|
| Lectures | 32 hours | Two hours per week: concepts, worked examples and proof techniques |
| Tutorials / guided problem solving | 16 hours | One hour per week: design exercises, proof critique and exam-style practice |
| Independent study and reading | 20 hours | Textbook reading, review of lecture material and preparation |
| Eight homework assignments | 24 hours | Approximately three hours per assignment |
| Examination preparation and completion | 8 hours | Review and completion of two midterms and a comprehensive final |
First- and second-year students who have not completed the prerequisite courses may submit an application to obtain an add code for the course.
By the end of the module, a successful student should be able to:
Readings refer to Kleinberg & Tardos, Algorithm Design (KT), with selected sections from Cormen, Leiserson, Rivest & Stein (CLRS) and instructor notes.
| Week | Lecture Topics | Key Concepts and Algorithms | Reading | Assessment Milestone |
|---|---|---|---|---|
| 1 | Foundations of algorithm design | Problem specification; pseudocode; correctness; O, Ω, Θ; worst-case analysis; induction and loop invariants | KT, introductory analysis sections | HW 1 assigned |
| 2 | Stable matching and recurrences | Gale–Shapley; termination and stability; proposer-optimality; recurrences; Master Theorem; modelling implications | KT, stable matching and analysis sections | HW 1 due |
| 3 | Graph search | Graph representations; BFS; DFS; connected components; reachability; shortest unweighted paths | KT, graph algorithms sections | HW 2 assigned |
| 4 | Directed graphs and modelling | Topological sorting; strongly connected components; bipartite testing; reductions to graph problems | KT, graph algorithms sections | HW 2 due |
| 5 | Greedy design I | Interval scheduling; minimising lateness; optimal caching; greedy-choice property; stays-ahead proofs | KT, greedy algorithms sections | HW 3 assigned |
| 6 | Greedy design II | MST cut/cycle properties; Kruskal; Prim; Dijkstra; Huffman coding; failure cases | KT, greedy algorithms sections | HW 3 due Midterm 1 review |
| 7 | Divide and conquer I | Merge sort; binary-search variants; counting inversions; recurrence formulation and analysis | KT, divide-and-conquer sections | Midterm 1 HW 4 assigned |
| 8 | Divide and conquer II and lower bounds | Selection; closest pair; maximum subarray; fast multiplication; comparison-tree lower bounds; brief pattern-matching application | KT and CLRS selected sections | HW 4 due |
| 9 | Dynamic programming I | Optimal substructure; memoisation/tabulation; weighted interval scheduling; 0/1 knapsack; reconstruction | KT, dynamic-programming sections | HW 5 assigned |
| 10 | Dynamic programming II | LCS/LIS; sequence alignment; grid DP; Bellman–Ford; negative edges; space optimisation | KT, dynamic-programming sections | HW 5 due Midterm 2 review |
| 11 | Advanced dynamic programming | Adding state parameters; DP on trees; correctness and runtime; integration of paradigms | KT and instructor notes | Midterm 2 HW 6 assigned |
| 12 | Network flow fundamentals | Flow networks; residual graphs; augmenting paths; Ford–Fulkerson; Edmonds–Karp; max-flow/min-cut | KT, network-flow sections | HW 6 due |
| 13 | Network flow applications | Bipartite matching; assignment; edge-disjoint paths; circulation with demands; modelling transformations | KT, network-flow sections | HW 7 assigned |
| 14 | Computational complexity and reductions | Decision problems; P and NP; certificates; polynomial reductions; SAT/3-SAT; Independent Set, Vertex Cover, Clique | KT, NP-completeness sections | HW 7 due |
| 15 | Intractability, LP and approximation | Hamiltonian Cycle/TSP reductions; proving NP-hardness; linear-programming models; 2-approx Vertex Cover; greedy Set Cover; brief randomisation | KT, approximation/LP sections | HW 8 assigned |
| 16 | Synthesis and comprehensive assessment | Paradigm selection; modelling choices; cumulative problem solving; connections among flow, LP, reductions and approximation | Review materials and selected prior readings | HW 8 due Final examination |
The final module mark uses a fixed 20 / 20 / 20 / 40 distribution. No unlisted assessment component may change this grading distribution.
Eight assignments, each worth 2.5% (one-eighth of the homework category), scheduled approximately once every two weeks.
Week 7. Asymptotic analysis; correctness; stable matching; graph search and modelling; greedy algorithms; introduction to divide and conquer.
Week 11. Divide and conquer; recurrences and lower bounds; dynamic-programming formulation, correctness and analysis; shortest paths with negative edges.
Week 16 / formal examination period. Comprehensive, with particular emphasis on advanced dynamic programming, network flow, reductions, NP-completeness, linear programming and approximation algorithms.
| Assignment | Weight | Timing | Principal Coverage |
|---|---|---|---|
| HW 1 | 2.5% | Weeks 1–2 | Asymptotic analysis, recurrences, proof review and stable matching |
| HW 2 | 2.5% | Weeks 3–4 | BFS/DFS, topological ordering, SCCs, bipartite testing and graph modelling |
| HW 3 | 2.5% | Weeks 5–6 | Greedy design, exchange arguments, MSTs, shortest paths and counterexamples |
| HW 4 | 2.5% | Weeks 7–8 | Divide and conquer, recurrence solving, inversions, selection and lower bounds |
| HW 5 | 2.5% | Weeks 9–10 | Weighted interval scheduling, knapsack, sequence problems and Bellman–Ford |
| HW 6 | 2.5% | Weeks 11–12 | Advanced DP, DP on trees, solution reconstruction and basic flow algorithms |
| HW 7 | 2.5% | Weeks 13–14 | Max-flow/min-cut, matching, assignment, disjoint paths and reductions |
| HW 8 | 2.5% | Weeks 15–16 | NP-completeness, approximation, linear programming and cumulative synthesis |
Typical homework structure. Each assignment contains short execution or counterexample questions and two to four long-form problems requiring algorithm design, pseudocode, proof and complexity analysis. A small implementation component may be included where it supports conceptual understanding.
Assessment emphasis. Marks reward a correct and unambiguous algorithm, an appropriate proof of correctness, valid runtime and space analysis, and clear mathematical communication. An unsupported final answer receives limited credit even when correct.
Unless a question states otherwise, a complete algorithmic solution should contain three distinct components:
Precise pseudocode or a clear language-independent procedure, including inputs, outputs and important data structures.
A proof using an appropriate method, not merely an example or an assertion that the algorithm is intuitive.
A justified asymptotic bound in terms of clearly defined input parameters, including major data-structure operations.
Students are expected to distinguish between a proof that an algorithm terminates, a proof that its output is feasible, and a proof that its output is optimal. For reductions, both directions of the equivalence must be justified where required, and the transformation itself must run in polynomial time.
Students may discuss general concepts and high-level approaches with classmates unless an assignment states otherwise. Every submitted solution, proof, pseudocode fragment and implementation must be written independently. Sources and collaborators that materially influenced a solution must be acknowledged. Sharing completed solutions, copying code or jointly composing a written proof is not permitted.
All work is subject to University of Nottingham academic-integrity requirements. Plagiarism, contract cheating, unauthorised collaboration, misrepresentation of sources and submission of work not produced by the student may be referred through the applicable academic-misconduct process.
External references, programming assistants and generative-AI systems may be used only to the extent explicitly permitted for a particular task. Unless the instructor states otherwise, students may use such tools for general study, syntax clarification and generation of additional practice questions, but not to produce a submitted algorithm, proof, reduction or written explanation. Any permitted material assistance must be disclosed. Students remain responsible for the correctness, originality and integrity of everything submitted.
Students who require reasonable adjustments should contact the appropriate university support service and the instructor as early as practical. Course materials should be provided in accessible digital formats where available. Alternative arrangements for timed assessments are governed by approved accommodations. Examples and case studies should be discussed critically, especially where an algorithmic model may disadvantage a population or omit important real-world constraints.
Primary Text
Principal source for stable matching, greedy algorithms, divide and conquer, dynamic programming, network flow, NP-completeness and approximation.
Supplementary
Alternative explanations, formal analysis and extended algorithm reference.
Supplementary
Concise treatment of design paradigms, flows, linear programming and complexity.
Supplementary
Problem-solving and proof-oriented perspective.
Course Materials
Used to align terminology, proof expectations and assessment format.
Students at the University of Nottingham Ningbo China access module information and services through the following official university systems. For the full list, visit the UNNC Information for Students hub (official university website).
Central information hub and service centre — university news, notices, events and student service applications.
Essential student record and registration system.
Online learning management system.
Module results and student evaluation system.
Access your University email account online.
Library services, academic calendar, teaching timetable and examinations — all linked from the UNNC Portal.
Module Instructor — CELE N086 Introduction to Algorithms
Office hours, consultation arrangements and contact details are communicated through official module channels at the University of Nottingham Ningbo China.
Contact details are taken from the official UNNC Information for Students hub. Students requiring accessibility adjustments can also contact the Disability Support Service at disability-support@nottingham.edu.cn.
Milestones are stated by teaching week of the 16-week Autumn semester. All dates are subject to official university timetabling and any updates issued by the instructor.
| Week | Milestone | Weight |
|---|---|---|
| Week 2 | Homework 1 due | 2.5% |
| Week 4 | Homework 2 due | 2.5% |
| Week 6 | Homework 3 due; Midterm 1 review | 2.5% |
| Week 7 | Midterm Examination 1 | 20% |
| Week 8 | Homework 4 due | 2.5% |
| Week 10 | Homework 5 due; Midterm 2 review | 2.5% |
| Week 11 | Midterm Examination 2 | 20% |
| Week 12 | Homework 6 due | 2.5% |
| Week 14 | Homework 7 due | 2.5% |
| Week 16 | Homework 8 due | 2.5% |
| Week 16 / exam period | Comprehensive Final Examination | 40% |