Looking for online learning materials for this unit?
Online course materials for MATH20902

Discrete Mathematics


Unit code: MATH20902
Credit Rating: 10
Unit level: Level 2
Teaching period(s): Semester 2
Offered by School of Mathematics
Available as a free choice unit?: N

Requisites

None

Aims

This module aims to engage students with a circle of algorithmic techniques and concrete problems arising in elementary number theory and graph theory.

Overview

Modern Discrete Mathematics is a broad subject bearing on everything from logic to logistics. Roughly speaking, it is a part of mathematics that touches on those subjects that Calculus and Algebra can't: problems where there is no sensible notion continuity or smoothness and little algebraic structure. The subject, which is typically concerned with finiteor at the most countablesets of objects, abounds with interesting, concrete problems and entertaining examples.

Learning outcomes

Students should develop the ability to think and argue algorithmically, mainly by studying examples and applications in graph theory and combinatorics.

On completion of this unit successful students will be able to:

  • understand proofs by induction thoroughly and be fluent in their construction;
  • read and understand written descriptions of algorithms;
  • develop and apply simple algorithms to solve problems or prove theorems;
  • give the basic definitions of graph theory and a range of standard examples including, for example, complete graphs and bipartite graphs;
  • characterise planar graphs and prove the five-colour theorem.

Assessment methods

  • Other - 20%
  • Written exam - 80%

Assessment Further Information

  • Coursework; Weighting within unit 20%. This will consist of a problem set due on the last Friday before Easter and handed out two weeks earlier.
  • 2 hours end of semester examination; Weighting within unit 80%

Syllabus

Graph Theory & Applications: [22]


The basic definitions about graphs should be familiar from the Mathematical Workshop MATH10001, so after a brief review we will treat the following topics:
 

• Basic notions & notations, trees [5]
• Eulerian tours & Hamiltonian cycles [4]
• The Principle of Inclusion/Exclusion and the Matrix-Tree Theorem [4]
• Shortest paths & applications to scheduling [4]
Planar graphs & map colouring [5]
 

Recommended reading

  • Dieter Jungnickel, Graphs, Networks and Algorithms (Springer, 2005)

This book is available online through SpringerLink, a service to which the University subscribes.

Feedback methods

Feedback tutorials will provide an opportunity for students' work to be discussed and provide feedback on their understanding.  Coursework or in-class tests (where applicable) also provide an opportunity for students to receive feedback.  Students can also get feedback on their understanding directly from the lecturer, for example during the lecturer's office hour.

Study hours

  • Lectures - 22 hours
  • Tutorials - 11 hours
  • Independent study hours - 67 hours

Teaching staff

Mark Muldoon - Unit coordinator

▲ Up to the top