(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.
Skills:
Problem Solving (F, A)
Content:
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.
|
