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