These courses are offered as modules of the honours programme for students in the fourth year:

Computational Complexity

Dr Holger Spakowski

This course provides an introduction to major topics in computational complexity theory, which is one of the core areas of Theoretical Computer Science. In computational complexity, we investigate the power of efficient computation. That is, we try to distinguish between computational problems that can be solved efficiently in practice and those that, though theoretically solvable, are not solvable in practice because of prohibitively large time or space requirements. Topics covered include: Nondeterministic and deterministic Turing machines; basic time and space complexity classes; space and time hierarchies. NP and NP-completeness. The polynomial hierarchy. Oracle complexity classes; relativization of the P versus NP problem. Space-bounded computation. Randomized computation. Circuits. Counting problems. Interactive proofs.

Cryptography

Dr Christine Swart

Cryptography is the mathematics of scrambling data to keep it secret. The course will be an overview of modern cryptology, including: block ciphers (and attacks), hash functions (and attacks), stream ciphers (and attacks), public key encryption and digital signatures (and attacks) and secret sharing (and attacks). We assume some basic familiarity with groups and fields, but will cover all the number theory you need. Depending on time it might be possible to cover a special topic, like electronic voting or identity-based encryption.

Graph Theory

Dr David Erwin

Graph Theory is an increasingly important area of modern mathematics. There are numerous applications of Graph Theory: Modelling the World Wide Web, the spread of disease, driving directions, and electrical networks, to name a few. This course, though, is delivered as a course of Pure Mathematics, i.e., it is a sequence of theorems and proofs.

Topics Covered:

  • Introduction: Graphs and digraphs, degree, isomorphism, operations on graphs, distance, bipartite graphs, cut-vertices and bridges, trees.
  • Connectivity, vertex and edge cuts, Menger’s Theorem.
  • Planar graphs, Kuratowski’s Theorem, the Four and Five Colour Theorems.
  • Vertex colouring, Brooks’ Theorem.
  • Eulerian and Hamiltonian graphs.
  • Graphs and groups, permutation groups and the Cauchy-Frobenius-Burnside Theorem.