School of Computer Science

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