Basic Information

Objectives The course aims to build on the mathematical foundations laid in the introductory course on discrete mathematics. In particular, Graph theory, basics of Abstract Algebra and elementary concepts in Number Theory that are relevant to Computer Science will be introduced in the course. The students will also receive further training in writing rigorous proofs with a special focus on constructive proofs, which are at the heart of Algorithms.

Course Contents

Basics of Graph Theory (8 Weeks) Basic definitions & isomorphism, walks, trails, paths, cycles, forests & trees, connected vs disconnected graphs, subgraphs, spanning subgraphs & spanning trees, bipartite graphs vs odd cycles (with proof), vertex colourings, Eulerian tours vs Hamiltonian cycles, characterisation of Eulerian graphs (with proof), vertex-connectivity & edge-connectivity, Menger’s Theorem (with proof), Matchings and Hall's Theorem. Planar graphs, Euler formula. Digraphs, DAGs, Tournaments - basics and properties
Algebraic Structures (4 weeks) Semigroups, Monoid and Groups, Rings, and Fields. Vector spaces, bases.
Basic Number Theory (2 Weeks) Divisibility, GCD, Bezout’s Lemma, Properties of primes. Modular arithmetic, Congruences, Chinese remainder theorem. Fermat's little theorem.