MT3170 Discrete mathematics and algebra
Prerequisites (applies to degree students only)
MT2116 Abstract mathematics.
Syllabus
This full unit develops the mathematical methods of discrete mathematics and algebra and will
emphasise their applications.
- Counting: selections, inclusion-exclusion, partitions and permutations, Stirling numbers, generating functions, recurrence relations.
- Graph Theory: basic concepts (graph, adjacency matrix, etc.), walks and cycles, trees and forests, colourings.
- Set Systems: matching, finite geometries, block designs.
- Abstract groups: revision of key concepts such as cyclic groups, subgroups, homomorphisms and Lagrange's theorem. Conjugation and normal subgroups. Group actions.
- Applications of algebra to discrete mathematics I: permutations, orbits and stabilisers, the orbit-stabiliser theorem; applications to counting problems.
- Rings and polynomials: the Euclidean algorithm for polynomials, integral domains, ideals, factor rings, fields, field extensions.
- Finite fields: construction, the primitive element theorem, and finite linear algebra.
- Applications of algebra to discrete mathematics II: finite Geometry: designs, affine and projective planes.
- Error-correcting codes: linear codes, cyclic codes, perfect codes.
