Discrete Mathematics:  2024-2025

Overview

In order to be able to formulate what a computer system is supposed to do, or to prove that it does meet its specification, or to reason about its efficiency, one needs the precision of mathematical notation and techniques. For instance, to specify computational problems precisely one needs to abstract the detail and then use mathematical objects such as sets, functions, relations, orders, and sequences. To prove that a proposed solution does work as specified, one needs to apply the principles of mathematical logic, and to use proof techniques such as induction. And to reason about the efficiency of an algorithm, one often needs to count the size of complex mathematical objects. The Discrete Mathematics course aims to provide this mathematical background.

Problem Sheets: There will be 5 problem sheets for the course, covered in college tutorials.  The problem sheets cover material in weeks 1, 2, 3-4, 5-6, and 7 (respectively), so are suitable for discussion on weeks 2, 3, 5, 7, and 8. The problem sheets will be posted during week 0; these will include a small number of starred problems whose solutions will appear on moodle.

Learning outcomes

This is an introductory course on discrete mathematics. Students will learn:

• some fundamental mathematical concepts and terminology;
• how to use and analyse recursive definitions;
• how to count some different types of discrete structures;
• techniques for constructing mathematical proofs, illustrated by discrete mathematics examples.

Synopsis

The overall goal is to introduce fundamental mathematical concepts arising in computer science and study them using various methods, ranging from inductive arguments and counting techniques to number-theoretic and combinatorial approaches. A more detailed overview is given below.

Week 1: Induction-Sets-Functions. Proofs using induction. Basic definitions of sets and functions. Set operations; 1-1, onto, and bijective functions; countable and uncountable sets. 

Week 2: Counting. Rules of sum, subtract, product; permutations, combinations, binomial coefficients; inclusion-exclusion principle. Counting in two ways.

Week 3: Counting.  Sequences, linear recurrences, and examples. Catalan numbers and generating functions; differentiation, integration and convolution.

Week 4: Asymptotic Estimation. Asymptotic order and Big-O notation. Solving recurrences up to asymptotic order. Estimating sums and Stirling's approximation. Asymptotics of binomial coefficients. 

Week 5: Intro to Number Theory. Modular Arithmetic. The greatest common divisor and Euclid's algorithm. Primes. Solving congruences and the Chinese remainder theorem. Fermat's little theorem

Week 6: Intro to Number Theory. Arithmetic functions and multiplicativity; Euler's totient function and Euler's theorem; primality testing.The Pigeonhole Principle, with applications to number theory and elsewhere. 

Week 7: Relations and Graphs.  Basic properties of relations; equivalences and partial orders. Graphical representation of relations. Graphs, basic terminology and examples; connectivity; paths, cycles, trees, and forests.

Week 8: Further topics in Graphs. Bipartite graphs and even/odd cycles; Proper colourings, max degree and Brooks' theorem. Planar graphs; faces, Euler's formula, subdivisions and Kuratowski's theorem.

Syllabus

Sets: union, intersection, difference, power set, algebraic laws. Functions: injectivity/surjectivity, composition, inverse. Relations: equivalence relations, partial orders, and partitions; relational composition, transitive closure. Combinatorial algebra: permutations, combinations, sums of finite sequences, binomial expansion. Functions associated with combinatorial problems: ceiling, floor, factorial, binomial/multinomial coefficients. The inclusion-exclusion principle. Recurrences arising from combinatorial problems. Sequences: linear recurrences with constant coefficients, generating functions, convolution. Asymptotics: Big-O and related notations, Stirling's approximation, estimating binomials and sums.  Number theory: modular arithmetic, gcd and Euclid's algorithm, Bezout's identity, congruences and the Chinese Remainder theorem,  Fermat/Euler theorems, multiplicative arithmetic functions, Euler's totient function. The pigeonhole principle. Graphs: bipartite graphs, q-colourability, Brooks' theorem, planar graphs, subdivisions, Kuratowski's theorem

Reading list

The following books cover all the topics discussed in the course. They cover the basics very well, have many good practice questions, and are also recommended for the more advanced topics. 

• Kenneth H. Rosen. Discrete Mathematics and its Applications (7th Edition). McGraw Hill, 2012.
• Ralph P. Grimaldi, Discrete And Combinatorial Mathematics (Fifth Edition), Addison Wesley, 2003.

The following comprehensive course notes (from a previous edition of the course) are also highly relevant and useful, covering the majority of the material (around 80%).

• Andrew D. Ker, Discrete Mathematics Lecture Notes, 2009.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.