*Lecturer: Dr M. Richards*
(`mr@cl.cam.ac.uk`)

*No. of lectures:* 4

**Aims**

This course is a brief introduction to discrete mathematics. It
covers core elements of the subject to make the
*Data Structures and Algorithms*
course accessible to people who have not seen any
significant discrete mathematics before.
In particular, it covers topics which are covered in Part IA
which are useful for the Data Structures and Algorithms course.

**Lectures**

- Common mathematical notation.
- Sets, tuples, functions.
- Relations (e.g. telephone directory) and Graphs (e.g. air routes).
Induction.
- Combinations and permutations.
*O*(*f*) notation, sorting as example.

**Objectives**

At the end of the course students should

- be familiar with the mathematical notation used in several areas of
discrete mathematics
- be able to find
*O*(*f*) notation representations of the growth rates of functions defined by certain recurrence relations - be able to construct mathematical proofs involving induction
- be familiar with set notation and how to reason about sets and
relations over sets

**Recommended books**

For many people the best advice is simply to read the books in the
*Data Structures and Algorithms* course. The
book

Lipschutz, S. (1976). *Discrete Mathematics*. McGraw-Hill

has a good ``solved problems'' approach which may be useful for students
who have not seen discrete mathematics before.

Those who would like to know *much* more about discrete mathematics
can try:

Stanat, D.F. & McAllister, D.F. (1977). *Discrete Mathematics in
Computer Science*. Prentice-Hall.

Mattson, H.F. Jr (1993). *Discrete Mathematics with Applications*.
Wiley.

Skvarcius, R. & Robinson, W.B. (1986). *Discrete Mathematics with
Computer Science Applications*. Benjamin/Cummings.

Graham, R.L., Knuth, D.E. & Patashnik, O. (1989). *Concrete
Mathematics*. Addison-Wesley.