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 generalisations 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]
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 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.