The University of Hong Kong · FACULTY OF COMPUTER SCIENCE

COMP2121 Discrete Mathematics

- one subject, every graph, every model, every mark
11 Chapters55-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
The Complete Exam Bible · First Semester 2026-27

COMP2121 Overview

Discrete Mathematics
— State the definition, choose the method, and check the result.
  • The University of Hong Kong
  • First Semester, 2026-27
  • Level 2 undergraduate
  • Computer Science
  • Final examination plus continuous assessment

What this course covers

COMP2121 Discrete Mathematics at The University of Hong Kong gives a foundation in the mathematics that computer science is built on. The course homepage names five topic areas: logic; sets, relations and functions; counting; probability; and graphs.

  • Assessment Three homeworks, two in-class quizzes and a final examination worth half the grade make up the assessment.
  • Core skill Turn each definition into a quantified sentence, then prove it for an arbitrary element or refute it with one example.
  • Before the final Practise mixed questions under time and keep an error log organised by decision.
Why read this guide

What you get in the full COMP2121 Exam Bible

  1. 11 chapters, 55 pages — every examinable topic
  2. 28 original practice questions, each with a model answer in the Final examination format
  3. 11 worked examples, solved the way COMP2121 marks
  4. 20 computed figures, redrawn from the course’s own numbers
  5. Exam-morning plan for the Final examination (50%) — what to revise last, where marks are lost

Free on this page: assessment table, chapter map, one worked example, key terms, FAQ. The rest is in the full exam bible.

COMP2121 · The University of Hong Kong
An independent, AskSia-authored study guide. AskSia is not affiliated with, endorsed by, or sponsored by The University of Hong Kong; the course code and name are used for identification only.
Assessment

How COMP2121 is assessed

ComponentWeightFormat
Three written homeworks10%Not graded; on-time genuine submissions earn the points
Two in-class quizzes40%Held at normal lecture time and venue
Final examination50%AI and LLM tools strictly prohibited

The three published weights total 100%. Homeworks are not graded: each on-time, genuine submission earns 3 points and submitting all three adds a bonus point, for 10 in total. The final examination carries the other half of the grade. AI and LLM tools are prohibited in the quizzes and the final examination.

Assessment structure

10Quizzes 40%Final examination 50%Homeworks 10%

Segment widths reproduce the three published weights, which total 100%.

Other students are asking · COMP2121

What other students are asking about COMP2121

Where can I find lecture notes or study guides for COMP2121 at HKU?
The COMP2121 study guide in AskSia Library covers Discrete Mathematics in 11 chapters, with the assessment table, a chapter-by-chapter topic map, key terms and a worked example, free to read on this page.
Is there a final exam in COMP2121, and how much is it worth?
Yes. In the offering this AskSia Library guide is built from, Final examination carries 50% of the COMP2121 mark; the full split is Three written homeworks 10%, Two in-class quizzes 40%, Final examination 50%.
What does COMP2121 cover on proof methods and mathematical induction?
In AskSia Library's COMP2121 guide, the Proof Methods and Mathematical Induction chapter explains direct proof, contrapositive, contradiction, cases, weak and strong induction, recurrences and faulty proofs.
What does COMP2121 cover on big-o notation and sets?
In AskSia Library's COMP2121 guide, the Big-O Notation and Sets chapter explains big-O, Omega and Theta witnesses, sets, subsets, power sets, set operations and identities.
What does COMP2121 cover on relations and functions?
In AskSia Library's COMP2121 guide, the Relations and Functions chapter explains relation properties, equivalence relations and classes, injective, surjective and bijective functions.
Weights, dates and every chapter are set out with their sources further down this page.
Current dates · verify in LMS

Current COMP2121 dates

DateItemControl
17 November 2026Quiz 2At normal lecture time and venue.
24 November 2026Homework 3 dueSubmission to Moodle by 7pm.

Dates are as published in the official COMP2121 course information for this offering. Confirm exact deadlines and submission settings in the live LMS.

Contents · every chapter, one map

What COMP2121 covers

Eleven chapters follow the lectures from logic and proof through sets, functions, counting and probability to graphs.

01

Propositional Logic, Predicates and Quantifiers

truth tables, implication, equivalence laws, predicates, domains, quantifier negation and translation

Statements, operators and truth

The chapter starts with propositions, statements that are true or false but not both, and the six operators that combine them.

  • Propositions and truth tables
  • Implication and the biconditional
  • Equivalence laws
  • Predicates and domains
  • Quantifier negation
  • Translating English into logic
In the full guide: 5 pages · 2 practice questions · 2 figures
02

Proof Methods and Mathematical Induction

direct proof, contrapositive, contradiction, cases, weak and strong induction, recurrences and faulty proofs

Choosing a proof shape

