# 2021/2022

## Prerequisite/Recommended prerequisite for participation in the module

The module builds on knowledge obtained in Linear Algebra.

## 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

 Name of exam Discrete Mathematics Type of exam Written or oral exam ECTS 5 Assessment 7-point grading scale Type of grading Internal examination Criteria of assessment The criteria of assessment are stated in the Examination Policies and Procedures