- To provide a sound foundation concerning the design and analysis of advanaced discrete algorithms.
- To provide a critical rational concerning advanced complexity theory and algorithmics.
- To provide an in-depth, systematic and critical understanding of selected significant issues at the forefront of research explorations in the design and analysis of discrete algorithms.
- Core algorithmic primitives including: notation, standard (sequential) models of computation, algorithmic design methods, data structures, formal proofs and methods of analysis on the example of recent (up to date) research problems. [2 weeks]
- Advanced particular graph algorithms, string algorithms, randomised algorithms, approximation algorithms, on-line algorithms. [5 weeks]
- Crucial elements of probabilistic theory. [1 week]
- Non-standard computational models including: parallel, distributed, non-deterministic (incl. probabilistic), biologically motivated, and appropriate diverse measures of complexity. [2 weeks]
J. Kleinberg, E.Tardos: Algorithm Design. Addison-Wesley (latest edition).
At the end of this module students should be able to:
- Describe the following classes of algorithms and design principles associated with them: recursive algorithms, graph (search-based) algorithms, greedy algorithms, algorithms based on dynamic programming, network flow (optimisation) algorithms, approximation algorithms, randomised algorithms, distributed and parallel algorithms.
- Illustrate the above mentioned classes by examples from classical algorithmic areas, current research and applications.
- Identify which of the studied design principles are used in a given algorithm taking account of the similarities and differences between the principles.
- Apply the studied design principles to produce efficient algorithmic solutions to a given problem taking account of the strengths and weaknesses of the applicable principles.
- Outline methods of analysing correctness and asymptotic performance of the studied classes of algorithms, and apply them to analyse correctness and asymptotic performance of a given algorithm.
Formal Lectures: Students will be expected to attend 3 hours of formal lectures in a typical week. Formal lectures will be used to introduce students to the concepts and methods covered by the module.
Tutorials: Students will be expected to attend one hour of tutorials in a typical week.
Private study: In a typical week students will be expected to devote six hours of unsupervised time to private study. The time allowed per week for private study will typically include three hours of time for reflection and consideration of lecture material and background reading, and three hours for completion of practical exercises.
Assessment: Continuous assessment will be used to test to what extent practical skills have been learned. A final examination at the end of the module will assess the academic achievement of students.