Course pages 2011–12

# Mathematical Methods for Computer Science

**Principal lecturers:** Prof John Daugman, Dr Richard Gibbens**Taken by:** Part IB**Past exam questions:** Mathematical Methods for Computer Science, Continuous Mathematics**Information for supervisors** (contact lecturer for access permission)

No. of lectures: 12

Prerequisite course: Probability

This course is a prerequisite for Computer Graphics and Image Processing (Part IB) and the following Part II courses: Artificial Intelligence II, Bioinformatics, Computer Systems Modelling, Computer Vision, Digital Signal Processing, Information Theory and Coding, Quantum Computing.

## Aims

The aims of this course are to introduce and develop mathematical
methods that are key to many applications in Computer Science.
The course proceeds on two fronts: (*A*) Fourier methods and
their generalizations that lie at the heart of digital signal processing,
analysis, coding, and communication theory; and (*B*) probability
modelling techniques that allow stochastic systems and algorithms to
be described and better understood. The style of the course is
necessarily concise but will attempt to mix a blend of theory with
examples that glimpse ahead at applications developed in Part II
courses.

## Lectures

- Part A: Fourier and related methods (Professor J. Daugman)
**Fourier representations.**Inner product spaces and orthonormal systems. Periodic functions and Fourier series. Results and applications. The Fourier transform and its properties. [3 lectures]**Discrete Fourier methods.**The Discrete Fourier transform, efficient algorithms implementing it, and applications. [2 lectures]**Wavelets.**Introduction to wavelets, with applications in signal processing, coding, communications, and computing. [1 lecture]

- Part B: Probability methods (Dr R.J. Gibbens)
**Inequalities and limit theorems.**Bounds on tail probabilities, moment generating functions, notions of convergence, weak and strong laws of large numbers, the central limit theorem, statistical applications, Monte Carlo simulation. [3 lectures]**Markov chains.**Discrete-time Markov chains, Chapman-Kolmogorov equations, classifications of states, limiting and stationary behaviour, time-reversible Markov chains. Examples and applications. [3 lectures]

## Objectives

At the end of the course students should

- understand the fundamental properties of inner product spaces and orthonormal systems;
- grasp key properties and uses of Fourier series and transforms, and wavelets;
- understand discrete transform techniques, algorithms, and applications;
- understand basic probabilistic inequalities and limit results and be able to apply them to commonly arising models;
- be familiar with the fundamental properties and uses of discrete-time Markov chains.

## Reference books

* Pinkus, A. & Zafrany, S. (1997). *Fourier series and integral transforms*. Cambridge University Press.

* Ross, S.M. (2002). *Probability models for computer science*. Harcourt/Academic Press.

Mitzenmacher, M. & Upfal, E. (2005). *Probability and computing: randomized algorithms and probabilistic analysis*. Cambridge University Press.

Oppenheim, A.V. & Willsky, A.S. (1997). *Signals and systems*. Prentice Hall.