CS215 – Combinatorics for Computer Science 2

TIMETABLE TEACHING MATERIAL
Credits 10
Level SHE Level 2
Prerequisites Some knowledge of discrete mathematics would be advantageous
Availability Semester 1
Elective Yes
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.

Learning Outcomes

On completion of the class, a student should be able:

  1. Demonstrate an awareness of essential structures for computers.
  2. Solve a variety of problems in graph theory.
  3. Solve problems in order theory, and have an understanding of the different types of relations that can exist in discrete structures.
  4. Present solutions clearly and rigorously in both text and orally.

Syllabus

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.

Resit

The resit for the class will take the form of individual assignments as well as an individual oral examination.

Indicative Reading*

* 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.

Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer by Tom Jenkyns and Ben Stephenson (Springer, 2012).

Graph Theory, Combinatorics and Algorithms: Interdisciplinarity by Martin Charles Golumbic and Irith Ben-Arroyo Hartman  (Springer, 2011)