MA408 Half Unit

Discrete Mathematics and Graph Theory

**This information is for the 2019/20 session.**

**Teacher responsible**

Prof Jozef Skokan

**Availability**

This course is available on the MSc in Applicable Mathematics and MSc in Operations Research & Analytics. This course is available as an outside option to students on other programmes where regulations permit.

**Pre-requisites**

Students should be taking the course MA407 Algorithms and Computation or have taken an equivalent course to provide a basic knowledge of algorithms, and should have experience with proofs and proof techniques used in pure mathematics.

**Course content**

This course provides an introduction to discrete mathematics, particularly graph theory. Emphasis will be placed on the algorithmic aspects of the area.

Topics to be covered include: Brief Introduction to discrete mathematics and graph theoretic terminology; Ramsey's Theorem; matchings and Hall's Theorem; graph search algorithms; stable marriages and the Gale-Shapley Theorem; network flows and the Ford-Fulkerson Theorem; connectivity and Menger's Theorems; graph colouring and Brooks' Theorem; and other topics that may vary from year to year.

**Teaching**

20 hours of lectures and 15 hours of seminars in the MT. 2 hours of lectures in the ST.

**Formative coursework**

Students will be expected to produce 10 exercises in the MT.

Weekly exercises are set and marked.

**Indicative reading**

Norman L. Biggs, Discrete Mathematics, Oxford University Press;

T H Cormen, C E Leiserson & R Rivest and C Stein, Introduction to Algorithms, Cambridge University Press;

R Diestel, Graph Theory, Springer;

H S Wilf, Algorithms and Complexity, Prentice Hall.

Several of these texts are available online. More information, plus additional notes, will be provided during the course.

**Assessment**

Exam (75%, duration: 2 hours) in the summer exam period.

Coursework (25%) in the MT.

**
Key facts
**

Department: Mathematics

Total students 2018/19: 7

Average class size 2018/19: 8

Controlled access 2018/19: No

Value: Half Unit

**Personal development skills**

- Self-management
- Problem solving
- Application of information skills
- Communication
- Application of numeracy skills
- Specialist skills