CS301 Complexity of Algorithms
CS30115 Complexity of Algorithms
Introductory description
CS301 Complexity of Algorithms
Module aims
To learn the notions of the complexity of algorithms and the complexity of computational problems. To learn various models of computation. To understand what makes some computational problems harder than others. To understand how to deal with hard/intractable problems.
Outline syllabus
This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.
In this module, the notions of complexity of algorithms and of computational problems will be
studied. Students will learn how to design efficient algorithms for reducing computational
problems to one another, what makes an algorithm efficient, and what makes a problem hard (so that it has no fast algorithm).
Various models of computation will be discussed, in particular, the models of classical deterministic computations, nondeterministic computations, and also of randomized computations, and approximation algorithms. Furthermore, parallel computations and online computations might be presented.
Some part of the module will be devoted to the discussion of what makes some computational problems harder than others, how to classify welldefined computational problems into levels of hardness, and how to deal with problems that are hard and intractable.
Learning outcomes
By the end of the module, students should be able to:
 Know and understand a variety of complexity classes.
 Understand techniques for formally proving that a computational problem is solvable or not solvable.
 Understand techniques for formally proving something about the kind and amount of computational resources (e.g. processing time, memory requirements) that are required to solve a problem.
 Formulate more tractable variations of some computationally hard problems.
Subject specific skills
N/A
Transferable skills
Critical thinking
Study time
Type  Required 

Lectures  30 sessions of 1 hour (20%) 
Seminars  9 sessions of 1 hour (6%) 
Private study  111 hours (74%) 
Total  150 hours 
Private study description
Revising lecture material and background reading.
Solving exercises.
Revision for the exam.
Costs
No further costs have been identified for this module.
You must pass all assessment components to pass the module.
Students can register for this module without taking any assessment.
Assessment group B2
Weighting  Study time  

Inperson Examination  100%  
CS301 exam

Assessment group R1
Weighting  Study time  

Inperson Examination  Resit  100%  
CS301 resit exam ~Platforms  AEP

Feedback on assessment
N/A
Prerequisites
CS259 and CS260 are recommended to have been studied.
Courses
This module is Core for:
 Year 3 of UCSAG4G1 Undergraduate Discrete Mathematics
 Year 3 of UCSAG4G3 Undergraduate Discrete Mathematics
 Year 4 of UCSAG4G4 Undergraduate Discrete Mathematics (with Intercalated Year)
 Year 4 of UCSAG4G2 Undergraduate Discrete Mathematics with Intercalated Year
This module is Optional for:
 Year 4 of UMAAG105 Undergraduate Master of Mathematics (with Intercalated Year)

USTAG1G3 Undergraduate Mathematics and Statistics (BSc MMathStat)
 Year 3 of G1G3 Mathematics and Statistics (BSc MMathStat)
 Year 4 of G1G3 Mathematics and Statistics (BSc MMathStat)

USTAG1G4 Undergraduate Mathematics and Statistics (BSc MMathStat) (with Intercalated Year)
 Year 4 of G1G4 Mathematics and Statistics (BSc MMathStat) (with Intercalated Year)
 Year 5 of G1G4 Mathematics and Statistics (BSc MMathStat) (with Intercalated Year)
This module is Option list A for:
 Year 4 of UCSAG504 MEng Computer Science (with intercalated year)

UCSAG500 Undergraduate Computer Science
 Year 3 of G500 Computer Science
 Year 3 of G500 Computer Science
 Year 4 of UCSAG502 Undergraduate Computer Science (with Intercalated Year)

UCSAG503 Undergraduate Computer Science MEng
 Year 3 of G503 Computer Science MEng
 Year 3 of G503 Computer Science MEng
 Year 3 of USTAG302 Undergraduate Data Science
 Year 3 of USTAG304 Undergraduate Data Science (MSci)
 Year 4 of USTAG303 Undergraduate Data Science (with Intercalated Year)

UMAAG100 Undergraduate Mathematics (BSc)
 Year 3 of G100 Mathematics
 Year 3 of G100 Mathematics
 Year 4 of UMAAG101 Undergraduate Mathematics with Intercalated Year
This module is Option list B for:

UMAAG105 Undergraduate Master of Mathematics (with Intercalated Year)
 Year 4 of G105 Mathematics (MMath) with Intercalated Year
 Year 5 of G105 Mathematics (MMath) with Intercalated Year

UMAAG103 Undergraduate Mathematics (MMath)
 Year 3 of G103 Mathematics (MMath)
 Year 3 of G103 Mathematics (MMath)
 Year 4 of G103 Mathematics (MMath)
 Year 4 of G103 Mathematics (MMath)

UMAAG106 Undergraduate Mathematics (MMath) with Study in Europe
 Year 3 of G106 Mathematics (MMath) with Study in Europe
 Year 4 of G106 Mathematics (MMath) with Study in Europe
 Year 3 of USTAGG14 Undergraduate Mathematics and Statistics (BSc)
 Year 4 of USTAGG17 Undergraduate Mathematics and Statistics (with Intercalated Year)