Course pages 2016–17
Mathematical Methods for Computer Science
Lecturers: Professor J.G. Daugman and Dr R.J. Gibbens
No. of lectures: 16
Suggested hours of supervisions: 4
This course is a prerequisite for Computer Graphics and Image Processing (Part IB) and the following Part II courses: Machine Learning and Bayesian Inference, Bioinformatics, Computer Systems Modelling, Computer Vision, Digital Signal Processing, Information Theory, 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, namely: probability modelling techniques that allow stochastic systems and algorithms to be described and better understood; and Fourier methods and their generalizations that lie at the heart of digital signal processing, analysis, coding, and communication theory. 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
- Probability methods (Dr R.J. Gibbens)
- Probability generating functions. Definitions and
properties. Use in calculating moments of random variables and for
finding the distribution of sums of independent random
variables. [2 lectures]
- Inequalities and limit theorems. Bounds on tail
probabilities, moment generating functions, notions of convergence,
laws of large numbers, the central limit theorem,
statistical applications, Monte Carlo simulation. [3 lectures]
- Stochastic processes. Random walks. Recurrence and transience. The Gambler’s Ruin problem. Discrete-time Markov chains, Chapman-Kolmogorov equations, classifications of states, limiting and stationary behaviour, time-reversible Markov chains. Examples and applications. [5 lectures]
- Probability generating functions. Definitions and
properties. Use in calculating moments of random variables and for
finding the distribution of sums of independent random
variables. [2 lectures]
- 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]
- Fourier representations. Inner product spaces and orthonormal
systems. Periodic functions and Fourier series. Results and
applications. The Fourier transform and its properties. [3 lectures]
Objectives
At the end of the course students should
- understand the use of probability generating functions;
- 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 random
walks and discrete-time Markov chains;
- 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;
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.