OCOM5102M (L02) Algorithms

Algorithms and algorithmic problem solving are at the heart of computer science. This module introduces students to the design and analysis of efficient algorithms and data structures. Students learn how to quantify the efficiency of an algorithm and what algorithmic solutions are efficient. Techniques for designing efficient algorithms are taught, including efficient data structures, standard methods such as Divide-and-Conquer and Dynamic Programming as well as more advanced techniques for computationally intractable problems and large data sets. This is done using illustrative and fundamental problems relevant to AI.

Course Description

Syllabus

Indicative content for this module includes:

- Algorithmic thinking (the stable matching problem)

- Basic tools: probability, matrices, graphs and networks, mathematical reasoning

- Time and space complexity, asymptotic analysis of algorithms

- Algorithms: interval scheduling, median finding, quickselect;

- Algorithm design principles: Greedy algorithms, divide and conquer,

dynamic programming; fundamental data structures;

- Intractability: the classes P and NP

- Dealing with NP-hard problems in practice

- Markov chains: computing the page rank

- Approximation algorithms

- Modern algorithms: streaming and testing, parameterised algorithms

 

Learning outcomes
On completion of this module students should be able to:

1. Demonstrate an understanding of what constitutes an efficient and an inefficient solution to a computational problem

2. Analyse the efficiency of algorithms

3. Evaluate and justify appropriate ways to provide efficient solutions for computational problems

4. Identify and apply design principles such as greediness, divide and conquer and dynamic programming in the design of efficient algorithms

5. Describe efficient algorithms for a range of computational problems, along with their computational complexity

6. Articulate the key concepts and critically evaluate approaches in a clear and rigorous manner