# Discrete Mathematics

Credits

20

Module code

MA21003

This module provides an introduction for Level 2 students to various topics in Discrete Mathematics. This module is mandatory for Level 2 students taking the BSc or MMath in Mathematics or the BSc or MSci in Mathematical Biology. This module is optional for students taking the BSc in Mathematics combined with any of Accountancy, Economics, Financial Economics or Psychology. If you have questions about this module please contact our Undergraduate Admissions Tutor or your Advisor of Studies.

### Prerequisites

Students taking this module must have achieved a pass mark in each of the modules MA11001 and MA12001, or in EG11003 and EG12003, or equivalents.

### Indicative Content

• #### Sets and Graphs

Sets and subsets: definitions, examples, Set operations, basic identities, power of a set, Cartesian product of sets, relations on sets, Basic graph terminology.

• #### Recurrence relations (Difference Equations)

Definition of a recurrence relation (difference equations), Homogeneous and inhomogeneous difference equations, Nonlinear difference equations: xn+1 = g(xn), Fixed points, linearisation, stability of fixed points. Applications: the Newton and Secant Methods to solve non-linear equations f(x) = 0, Programming: Short introduction to Matlab, Numerical algorithms for difference equations: Newton′s method, Fibonacci sequences, Recursion.

• #### Markov Chains

Definition of Markov chains, probability vectors, and stochastic matrices, Connection between a Markov chain and a second order difference equation, Long time behaviour of a process described by a Markov chain, Random walk as a Markov chain, Absorbing and irreducible Markov chains.

• #### Combinatorics

Permutations and combinations, Binomial coefficients and their properties, Binomial theorem, Principle of inclusion and exclusion. Derangements, Partitions and Stirling numbers, Transpositions and Cycles, Multinomial Theorem, Newton′s Binomial Theorem.

• #### Game Theory

Strategic form games, Dominated Strategies, Nash Equilibrium, Prisoner′s Dilema, Two-person zero-sum games, The minimax Theorem, Extensive form games with perfect information.

### Delivery and Assessment

The module is delivered in the form of lectures and workshops/tutorials and assessed via an exam (60%) and coursework (40%) consisting of homeworks and tests.

### Credit Rating

This module is a Scottish Higher Education Level 2 or SCQF level 8 module and is rated as 20 SCOTCAT credits or 10 ECTS credits.