A direct proof assumes the hypothesis and derives the conclusion. The contrapositive assumes the conclusion fails and shows the hypothesis fails.

  • Direct proof
  • Contrapositive
  • Proof by contradiction
  • Proof by cases
  • Weak and strong induction
  • Recurrences and faulty proofs
In the full guide: 5 pages · 2 practice questions · 2 figures
03

Big-O Notation and Sets

Big-O, Omega and Theta witnesses, sets, subsets, power sets, set operations and identities

Comparing growth

Big-O notation states that one function eventually grows no faster than a constant multiple of another. A proof names a constant c and a threshold N and checks the inequality for every n from N on.

  • Big-O definition with witnesses
  • Omega and Theta
  • Sets and membership
  • Subsets and equality
  • Power sets
  • Set operations and identities
In the full guide: 4 pages · 2 practice questions · 2 figures
04

Relations and Functions

relation properties, equivalence relations and classes, injective, surjective and bijective functions

Relations and equivalence

A relation on a set is a set of ordered pairs, drawn as a table or a directed graph. The chapter tests three properties, reflexive, symmetric and transitive, each written as a quantified statement.

  • Relations as ordered pairs
  • Reflexive, symmetric and transitive
  • Equivalence relations and classes
  • Domain, codomain and range
  • Injective and surjective functions
  • Bijections for counting
In the full guide: 3 pages · 2 practice questions · 1 figure
05

Counting Principles, Permutations and Combinations

product and sum rules, permutations, multisets, combinations, Pascal, stars and bars, pigeonhole

Two rules and their consequences

Multiply counts for choices made in sequence and add them for alternatives that cannot both happen.

  • Product and sum rules
  • Permutations
  • Arrangements with identical objects
  • Combinations and Pascal's identity
  • Stars and bars
  • Pigeonhole principle
In the full guide: 4 pages · 2 practice questions · 2 figures
06

Inclusion-Exclusion Counting

unions of two and three sets, the general formula, onto assignments, bounded solutions, derangements

Correcting an overcount

Adding the sizes of overlapping sets counts shared elements more than once. Inclusion-exclusion subtracts pairwise overlaps, adds back triple overlaps and continues with alternating signs.

  • Union of two sets
  • Union of three sets
  • General inclusion-exclusion
  • Onto assignments
  • Bounded integer solutions
  • Derangements
In the full guide: 3 pages · 2 practice questions · 1 figure
07

Probability and Conditional Probability

sample spaces, equally likely outcomes, conditioning, independence, total probability and Bayes

Sample spaces and equal likelihood

Probability starts with a sample space and events as its subsets.

  • Sample spaces and events
  • Equally likely outcomes
  • Conditional probability
  • Independence
  • Total probability
  • Bayes' theorem
In the full guide: 5 pages · 2 practice questions · 2 figures
08

Random Variables, Expectation and Variance

distributions, expectation, linearity, indicators, Bernoulli and binomial, waiting times, variance

Random variables and expectation

A random variable is a function from outcomes to numbers, and each of its values defines an event. Its expectation is a weighted average that can be summed over outcomes or over values.

  • Random variables as functions
  • Probability distributions
  • Expected value
  • Linearity and indicators
  • Independence and the product rule
  • Variance
In the full guide: 4 pages · 2 practice questions · 2 figures
09

Graphs, Isomorphism and Euler Circuits

degrees, handshaking, special graphs, bipartite graphs, isomorphism, connectivity, Euler paths and circuits

Graph vocabulary and counting degrees

A graph is a set of vertices and edges, simple unless stated otherwise. The handshaking theorem says the degrees sum to twice the number of edges, so every graph has an even number of odd vertices.

  • Vertices, edges and degree
  • Handshaking theorem
  • Complete, cycle, wheel and bipartite graphs
  • Isomorphism and invariants
  • Connectivity
  • Euler paths and circuits
In the full guide: 4 pages · 2 practice questions · 2 figures
10

Hamiltonian Paths and Circuits

tournaments, bipartite and independent-set obstructions, Dirac and Ore, travelling salesman

No simple test

Hamiltonian paths and circuits visit every vertex exactly once. Unlike the Euler question, deciding whether one exists has no simple criterion and is NP-hard.

  • Hamiltonian paths and circuits
  • Tournaments
  • Bipartite imbalance
  • Independent sets and forced edges
  • Dirac's and Ore's theorems
  • Travelling salesman problem
In the full guide: 3 pages · 2 practice questions · 1 figure
11

Planar Graphs and Graph Colouring

Euler's formula, edge bounds, non-planar graphs, chromatic number, greedy bounds, four colours

Planar graphs and Euler's formula

