MATH20902 - 2008/2009

 

Unit specification

Aims

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

Brief description

Modern Discrete Mathematics is 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 finite or at the most countable sets of objects, abounds with interesting, concrete problems and entertaining examples.

Throughout, we will be interested in developing and analysing algorithms: explicit recipes to solve problems and prove theorems.

Intended learning outcomes

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

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

• read and understand written descriptions of algorithms;
• develop and apply simple algorithms to solve problems or prove theorems;
• understand and, for simple examples, bound the complexity of algorithms;
• give the basic definitions of graph theory and a range of standard examples including, for example, complete graphs and bipartite graphs;
• prove the correctness of certain standard graph-theoretic algorithms, including, for example, Dijkstra's algorithm and Hierholzer's algorithm;
• characterise planar graphs and prove the five-colour theorem.

Future topics requiring this course unit

No options in later years require this unit, but the styles of argument developed here are useful in many parts of mathematics.

Syllabus

1. Introduction to Algorithms and Complexity: [5]
   • The Tower of Hanoi, Euclid's algorithm for the greatest common divisor, simple continued fractions, asymptotic bounds for running times.
2. Graph Theory and Applications: [17]
   The basic definitions about graphs should be familiar from the Mathematical Workshop MT10000, so after a brief review we will treat the following topics:
   • Basic notions and notations, trees, [3]
   • Eulerian tours and Hamiltonian cycles, [2]
   • Planar graphs and graph colouring, [5]
   • Shortest paths and applications to scheduling, [4]
   • An introduction to Social Networks and Small Worlds, [1]
   • The graph Laplacian with applications to graph partitioning and community detection. [2]

Recommended Reading

• Ronald L. Graham, Donald E. Knuth & Oren Patashnik, Concrete Mathematics (Addison-Wesley, 1994 & 1989).
• Aleksandr Ya. Khinchin, Continued Fractions (Dover, 1997).
• David M. Bressoud, Factorization and Primality Testing (Springer, 1997) .
• Dieter Jungnickel, Graphs, Networks and Algorithms (Springer, 2005),
  This book is available online through SpringerLink, a service to which the University subscribes.
• Alan Gibbons, Algorithmic Graph Theory (Cambridge University Press, 1985) .

to the top

Learning and teaching processes

Two lectures and one examples class each week. In addition students should expect to do at least four hours of private study each week on this course unit.

Assessment

Coursework; Weighting within unit 20%

2 hours end of semester examination; Weighting within unit 80%

to the top

Arrangements