MA408      Half Unit
Discrete Mathematics and Graph Theory

This information is for the 2017/18 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; an introduction to the probabilistic method; spectral graph theory and random walks.

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 main exam period.
Coursework (25%) in the MT.

Key facts

Department: Mathematics

Total students 2016/17: 5

Average class size 2016/17: 5

Controlled access 2016/17: No

Value: Half Unit

Guidelines for interpreting course guide information

Personal development skills

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