Course material 2010–11

##

Mathematical Methods for Computer Science

*Lecturer: Dr R.J. Gibbens*

*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 aim of this course is to introduce and develop mathematical
methods that are key to many modern applications in Computer Science.
The course proceeds on two fronts: (*i*) Fourier methods and
their generalizations that lie at the heart of modern digital signal
processing, coding and information theory and (*ii*) 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 blend a mix of theory with
examples that glimpse ahead at applications developed in Part II
courses.

**Lectures**

**Fourier methods.**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 and related algorithms and applications. [2 lectures]**Wavelets.**Introduction to wavelets with computer science applications. [1 lecture]**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 and their 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.