This course is unavailable through clearing

This course is now full for our 2022 entry, but have a look at our clearing vacancies to see if a similar course has space.

Search all clearing vacancies

# BSc Computer Science and Mathematics / Course details

Year of entry: 2022

## Course unit details:Discrete Mathematics

Unit code MATH20902 10 Level 2 Semester 2 Department of Mathematics No

### 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.

### Pre/co-requisites

Unit title Unit code Requirement type Description
Foundations of Pure Mathematics A MATH10101 Pre-Requisite Compulsory
Foundations of Pure Mathematics B MATH10111 Pre-Requisite Compulsory

### Aims

This module aims to engage students with a circle of concrete problems and applications, algorithmic techniques and basic theorems arising in graph theory.

### Learning outcomes

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

• Define what it means for two graphs to be isomorphic and determine, with rigorous supporting arguments, whether two (small) graphs are isomorphic.
• Explain what the chromatic number of a graph is, determine it for small graphs and apply the idea to scheduling problems.
• Say what it means for a graph to be Eulerian and determine whether small graphs or multigraphs are Eulerian.
• Say what it means for a graph to be Hamiltonian and use the Bondy-Chvátal theorem to prove that a graph is Hamiltonian.
• Construct the graph Laplacian and apply the Matrix-Tree Theorem to count the number of spanning trees or spanning arborescences contained in a graph.
• Construct the adjacency matrix of a graph and exploit the connection between powers of the adjacency matrix to count walks. Also, define the operations of tropical arithmetic, construct the weight matrix associated with a weighted graph and use its tropical matrix powers to find the lengths of shortest paths.
• Given a project defined by a set of tasks, along with their durations and prerequisites, use critical path analysis to determine how quickly the project can be completed.
• Say what it means for a graph to be planar; state and apply Kuratowski’s theorem and determine whether a graph is planar or not.

### 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]

### Assessment methods

Method Weight
Other 20%
Written exam 80%
• 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.
• End of semester examination; Weighting within unit 80%

### 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.

Recommended: Dieter Jungnickel (2013), Graphs, Networks and Algorithms, 4th edition, Springer.
Harris, Hurst & Mossinghoff (2008), Combinatorics and Graph Theory, Springer.
Marcus (2008), Graph Theory: a problem oriented approach, Mathematical Association of America.
Biggs (1993), Algebraic Graph Theory, 2nd edition, CUP.
Cameron (2017), Notes on Counting: An Introduction to Enumerative Combinatorics, CUP.

### Study hours

Scheduled activity hours
Lectures 12
Tutorials 12
Independent study hours
Independent study 76

### Teaching staff

Staff member Role
Mark Muldoon Unit coordinator

The independent study hours will normally comprise the following. During each week of the taught part of the semester:

·         You will normally have approximately 60-75 minutes of video content. Normally you would spend approximately 2-2.5 hrs per week studying this content independently

·         You will normally have exercise or problem sheets, on which you might spend approximately 1.5hrs per week

·         There may be other tasks assigned to you on Blackboard, for example short quizzes or short-answer formative exercises

·         In some weeks you may be preparing coursework or revising for mid-semester tests

Together with the timetabled classes, you should be spending approximately 6 hours per week on this course unit.

The remaining independent study time comprises revision for and taking the end-of-semester assessment.