Discrete Mathematics (2024)

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 (note for college tutors: these will be different from previous years).

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, 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 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, harmonic number and integration. 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. Graphs: bipartite graphs, q-colourability, Brooks' theorem, planar graphs, subdividisions, Kuratowski's theorem

Reading list

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

Comprehensive, book-style, notes which cover the majority of the material (around 80%).

Supplementary notes for topics that are not fully covered therein will be provided on a lecture-by-lecture basis.

Primary Text

• K. A. Ross and C. R. B. Wright, Discrete Mathematics (Fifth Edition), Prentice Hall, 2003

This book has much to commend it, including an enormous number of examples and exercises and a computer science oriented exposition. It is pitched at a somewhat easy level, suitable for supplementing the lecture notes. It is rather expensive (about £50) but there are many copies in Oxford libraries.

Alternative Texts

• A. Chetwynd and P. Diggle, Discrete Mathematics, Arnold, 1995.

Very basic, but easy to read. Only covers the first half of the course. Cheap.

• R. P. Grimaldi, Discrete And Combinatorial Mathematics (Fifth Edition), Addison Wesley, 2003.

Some of the book is rather advanced, but also covers the basics quite well. Has many good practice questions (some difficult). Earlier editions are equally useful.

Taking our courses

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

Other matriculated University of Oxford students who are interested in taking this,or other, courses in the Department of Computer Science, must completethis online formby 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 departmentalcommittee and can only be submitted using this form.