Skip to main content Skip to navigation

CS418 Advanced Topics in Algorithms and Complexity

CS418-15 Advanced Topics in Algorithms and Complexity

Academic year
21/22
Department
Computer Science
Level
Undergraduate Level 4
Module leader
Igor Oliveira
Credit value
15
Module duration
10 weeks
Assessment
Multiple
Study location
University of Warwick main campus, Coventry
Introductory description

The module aims to introduce students to modern techniques, methods, and results from the rapidly developing field of algorithms and complexity. The main topic may change year to year.

Module aims

Students will learn the algorithmic, mathematical, and probabilistic foundations underpinning modern design and analysis algorithms.

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.

  • This is an advanced module covering a range of topics in algorithms and complexity, as well as some of the most recent developments in the field.

Typical topics include a mixture of:

  • Foundations of learning algorithms and their limitations.
  • Probabilistic techniques, probabilistic algorithms and the power of randomness in computation.
  • Algebraic methods in algorithm design.
  • Concrete computational models, such as decision trees, CNF's, and Boolean circuits, and their connections to learning algorithms, satisfiability algorithms, and complexity theory.
  • Parallel algorithms and the limits of parallel computation.
Learning outcomes

By the end of the module, students should be able to:

  • Understand a range of algorithmic topics and associated complexity-theoretic results.
  • Understand a broad range of analytical, algebraic, and probabilistic tools underlying the modern design and analysis of algorithms.
  • Use modern algorithmic techniques to solve natural computational problems.
  • Understand state-of-the-art research in some areas of algorithms and complexity, including new developments and open problems.
Indicative reading list

"An Introduction to Computational Learning Theory". Umesh Vazirani and Michael Kearns.
"Mathematics + Computation". Avi Wigderson.
"Analysis of Boolean Functions". Ryan O'Donnell.
"Computational Complexity". Sanjeev Arora and Boaz Barak.
"Probability and Computing". Michael Mitzenmacher and Eli Upfal.

Subject specific skills
  • Students will learn basic properties and applications of a range of concrete computational models, including decision trees, small-depth circuits, threshold circuits (discrete analogues of neural networks), Boolean formulas, and general Boolean circuits.

  • This advanced module will provide a gentle introduction to fundamental questions connected to the power and limits of algorithms (e.g. randomness in computation, efficient learning algorithms, exhaustive search) from the vantage point of the aforementioned computational models.

  • Students will be introduced to a variety of mathematical techniques that can be used to establish limits on the computational power of some of these models (complexity lower bounds) and to design new algorithms (complexity upper bounds). It will cover probabilistic, algebraic, combinatorial, and analytic techniques, which will be introduced in a self-contained way through a sequence of accessible examples.

Transferable skills
  • The computational models covered in this module have far-reaching applications in computer science, appearing in areas such as machine learning, optimisation, algorithms, cryptography and theoretical computer science.

  • The algorithmic and mathematical techniques introduced in this module are widely applicable and transcend the topics covered in this module (e.g. algebraic methods have significant applications in communication protocols, analytic techniques are employed in machine learning, and probabilistic and combinatorial techniques are ubiquitous in algorithms and optimisation).

  • This module will highlight fruitful interactions between computer science and mathematics, introducing new problem-solving skills and stimulating creative ideas in the design and analysis of algorithms.

Study time

Type Required
Lectures 20 sessions of 1 hour (13%)
Seminars 9 sessions of 1 hour (6%)
Private study 121 hours (81%)
Total 150 hours
Private study description

Private study will consist of:

  • Researching topics
  • Reading background material
  • Completing homework assignments
  • Revising for exam

Costs

No further costs have been identified for this module.

You do not need to pass all assessment components to pass the module.

Students can register for this module without taking any assessment.

Assessment group D2
Weighting Study time
Problem Set 1 10%

Homework assignment 1

Problem Set 2 10%

Homework assignment 2

Problem Set 3 10%

Homework assignment 3

On-campus Examination 70%

CS418 examination

~Platforms - AEP


  • Answerbook Gold (24 page)
Assessment group R1
Weighting Study time
On-campus Examination - Resit 100%

CS418 resit examination.

~Platforms - AEP


  • Online examination: No Answerbook required
Feedback on assessment

Individual written feedback and group feedback in seminars

Past exam papers for CS418

Pre-requisites

This module is only suitable for students familiar with the material from CS260 (Algorithms) and CS301 (Complexity of Algorithms).

Courses

This module is Optional for:

  • Year 5 of UCSA-G504 MEng Computer Science (with intercalated year)
  • Year 4 of UCSA-G503 Undergraduate Computer Science MEng

This module is Option list A for:

  • Year 4 of UCSA-G4G3 Undergraduate Discrete Mathematics

Further Information

Term 1

15 CATS (7.5 ECTS)

Online Material

Additional Information