MT3170 Discrete mathematics and algebra
MT2116 Abstract mathematics.
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.