Discrete Mathematics

🎯

Learning Goals

By the end of this course, students will be able to:

›Read, write, and evaluate propositional and predicate logic formulas, including truth tables and equivalence proofs.

›Apply rules of inference and formal proof techniques (direct, contrapositive, contradiction, induction).

›Work with sets, relations, and functions using formal notation and prove their properties rigorously.

›Use mathematical induction and strong induction to prove statements about integers and recursive structures.

›Count using permutations, combinations, and the binomial theorem; prove combinatorial identities.

›Model and analyse real-world problems using graph theory: isomorphism, special graphs, routing, and paths.

›Automate mathematical reasoning with Python tools (SymPy, Z3, NetworkX) inside Jupyter notebooks.

›Typeset mathematical proofs and documents using LaTeX.

Sequence 1 Foundations of Logic — Part 1 Weeks 1 – 2 ▶

Unit 1.1 Propositions and Logical Connectives — truth values, negation, conjunction, disjunction, implication, biconditional.

Unit 1.2 Equivalence of Propositions — logical laws, De Morgan's laws, simplification, CNF and DNF.

Construct and evaluate truth tables for compound propositions.
Identify tautologies, contradictions, and contingencies.
Simplify logical expressions using equivalence laws step by step.

Sequence 2 Foundations of Logic — Part 2 Weeks 3 – 4 ▶

Unit 2.1 Predicate Logic and Quantifiers — predicates, $\forall$, $\exists$, scope, negation of quantified statements.

Unit 2.2 Rules of Inference in Propositional Logic — modus ponens, modus tollens, hypothetical syllogism, resolution.

Translate natural-language statements into predicate logic formulas.
Negate quantified expressions correctly.
Apply rules of inference to derive conclusions from premises.

Sequence 3 Discrete Structures Weeks 5 – 7 ▶

Unit 3.1 Foundations of Set Theory — sets, subsets, power sets, Cartesian products, Venn diagrams.

Unit 3.2 Set Operations — union, intersection, complement, difference, symmetric difference.

Unit 3.3 Relations and Functions — binary relations, equivalence relations, partial orders, injections, surjections, bijections.

Unit 3.4 Sequences and Series — arithmetic and geometric sequences, summation formulas, telescoping sums.

Prove set identities using element arguments and algebraic laws.
Classify relations by their properties (reflexive, symmetric, transitive).
Determine whether a function is injective, surjective, or bijective.

Sequence 4 Proofs and Recursions Weeks 8 – 10 ▶

Unit 4.1 Fundamental Proof Techniques — direct proof, proof by contrapositive, proof by contradiction, exhaustive proof.

Unit 4.2 Mathematical Induction — weak induction, strong induction, well-ordering principle.

Unit 4.3 Recursive Definitions — recursively defined functions, structural recursion, recurrence relations.

Understand and apply fundamental proof techniques.
Master mathematical induction and strong induction.
Develop skills in recursive thinking and recursive definitions.
Connect proofs, recursion, and induction in mathematical problem solving.

Sequence 5 Counting Weeks 11 – 12 ▶

Unit 5.1 Counting Principles — sum rule, product rule, inclusion-exclusion, permutations, combinations.

Unit 5.2 Binomial Identities — binomial theorem, Pascal's triangle, Pascal's identity, Vandermonde's identity.

Apply sum and product rules as the foundation of counting.
Distinguish between ordered selections (permutations) and unordered selections (combinations).
Apply the binomial theorem and Pascal's triangle to expand polynomial expressions.
Prove classical binomial identities using algebraic and combinatorial arguments.

Sequence 6 Graphs — Part 1 Weeks 13 – 14 ▶

Unit 6.1 Introduction to Graphs — vertices, edges, degree, adjacency matrix, adjacency list, directed vs undirected.

Unit 6.2 Special Graphs — trees, bipartite graphs, complete graphs $K_n$, cycles $C_n$, paths $P_n$.

Acquire the fundamental concepts of graph theory, including vertices, edges, and basic properties.
Master the construction and modification of graphs for different contexts.
Classify and analyse special types of graphs.
Apply graph theory to modelling problems in computer science.

Sequence 7 Graphs — Part 2 Weeks 15 – 16 ▶

Unit 7.1 Graph Isomorphism & Canonical Form — invariants, isomorphism checks, isomorphic subgraphs (cliques, stars, cycles).

Unit 7.2 Routing Problems — walk/trail/path, shortest paths, Eulerian circuits (Chinese Postman), Hamiltonian cycles (TSP).

Identify graph isomorphisms using invariants and canonical form.
Find and count isomorphic subgraphs.
Classify routing tasks: shortest path, Eulerian/Chinese Postman, Traveling Salesman.
Differentiate walk, trail, and path, and compute shortest paths in graphs.

⚙️

Methodology

Each sequence follows a consistent four-step pedagogical cycle designed to build understanding progressively — from concept exposure to applied problem solving.

▶️

Watch

Video lectures introduce core concepts with worked examples and visual explanations.

📖

Read

Lecture notes provide formal definitions, proofs, and guided exercises for deeper study.

🧩

Practice

Unit quizzes reinforce understanding with immediate feedback on each topic.

🔬

Lab

Python-based Jupyter labs let students explore and automate mathematical reasoning.

📝

Assign

End-of-sequence assignments evaluate mastery across all units with multi-part problems.

Assessment split: Quizzes provide continuous formative feedback (ungraded or low-stakes). Lab assignments carry weight toward the final grade. Each sequence concludes with a graded assignment. A specialisation-track choice (Data or Cyber) is made after Sequence 7.

Learning Goals

Prerequisites

Schedule

Methodology

Tools & Platforms