# Module 06-35308 (2020)

## Algorithms and Complexity

## Level 3/H

Anupam Das Paul Levy Rajesh Chitnis | Semester 2 | 20 credits |

Co-ordinator: Rajesh Chitnis

Reviewer: Anupam Das

The Module Description is a strict subset of this Syllabus Page.

### Outline

Algorithms are at the heart of computer science. In this module we will develop a range of core algorithmic ideas such as dynamic programming, greedy methods, divide-and-conquer techniques, and network flows. We will then learn how to use these to design efficient algorithms for a range of problems, motivated by a range of applications. We will then consider core concepts from computational complexity theory such as NP-completeness, and their implications for algorithm design. Finally, we will consider some advanced modern topics such as approximate and randomized algorithms, parameterized algorithms and complexity, and algorithms for streams of data.

### Learning Outcomes

On successful completion of this module, the student should be able to:

- Understand, explain, and apply core techniques for constructing algorithms
- Design novel algorithms to solve specific problems
- Understand and apply core concepts from computational complexity theory
- Appreciate and explain modern topics in algorithmic theory

### Pre-requisites

- 06-30175 - Data Structures & Algorithms
- 06-35393 - Theories of Computation
- 06-35324 - Mathematical and Logical Foundations of Computer Science

### Cannot be taken with

- 06-35326 - Algorithms and Complexity (Extended)

### Assessment

- Main Assessments: 1.5 hour examination (50%) and continuous assessment (50%)
- Supplementary Assessments: 1.5 hour examination (50%) and continuous assessment (50%) over the Summer Period

### Programmes containing this module

- BSc Artificial Intelligence & Computer Science [0144]
- BSc Artificial Intelligence & Computer Science with an Industrial Year [9502]
- BSc Artificial Intelligence & Computer Science with Study Abroad [452B]
- BSc Computer Science [4436]
- BSc Computer Science with an Industrial Year [9499]
- BSc Computer Science with Digital Technology Partnership (PwC) [610C]
- BSc Computer Science with Digital Technology Partnership (Vodafone) [893C]
- BSc Computer Science with Study Abroad [5571]
- BSc Mathematics and Computer Science [5196]
- BSc Mathematics and Computer Science with an Industrial Year [9495]
- MEng Computer Science/Software Engineering [4754]
- MEng Computer Science/Software Engineering with an Industrial Year [9501]
- MSci Computer Science [4443]
- MSci Computer Science with an Industrial Year [9509]
- MSci Computer Science with Study Abroad [5576]
- MSci Mathematics and Computer Science [5197]
- MSci Mathematics and Computer Science with an Industrial Year [9496]