A planar graph can be drawn without crossings, and a connected planar drawing satisfies r equal to e minus v plus 2. Counting region degrees gives the bounds e at most 3v minus 6 and, for triangle-free graphs, e at most 2v minus 4, which prove that the complete graph on five vertices and the complete bipartite graph on three and three are not planar.

Colouring

The chromatic number is the fewest colours that give adjacent vertices different colours.

  • Planar drawings
  • Euler's formula
  • Edge bounds for planar graphs
  • Non-planar graphs
  • Chromatic number
  • Greedy colouring and four colours
In the full guide: 5 pages · 2 practice questions · 2 figures

Three outcomes run through them: understanding abstract concepts, using proof techniques such as induction and contradiction, and applying formal reasoning to count and analyse the outcomes of computational problems.

How the topics connect

Logic gives the language.

Every later definition, from a transitive relation to an injective function or a Big-O bound, is a quantified statement, and proving it means checking that statement for an arbitrary element. Counting turns sets into numbers through the product rule, permutations, combinations, stars and bars, the pigeonhole principle and inclusion-exclusion.

Probability reuses those counts whenever outcomes are equally likely and adds conditioning, independence, Bayes' theorem, random variables and expectation.

Graphs bring the tools together: degrees are counted, Euler's theorem is proved by construction, Hamiltonian questions need structural obstructions, and planarity and colouring combine counting bounds with explicit drawings.

How to prepare

The homework and practice sets reward complete, readable reasoning.

Declare domains before translating, label every part of an induction, prove yes answers in general and refute no answers with a small example, and give the reason beside every count. This guide follows the lecture sequence in eleven chapters, each with a fully worked original example and practice questions whose model answers are written out, so you can check each step of your own work against a complete solution.

Worked example · free

Reverse a test result with a probability tree

Q [6 marks]. AskSia-authored practice. This mark allocation is a study estimate and is not an official University marking scheme. A condition affects 1% of a population, a test detects it 95% of the time and gives a false positive 10% of the time. Find the probability that someone who tests positive has the condition.
A tree for a test with one per cent prevalence, 95 per cent sensitivity and a 10 per cent false positive rate.A tree for a test with one per cent prevalence, 95 per cent sensitivity and a 10 per cent false positive rate. First branches split by condition and second branches by test result; each leaf shows the product along its path, and the four leaves sum to one.disease 0.01+ 0.950.0095− 0.050.0005healthy 0.99+ 0.100.0990− 0.900.8910
A tree for a test with one per cent prevalence, 95 per cent sensitivity and a 10 per cent false positive rate. First branches split by condition and second branches by test result; each leaf shows the product along its path, and the four leaves sum to one.
  • 2Draw a tree with the condition first and the test result second.
  • 2Multiply along branches and add the two positive leaves.
  • 2Divide the true positive leaf by the total and interpret it.
The positive leaves are 0.0095 from people with the condition and 0.099 from people without it, so a positive result has probability 0.1085. The probability of the condition given a positive result is 0.0095 divided by 0.1085, about 0.088. Because the condition is rare, false positives from the large unaffected group outnumber true positives.
Sia tip — Check that the two leaf probabilities on the positive branches add to the probability of a positive result.
Glossary

Key terms

Proposition
A statement that is either true or false, but not both.
Logical equivalence
A relation between two formulas that agree under every assignment of truth values.
Mathematical induction
A proof method that establishes a basis case and an inductive step to cover every positive integer.
Big-O notation
A statement that a function is eventually bounded above by a constant multiple of another.
Power set
The set whose elements are every subset of a given set.
Equivalence relation
A relation that is reflexive, symmetric and transitive.
Bijection
A function that is both injective and surjective.
Pigeonhole principle
The rule that more objects than boxes force two objects into one box.
Inclusion-exclusion
A counting rule that corrects overlaps in a union with alternating signs.
Conditional probability
The probability of an event given that another event has occurred.
Expected value
The probability-weighted average of the values of a random variable.
Euler circuit
A circuit that uses every edge of a graph exactly once.
Hamiltonian circuit
A circuit that visits every vertex of a graph exactly once.
Chromatic number
The least number of colours that properly colours the vertices of a graph.
FAQ

COMP2121 FAQ

How is the course assessed?

The course homepage lists three components: three written homeworks worth 10%, two in-class quizzes worth 40% and a final examination worth 50%. Homeworks are not graded, but each on-time, genuine submission earns points, and submitting all three earns the full 10.

What is known about the final examination?

It carries 50% of the grade, matching the combined weight of the homeworks and quizzes. AI and LLM tools are strictly prohibited in it, and the plagiarism rules on the course homepage apply to it. Confirm the date, venue and paper rules in the official examination timetable and on Moodle when they are released.

Which topics does the course cover?

The course homepage names logic, then sets, relations and functions, then counting, probability and graphs. The lectures also cover proof methods with induction, Big-O notation, inclusion-exclusion, random variables, Euler and Hamiltonian circuits, planar graphs and colouring, so the guide gives each of these its own chapter.

