# School of Mathematics and Statistics

Home | About the school | Contact | Courses | Research | Personnel list

2011/2012 Sem. 1

## Aims

In recent years the mathematics of discrete (finite) structures has gained greatly in importance, especially with the development and expansion of computer technology.
This course covers a selection of topics from discrete mathematics.
The emphasis is on methods (algorithms) for manipulating finite mathematical objects (such as graphs, codes, abstract machines, etc.), solving problems using these algorithms, as well as on 'real life' applications of these methods to problems in operational research.
The course also gives a mathematical treatment of computational machines (automata and Turing machines) and safe transfer of information (coding and encryption).

## Objectives

By the end of the course students should be familiar with:

- Basics of graph theory, and different special types of graphs, such as digraphs, bipartite graphs, trees, networks, etc.

- Basic algorithms on graphs such as: connectivity algorithms, greedy algorithms for colouring, matching algorithms, Kruskal's algorithm for spanning trees, etc.

- Linear programming: graphical solution of 2 variable problems.

- Game theory: two person zero-sum games; games with saddlepoints; mixed strategies; the minimax theorem.

- Network problems: Optimal routing (shortest path problems); Dijkstra's algorithm, Floyd's algorithm; generalisations; maximal flow problems; Max-flow Min-cut algorithm.

- Sequencing and scheduling: Lawler's algorithm, Smith's algorithm, Johnson's algorithms, critical path analysis, project networks, determination of critical paths.

- Regular expressions and finite state automata for accepting them.

- Applications of graphs and automata to sorting and searching: tree search, regular expression search.

- Basics of the mathematical theory of computation: Turing machines, complexity of algorithms, computationally intractable problems, problems which cannot be solved by algorithms.

- Transfer of information - coding and encryption: Hamming distance, error detecting and error correcting capabilities of a code, using number theory to construct ciphers.

## Textbooks

N.L. Biggs Discrete Mathematics, Clarendon Press, 1989.

J.A. Anderson Discrete Mathematics with Combinatorics, Prentice Hall, 2001.

L.R. Foulds Graph Theory and Applications, Springer, 1992.

S. French et al. Operational Research Techniques, Edward Arnold, 1986.

H A Taha Operations Research: an Introduction (8th Ed.), Prentice Hall, 2006

D. Welsh Codes and Cryptography, Clarendon Press, 1988.

## Lectures, practicals and tutorials

The average load, in hours per week, is as follows:
Lectures: 5
Practicals: 1
Tutorials: 1
Examples Class: 1
These figures do not include the revision and exam period at the end of each semester.

## Assessment

30% of the assessment mark is from continuous assessment during the semester. The remainder is from a 3 hour exam at the end of the semester.

Re-assessment is entirely by a 3 hour exam in August.

MT1002

## Availability

This module is taught every year in Semester 2 at 11.

## Lecturers

Dr C M Roney-Dougal (Module coordinator), Dr S Huczynska, Dr D L Borchers