Computer LaboratoryComputer Science Syllabus - Mathematical Methods for Computer Science

Mathematical Methods for Computer Science
Next: Numerical Analysis I Up: Michaelmas Term 2005: Part Previous: Logic and Proof   Contents

## 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) probability modelling techniques that allow stochastic systems and algorithms to be described and better understood and (ii) Fourier methods and their generalizations which lie at the heart of modern digital signal processing, coding and information theory. 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

• 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]

• 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]

Objectives

At the end of the course students should

• 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

• grasp key properties and uses of Fourier analysis, transforms, and wavelets

• understand discrete transform techniques

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: Numerical Analysis I Up: Michaelmas Term 2005: Part Previous: Logic and Proof   Contents
Christine Northeast
Sun Sep 11 15:46:50 BST 2005

 © 2005 University of Cambridge Computer Laboratory Please send any comments to pagemaster@cl.cam.ac.uk Page last updated on 11-Sep-2005 at 15:57 by Christine Northeast