# Module 06-35326 (2020)

## Algorithms and Complexity (Extended)

## Level 4/M

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

Co-ordinator: Rajesh Chitnis

Reviewer: Rajesh Chitnis

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
- Demonstrate an awareness of the current literature in this area

### Pre-requisites

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

### Cannot be taken with

- 06-35308 - Algorithms and Complexity

### 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

- MEng Computer Science/Software Engineering [4754]
- MEng Computer Science/Software Engineering with an Industrial Year [9501]
- MSc Advanced Computer Science [0014]
- MSc Artificial Intelligence and Machine Learning [475D]
- MSc Cyber Security [504B]
- MSc Robotics [9889]
- 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]