Prerequisite/Recommended prerequisite for participation in the module

Content, progress and pedagogy of the module

Learning objectives

Knowledge

• Must understand set theory: sets, relations, functions, partial orderings, equivalence relations
• Must understand fundamental number theory: modular arithmetic, Euclidean algorithm, the Chinese remainder theorem, Fermat’s little theorem and prime factorisation
• Countability of the rational numbers
• Must understand recursive/iterative algorithms
• Must understand time complexity: asymptotic notation and Big-O notation
• Must know about logarithm and exponential functions with base 2
• Must know about combinatorics and the binomial formula
• Must know about recursive functions and recurrence relations
• Must know about proof techniques: weak and strong induction and proof by contradiction, contraposition and constructive
• Must understand logic: propositional logics and quantifiers
• Must understand graph theory: directed and undirected graphs, path, simple path and trees
• Graph algorithms: search in graphs and shortest path

Skills

• Must be able to construct proofs (using the proof techniques of the course) for results within the course
• Must be able for formulate in writing mathematical results related to the course

Competences

• Must have competencies in the use of concepts and techniques of discrete mathematics, including in connection with algorithms

Type of instruction

The teaching in Discrete Mathematics is a combination of sessions with lectures, exercises, and mini-projects.

Exam

Exams