Module description
Syllabus:
Elementary properties of Integers. Functions and their behaviour. Introduction to Recursion. Algorithms and complexity. Graphs including Euler’s Theorem, shortest path algorithm and vertex colouring. Trees - applications include problem solving and spanning trees. Directed Graphs including networks. Codes and Cyphers - with Hamming codes and RSA.
Prerequisites:
There are no formal prerequisites. Pre-knowledge is minimal, though a basic knowledge of matrices will be needed in one topic. Students who have taken 5CCM224A 'Introduction to Number Theory' will recognise a couple of the techniques used in the first 2 weeks of lectures, but we do not assume that students have attended this course.
Assessment details
Written examination and class tests.
Exercises or quizzes will be set each week to be handed in the following week. These problems will be discussed in the tutorials and solutions will be available.
Educational aims & objectives
To give students an understanding of the nature of an algorithmic solution to problems, to illustrate the idea by applications to problems in discrete mathematics and to promote an algorithmic viewpoint in subsequent mathematical work.
Teaching pattern
Three hours of lectures and one hour of tutorial per week throughout the term
Suggested reading list
Indicative reading list - link to Leganto system where you can search with module code for lists