MAT101-F26 · Mathematics · Semester 1
Discrete Structures
The mathematics of computer science: logic, proofs, sets, relations, functions, combinatorics and graphs.
- Format
- Self-paced
- Duration
- 12 weeks
- Effort
- 17–18 hours per week
- Status
- Status: open for enrolment
- Programme
- Foundation programme · Semester 1
- Term
- Fall 2026
- Credits
- 7 ECTS
- Study hours
- 210
- Prerequisites
- None
- Module leader
- Dr. Ali Khudiyev
- ali.khudiyev@wosm.academy
- Office hours
- Monday–Friday, 10:00–17:00 (Baku time, UTC+4)
- Language
- English
- Cost
- Free
Module Overview
Discrete Structures is the first of the required mathematics modules in the curriculum. It covers:
- Basic concepts of logic and mathematics (in the first 4–5 weeks)
- Cardinality and combinatorics, graph theory, number theory, group theory, and propositional and first-order logic (afterwards)
The course introduces fundamental concepts and key areas of discrete mathematics that are relevant to students of computer science.
Aims
- Introduce the mathematical language of computer science: logic, sets, relations, functions and proofs.
- Train students to read, write and check rigorous proofs, including proofs by induction.
- Develop the counting, graph-theoretic and algebraic tools used in the design and analysis of algorithms.
- Lay the foundations for the later mathematics modules and for Data Structures and Algorithms and Theory of Computation.
Learning Outcomes
After completing this course, you will be able to:
- LO1.Understand and apply the basic terminology and methods of discrete mathematics, including logic, algebraic structures, and algorithmic reasoning.
- LO2.Solve combinatorial problems using appropriate mathematical approaches.
- LO3.Model and solve problems using graph theory, and quantitatively evaluate the efficiency of algorithms.
Syllabus
| Unit | Topic |
|---|---|
| 1 | Logic: Propositions and Connectives |
| 2 | Logic: Quantifiers and Predicates |
| 3 | Set Theory: Basic Definitions |
| 4 | Set Theory: Venn diagrams, KV maps, Standard Identities |
| 5 | Natural numbers, Peano axioms, Axiom of Induction |
| 6 | Binary Relations |
| 7 | Endorelations, reflexive-transitive closure |
| 8 | Equivalence relations, partial orders |
| 9 | Partial orders: lattices and well-ordering |
| 10 | Functions |
| 11 | Cardinality |
| 12 | Combinatorics I |
| 13 | Combinatorics II: binomial/multinomial theorem, Stirling numbers |
| 14 | Graph Theory |
| 15 | Trees |
| 16 | Eulerian and Hamiltonian cycles |
| 17 | Planarity |
| 18 | Number theory |
| 19 | Groups I |
| 20 | Groups II: Cyclic groups |
| 21 | Groups III: Generated subgroups, Cayley graphs, homomorphisms |
| 22 | Propositional Logic I: Syntax and Semantics |
| 23 | Propositional Logic II: Validity and Semantics |
| 24 | Propositional Logic III: Normal Forms and Equisatisfiable CNF |
| 25 | Propositional Logic IV: SAT, DPLL, clause-set representation |
| 26 | Propositional Logic V: Resolution |
| 27 | First-order Logic |
Teaching and Learning Methods
The module is self-paced. All materials are provided on Moodle: lecture notes and recorded lectures for each unit, tutorial problem sheets with worked solutions, short quizzes, and the briefs for the two projects. Problem sheets are for practice and are not marked. Questions are discussed in the module channel on Discord and in office hours. Independent study includes reading, problem sheets and project work.
| Activity | Hours |
|---|---|
| Lectures | 54 |
| Labs / Tutorials | 36 |
| Independent study | 120 |
| Total | 210 |
Assessment
Your knowledge will be assessed throughout the course with quizzes, two projects and the final exam. The exam evaluates whether you can correctly use the mathematical terms and concepts introduced in the lectures, such as sets, relations, logic, graphs, and other mathematical objects. It also tests whether you can select and apply the right logical, combinatorial, graph-theoretical, or algebraic methods to solve specific problems.
The two projects are:
- Project 1 – Proofs and counting: a short portfolio of written proofs (induction, relations, functions, cardinality) and combinatorial problems, each solved and justified in full.
- Project 2 – Graphs and SAT: implement a few graph algorithms (e.g. spanning trees, Eulerian circuits) and a DPLL SAT solver, test them, and analyse their running time.
| Component | Weight | Due | LOs |
|---|---|---|---|
| Unit quizzes (best 10 of 12) | 20% | Weekly | LO1–LO3 |
| Project 1: Proofs and counting | 20% | Week 7 | LO1, LO2 |
| Project 2: Graphs and SAT | 20% | Week 12 | LO1, LO3 |
| Final exam (3 hours, written) | 40% | End of term | LO1–LO3 |
| Total | 100% |
Reading List
- K. H. Rosen: Discrete Mathematics and Its Applications, McGraw-Hill, 1995.
- R. L. Graham, D. E. Knuth, O. Patashnik: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1994.
- D. Gries, F. B. Schneider: A Logical Approach to Discrete Math, Springer, 1993.
- D. L. Kreher, D. R. Stinson: Combinatorial Algorithms: Generation, Enumeration, and Search, CRC Press, 1999.
- S. Pemmaraju, S. Skiena: Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, 2003.
Materials and Licence
Course materials are published under the Creative Commons Attribution-ShareAlike 4.0 licence unless stated otherwise. See wosm.academy/licence for details.
Policies
- Attendance: Attendance is not mandatory. The module is self-paced, so you can study the materials when it suits you.
- Late submissions: Work submitted after the deadline is penalised.
- Academic integrity: All submitted work must be your own. See the Code of Conduct.
Free. No application needed. New to Moodle? See How to join.