COMP523 - Advanced Algorithmic Techniques

Year: 2011-12
Originating department: Computer Science
Faculty: Faculty of Science
Semester: First Semester
Credit level: Masters Level
Credit value: 15
External examiner: Dr Mike Joy
Member of staff with responsibility for the module: Dr D Kowalski
Board of studies: Board of Studies in Computer Science
Mode of delivery: Lectures/Tutorials
Contact hours: 30 lectures, 10 tutorials
Pre-requisites: A first degree in Computer Science or a closely related subject (e.g.information systems or information technology), or have succesfully completed the first three years of an MEng programme in Computer Science.
Co-requisites: none

Module description

Aims

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.

Learning outcomes

At the end of the module students will have:
A critical awareness of current problems and research issues in the field of complexity theory and abstract discrete algorithms.
The ability to read research literature in the field of discrete algorithms.
The ability to look for research resources (mainly research papers); and later identify (discover), as well as formulate, new research problems.
The ability to perform research collaboration, in the academic field of algorithmics, within a group of researchers.
The ability to critically analyse advances within the academic field of algorithmics.

The module addresses learning outcomes 2, 3, 4, 5 and 6 for the MSc in Computer Science programme, and learning outcomes 2, 3, 4, 5 and 6 for the MEng in Computer Science programme.

Teaching and learning strategies

Formal Lectures: Students will be expected to attend two hours of formal lectures in a typical week accompanied by one hour of seminar given by students in groups.

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.

Syllabus

1 Study/recollection of 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]
2 Study of crucial elements of probabilistic theory and number theory. [1 week]
3 Study of non-standard computational models including: parallel, distributed, non-deterministic (probabilistic and quantum), biologically motivated, and appropriate diverse measures of complexity. [2weeks]
4 Study of advanced particular graph algorithms, string algorithms, randomised algorithms, approximation algorithms, on-line algorithms. [5 weeks]

Recommended texts

J. Kleinberg, E. Tardos. Algorithm Design. Addison-Wesley, 2005

Assessment weightings

25% continuous assessment 75% examination