Introductory description

The module introduces fundamental concepts in the area of discrete mathematics

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

Counting: inclusion/exclusion, binomial coefficients and Pascal's triangle, the twelvefold way (combinations, permutations, etc.), fundamental counting sequences (Catalan, Fibonacci, etc.), combinatorial proofs ("Proofs that really count")
Elementary number theory: floors and ceilings, modular arithmetic, GCD and Euclid's algorithm, diophantine equations, Chinese remainder theorem
Partially ordered sets: posets and Hasse diagrams, chains and antichains (Dilworth, Sperner), lattices, linear extensions and topological sorting
Graph theory basics: basics, degree sequences, paths and cycles, trees, bipartite graphs, Euler tours
Asymptotic notation: Big-O, little-o, Big-Omega, little-omega, Theta etc., Master theorem
Recurrence relations: characteristic polynomials, generating functions

Learning outcomes

By the end of the module, students should be able to:

• - Understand the role of formal definitions, formal and informal mathematical proofs, and underlying algorithmic thinking, and be able to apply them in problem solving.
• - Understand the role of discrete mathematics in applications in computer science.
• - Understand fundamental concepts of discrete mathematics.

Indicative reading list

Please see Talis Aspire link for most up-to-date list.

Subject specific skills

Acquiring fundamental knowledge, skills and tools in the area of discrete mathematics, including familiarity with the concepts of mathematical rigour and formal proof.

Transferable skills

Critical thinking and creativity, problem solving skills, endurance and persistence