What happens if I submit a homework late?

Work submitted within 24 hours after the deadline receives no penalty. After 24 hours no mark is given, and the course states that no reason, including medical or emergency reasons, is accepted for an extension, so submitting a preliminary file early is advised.

Can I use AI tools in this course?

The course encourages AI and LLM tools for learning and provides guidance on responsible use, such as thinking first and asking for hints rather than answers. Their use in the quizzes and the final examination is strictly prohibited, so practise solving without them.

How should I write proofs to earn marks?

Name the method, state assumptions precisely, give one justified step per line and end with the claim in words. Label the basis, hypothesis and step of an induction, prove yes answers in general and refute no answers with one small concrete counterexample.

Is there a textbook?

The course names Discrete Mathematics and Its Applications by Kenneth Rosen as an optional textbook, and any edition is fine. The course homepage notes that another reference book or other sources covering the course topics can be used instead, so this guide follows the lecture decks rather than any one book.

Chapter questions

Questions students ask in each COMP2121 chapter

When is an implication true?
It is false in one case only: the hypothesis holds and the conclusion fails. With a false hypothesis the implication counts as true, which is called vacuous truth, and this is a common source of lost marks. Chapter 01 · Propositional Logic, Predicates and Quantifiers
When should I use the contrapositive?
Use it when the negated conclusion gives a usable formula and the hypothesis does not, such as proving that n is odd from a property of an expression in n. Assuming the conclusion fails often produces the parity or remainder you need. Chapter 02 · Proof Methods and Mathematical Induction
What do the constants c and N do?
The constant c absorbs fixed factors such as a faster machine, and the threshold N lets you ignore small inputs where the slower-growing function happens to be larger. Any valid pair proves the bound. Chapter 03 · Big-O Notation and Sets
What is the difference between codomain and range?
The codomain is the set named as the target of the function. The range is the subset of outputs actually produced. Squaring on the integers has the integers as codomain but no negative numbers in its range. Chapter 04 · Relations and Functions
When do I divide by a factorial?
Divide when your count treats as different some arrangements that are really the same, such as orders within a chosen group or swaps of identical objects. The factorial is the number of such duplicate orders. Chapter 05 · Counting Principles, Permutations and Combinations
Why is the triple intersection added back?
An element in all three sets is counted three times by the single sets and removed three times by the pairwise overlaps, leaving it uncounted. Adding the triple intersection once restores it. Chapter 06 · Inclusion-Exclusion Counting
Why can I not count unordered dice outcomes?
Unordered outcomes are not equally likely: a double arises in one way and a mixed pair in two. Counting them as equal gives wrong answers, so count ordered pairs instead. Chapter 07 · Probability and Conditional Probability
Does linearity of expectation need independence?
No. The expectation of a sum equals the sum of the expectations for any random variables. That is why indicator variables can be added even when they depend on each other. Chapter 08 · Random Variables, Expectation and Variance
Why is the degree sum always even?
Each edge has two endpoints, so it adds two to the sum of degrees. The sum is therefore twice the number of edges, and the number of odd-degree vertices must be even. Chapter 09 · Graphs, Isomorphism and Euler Circuits
Is there a degree test for Hamiltonian circuits?
No simple necessary and sufficient test exists, and deciding the question is NP-hard. Dirac's and Ore's theorems are sufficient conditions only, so a graph that fails them may still have a circuit. Chapter 10 · Hamiltonian Paths and Circuits
Does satisfying the edge bound prove a graph is planar?
No. The bound is necessary but not sufficient. The complete bipartite graph on three and three vertices satisfies it and is still non-planar, which the triangle-free bound shows. Chapter 11 · Planar Graphs and Graph Colouring
Study strategy

How to study for the exam

Organise revision by the five topic areas the course lists, and inside each one keep three things: the definitions written as quantified sentences, one fully worked example you can reproduce, and a list of the decisions you have got wrong before. Work the homework and practice question types under time without notes, then compare with model solutions line by line and rewrite only the line where your work diverged.

For counting and probability, decide whether order matters, whether repeats are allowed and what the sample space is before writing any formula, and test every formula on a case small enough to list. For proofs, practise the first and last lines of each method until they are automatic. For graphs, always check connectivity and the hypotheses of a theorem before applying it.

In the final week, mix topics so that choosing the method becomes part of each question, as it will be in the examination.

Study COMP2121 with AI

Your AI Computer Science tutor for COMP2121

Stuck on a hard COMP2121 question? Sia is AskSia’s AI Computer Science tutor — ask any COMP2121 Discrete Mathematics 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.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP2121 tutor, unlimited, worked the way the exam marks it
The full 55-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works