Computer Science and Mathematics (3 Years) [BSc]
|Unit level:||Level 2|
|Teaching period(s):||Semester 2|
|Offered by||School of Mathematics|
|Available as a free choice unit?:||N
This module aims to engage students with a circle of algorithmic techniques and concrete problems arising in elementary number theory and graph theory.
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.
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.
- 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%
Graph Theory & Applications: 
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 
• Eulerian tours & Hamiltonian cycles 
• The Principle of Inclusion/Exclusion and the Matrix-Tree Theorem 
• Shortest paths & applications to scheduling 
Planar graphs & map colouring 
- Dieter Jungnickel, Graphs, Networks and Algorithms (Springer, 2005)
This book is available online through SpringerLink, a service to which the University subscribes.
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.
- Lectures - 22 hours
- Tutorials - 11 hours
- Independent study hours - 67 hours