Not available in 2020/21
MA408 Half Unit
Discrete Mathematics and Graph Theory
This information is for the 2020/21 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 2 exercises in the MT.
Weekly exercises are set and solved in the seminar.
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.
Important information in response to COVID-19
Please note that during 2020/21 academic year some variation to teaching and learning activities may be required to respond to changes in public health advice and/or to account for the situation of students in attendance on campus and those studying online during the early part of the academic year. For assessment, this may involve changes to mode of delivery and/or the format or weighting of assessments. Changes will only be made if required and students will be notified about any changes to teaching or assessment plans at the earliest opportunity.
Key facts
Department: Mathematics
Total students 2019/20: Unavailable
Average class size 2019/20: Unavailable
Controlled access 2019/20: No
Value: Half Unit
Personal development skills
- Self-management
- Problem solving
- Application of information skills
- Communication
- Application of numeracy skills
- Specialist skills
