Module MATH1031: DISCRETE MATHEMATICS

Department: Mathematical Sciences

MATH1031: DISCRETE MATHEMATICS

Prerequisites

• Normally, A level Mathematics at grade C or better, or equivalent.

Corequisites

• None.

Excluded Combination of Modules

• Foundation Mathematics (MATH1641) may not be taken with or after this module.

Aims

• To provide students with a range of tools for counting discrete mathematical objects.
• To provide experience of a range of techniques and algorithms in the context of Graph Theory, many with every day applications.

Content

• Principles of Counting: mathematical induction, permutations and combinations, combinatorial vs arithmetical proof.
• Pigeonhole principle, inclusion and exclusion.
• Prime numbers: density of prime numbers, modular arithmetic, public key encryption.
• Generating Functions: partitions, recurrence relations.
• Special Numbers: Fibonacci, Fermat, Mersenne, Stirling etc.
• Algorithms and Finite State Machines: elementary discussion of algorithmic complexity.
• Graphs: basic concepts, Euler paths, maze algorithms, random walks on graphs, Euler's theorem, planar graphs, brief introduction to colouring graphs, the Six and Five Colour Theorems.
• Optimisation Algorithms on Graphs: trees (relevant to searching data structures, genetics, decision problems), shortest and longest paths, flow problems, matching/assignment problems, latin squares, travelling salesman and Chinese postman problems.

Learning Outcomes

• By the end of the module students will: be able to solve a range of predictable and less predictable problems in Discrete Mathematics.
• have an awareness of the basic concepts of theoretical mathematics in the field of Discrete Mathematics.
• have a broad knowledge and basic understanding of these subjects demonstrated through one or more of the following topic areas: Principles of counting.
• Recurrence relations and generating functions.
• Algorithms and finite state machines.
• Graphs.
• Algorithms on graphs.

• students will have basic mathematical skills in the following areas: Spatial awareness, Abstract reasoning, Modelling.

• students will have basic problem solving skills.

Modes of Teaching, Learning and Assessment and how these contribute to the learning outcomes of the module

• Lectures demonstrate what is required to be learned and the application of the theory to practical examples.
• Tutorials provide the practice and support in applying the methods to relevant situations as well as active engagement and feedback to the learning process.
• Summative weekly coursework provides an incentive for students to consolidate the learning of material as the module progresses (there are no higher level modules in the department of Mathematical Sciences which build on this module). It serves as a guide in the correct development of students' knowledge and skills, as well as an aid in developing their awareness of standards required.
• The end-of-year written examination provides a substantial complementary assessment of the achievement of the student.

Teaching Methods and Learning Hours

Summative Assessment

Formative Assessment:

45 minute collection paper in the first week of Epiphany term.

■ Attendance at all activities marked with this symbol will be monitored. Students who fail to attend these activities, or to complete the summative or formative assessment specified above, will be subject to the procedures defined in the University's General Regulation V, and may be required to leave the University