COMP526

Applied Algorithmics

Aims

The main aim of this module is to lay down a strong context for research explorations in the field of algorithms. This is done through a rigorous study of selected algorithmic solutions with application to related fields requiring analysis of large data (bioinformatics, networking, data compression, etc). This will be done by provision of the rationale for the use of algorithmic design and analysis methods, and also an in-depth, systematic and critical study of several important algorithmic challenges residing on the border of the theory of abstract algorithms and engineering of applied algorithmic solutions.

Syllabus

Study of standard computational (including parallel) models, algorithmic methods, solutions and methods of analysis used in theory of algorithms and experimental algorithmics. This includes critical study of exemplar algorithmic problems including sorting, pattern matching, and others.

[3 weeks]

 

Study of time, space and communication efficient algorithms and data structures for large centralised and distributed environments. This includes studies on respective solutions for peer-to-peer systems, crowdsourcing, data compression, security and others.

[2 weeks]

 

Study of novel computational models motivated by new challenges in streaming of large data, memory caching, external memory computations, dynamic networks, and others.

[2 weeks]

 

Study of more advanced applied algorithms used in networks (e.g., communication, random walks, significance, clustering), property/groups testing, error correction, visualisation and others.

[3weeks]

Recommended Texts

​Introduction to Algorithms

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

MIT Press 2009

​Algorithm Design

Jon Kleinberg, Eva Tardos

Addison Wesley, 2006

Learning Outcomes

Critical awareness of algorithmic problems and as well as research issues in the context of engineering of efficient algorithmic solutions.

Clear understanding of the relation (including differences) between the goals in the design of efficient abstract and applied algorithmic solutions.

Ability to understand and assimilate research literature relating to the application of algorithmic techniques.

​Ability to undertake small software projects.

Ability to communicate (within and outside of Algorithms/CS community) problems related to efficiency of algorithmic solutions

Learning Strategy

Formal lectures including problem solving

Tutorials mainly based on programming assignements

Formal Lectures: Students will be expected to attend two hours of formal lectures in a typical week accompanied by one hour of problem solving or seminar sessions.

Tutorials: Students will be expected to attend one hour of tutorials in a typical week. The tutorials are mainly focused on programming exercises.

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 (mainly programming) exercises.