Skip to main content Skip to navigation

Module Catalogue

CS301-15 Complexity of Algorithms

Department
Computer Science
Level
Undergraduate Level 3
Module leader
Matthias Englert
Credit value
15
Module duration
10 weeks
Assessment
Multiple
Study location
University of Warwick main campus, Coventry

Download as PDF

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, non-deterministic computations, and also of randomized computations, and approximation algorithms. Furthermore, parallel computations and on-line 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 well-defined 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 Eligible for self-certification
In-person Examination 100% No

CS301 exam

  • Answerbook Gold (24 page)
Assessment group R1
Weighting Study time Eligible for self-certification
In-person Examination - Resit 100% No

CS301 resit exam

  • Answerbook Gold (24 page)
Feedback on assessment

N/A

Past exam papers for CS301

Pre-requisites

CS259 and CS260 are recommended to have been studied.

Courses

This module is Core for:

  • Year 3 of UCSA-G4G1 Undergraduate Discrete Mathematics
  • Year 3 of UCSA-G4G3 Undergraduate Discrete Mathematics
  • Year 4 of UCSA-G4G4 Undergraduate Discrete Mathematics (with Intercalated Year)
  • Year 4 of UCSA-G4G2 Undergraduate Discrete Mathematics with Intercalated Year

This module is Optional for:

  • Year 4 of UMAA-G105 Undergraduate Master of Mathematics (with Intercalated Year)
  • Year 4 of USTA-G1G3 Undergraduate Mathematics and Statistics (BSc MMathStat)
  • USTA-G1G4 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 UCSA-G504 MEng Computer Science (with intercalated year)
  • Year 3 of UCSA-G500 Undergraduate Computer Science
  • Year 4 of UCSA-G502 Undergraduate Computer Science (with Intercalated Year)
  • UCSA-G503 Undergraduate Computer Science MEng
    • Year 3 of G500 Computer Science
    • Year 3 of G503 Computer Science MEng
  • Year 3 of USTA-G302 Undergraduate Data Science
  • Year 3 of USTA-G304 Undergraduate Data Science (MSci)
  • Year 4 of USTA-G303 Undergraduate Data Science (with Intercalated Year)
  • Year 3 of UMAA-G100 Undergraduate Mathematics (BSc)
  • Year 3 of UMAA-G103 Undergraduate Mathematics (MMath)
  • Year 4 of UMAA-G101 Undergraduate Mathematics with Intercalated Year

This module is Option list B for:

  • UMAA-G105 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
  • UMAA-G103 Undergraduate Mathematics (MMath)
    • Year 3 of G103 Mathematics (MMath)
    • Year 4 of G103 Mathematics (MMath)
  • Year 4 of UMAA-G107 Undergraduate Mathematics (MMath) with Study Abroad
  • UMAA-G106 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 USTA-GG14 Undergraduate Mathematics and Statistics (BSc)
  • Year 4 of USTA-GG17 Undergraduate Mathematics and Statistics (with Intercalated Year)

This module is Option list D for:

  • Year 3 of USTA-G1G3 Undergraduate Mathematics and Statistics (BSc MMathStat)