**Next:**Programming in C and

**Up:**Lent Term 2008: Part

**Previous:**Foundations of Functional Programming

**Contents**

##

Mathematical Methods for Computer Science

*Lecturer: Dr R.J. Gibbens*

*No. of lectures: 16*

*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 and glimpse ahead at applications taken up 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 applications. The Fast Fourier Transform algorithm. [2 lectures]**Wavelets.**Introduction to wavelets with computer science applications. [1 lecture]**Review of elementary probability theory.**Random variables. Discrete and continuous distributions. Means and variances, independence, conditional probabilities. Bayes's theorem. [1 lecture]**Probability generating functions.**Definitions and properties. Use in calculating moments of random variables and for finding the distribution of sums of independent random variables. [1 lecture]**Elementary stochastic processes.**Random walks. Recurrence and transience. The Gambler's ruin problem. Solution using difference equations. [2 lectures]**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

- grasp key properties and uses of Fourier analysis, transforms, and wavelets
- understand discrete transform techniques
- understand elementary probability theory
- 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**

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

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

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

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

**Next:**Programming in C and

**Up:**Lent Term 2008: Part

**Previous:**Foundations of Functional Programming

**Contents**