Text only

 University | Catalogues for 2006/07

University of Bath logo - link to University home page

Department of Computer Science, Unit Catalogue 2006/07

CM20028 Computation IV: Algorithms

Credits: 6
Level: Intermediate
Semester: 2
Assessment: CW25EX75
Before taking this unit you must take CM10139
(or equivalent authorised by Director of Studies) Aims: To present a detailed account of some fundamentally important and widely used algorithms. To induce an appreciation of the design and implementation of a selection of algorithms.
Learning Outcomes:
1. To learn the general principles of effective algorithm design and analysis on some famous examples which are used as fundamental subroutines in major computational procedures; 2. To be able to apply these principles in the development of algorithms; 3. To be able to make informed choices between basic subroutines and data structures.
Problem Solving (F, A)
Algorithms and complexity. Main principles of effective algorithms design: recursion, divide-and-conquer, dynamic programming. Sorting and order statistics. Strassen's algorithm for matrix multiplication and solving systems of linear equations. Arithmetic operations over integers and polynomials (including Karatsuba's algorithm), Fast Fourier Transform method. Greedy algorithms. Basic graph algorithms: minimum spanning trees, shortest paths, network flows. Number-theoretic algorithms: integer factorization, primality testing, the RSA public key cryptosystem. Complexity classes P and NP. NP completeness.


University | Catalogues for 2006/07