|Level||SHE Level 2|
|Prerequisites||Some knowledge of discrete mathematics would be advantageous|
|Contact||Lectures: 11 | Labs/Tutorials: 20|
|Assessment||The class is assessed 100% by coursework and an oral examination.|
|Resit||The resit is assessed 100% by coursework and an oral examination.|
|Lecturer||Dr Sergey Kitaev|
Aims and Objectives
The aim of this class is to introduce the combinatorics of discrete objects that are ubiquitous in theoretical computer science, namely graphs and relations. For both these objects, the overarching aim is to develop the students’ skills in mathematical thinking and reasoning, and to be able to present that reasoning in rigorous written text.
On completion of the class, a student should be able:
- Demonstrate an awareness of essential structures for computers.
- Solve a variety of problems in graph theory.
- Solve problems in order theory, and have an understanding of the different types of relations that can exist in discrete structures.
- Present solutions clearly and rigorously in both text and orally.
Elementary graph theory:
Basic graph definitions and concepts – walks, paths, cycles, degree; types of graphs – trees, directed graphs, tournaments; graph isomorphism; the n-dimensional hypercube and binary sequences of length n; Hamiltonian paths and cycles of a graph; the spanning tree of a graph; Kruskal’s algorithm; planar graphs and Euler’s theorem; de Bruijn graphs and their application.
Elements of order theory:
Cartesian products of sets; Relations; Binary relations; The number of binary relations; Identities involving Cartesian product and set-intersection and set-union; Functions – definition, domain, co-domain, and range. Properties of relations – reflexivity, transitivity, symmetry, and anti-symmetry; Equivalence relations; Partially ordered sets; Hasse diagrams of partially ordered sets; The directed graph of a relation; Equivalence classes of equivalence relations.
Assessment and Exemption
Students will typically be set two assignments. There is an individual oral examination based on the work set in the two assignments.
The resit for the class will take the form of individual assignments as well as an individual oral examination.
* This list is indicative only – the class lecturer may recommend alternative reading material. Please do not purchase any of the reading material listed below until you have confirmed with the class lecturer that it will be used for this class.