# Computer Laboratory

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.

• © 2011 Computer Laboratory, University of Cambridge
Information provided by Prof John Daugman