MATH20902 - 2010/2011

 

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

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:

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

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 & Induction: [5]
         Euclid's algorithm for the greatest common divisor, simple continued fractions, asymptotic bounds for running times.
2. Graph Theory & Applications: [17]
         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 [3]
   • Eulerian tours & Hamiltonian cycles [3]
   • Planar graphs & graph colouring [5]
   • Shortest paths & applications to scheduling [4]
   • The graph Laplacian with applications to graph partitioning [2]

Textbooks

• Aleksandr Ya. Khinchin, Continued Fractions (Dover, 1997)
• Dieter Jungnickel, Graphs, Networks and Algorithms (Springer, 2005)
  This book is available online through SpringerLink, a service to which the University subscribes.

Learning and teaching processes

Two lectures and one examples class each week. In addition students are expected to work for about four hours each week for this course unit.

Assessment

Coursework; Weighting within unit 20%

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

to the top

Arrangements

The coursework will consist of a problem set handed out in Week 6 and due at the end of Week 7.