Skip to content

Detour into EXP Problems and Algorithms

Dr Matthew England has kindly recorded this guest lecture especially for 380CT students.

Who is Dr Matthew England?

Matthew is an Associate Professor in Computer Science (Coventry University). You might remember him from the module 4000CEM in your first year! (Python)

As well as teaching in the CEM School, he is a researcher in the Research Centre for Computational Science and Mathematical Modelling.
There he supervises PhD students and leads government funded research projects on the development, analysis and application of sophisticated algorithms. These algorithms all have exponential complexity!

The guest lecture looks into problems that require exponential time, and the current research that tries to overcome the prohibitive cost when dealing with practical problems.

Now I let you watch: Detour into EXP Problems and Algorithms -- thanks Matthew.

The slides are available for download below (PDF format).

Download the Guest Lecture slides

Here are some questions from Matthew to help you reflect about this guest lecture:

  • Which problems are important enough to demand an exact solution, and on which would you be happy to use a heuristic algorithms?
  • If SAT solvers can solve the SAT problem quickly in many cases; which other problems might they be applied to?

  • One of Matthew’s friends has made a QE solver available in a browser: https://matek.hu/zoltan/blog-20211001.php

    Note that the syntax used is space for multiplication.

    Try out the QE examples from Matthew's lecture and any more you can think of!

And here are some questions for you to reflect on after the above:

  • (Short term) Do you view computers and Computer Science in the same way you did before studying this module? (Hint: Your view should be different! But what is different now?)
  • (Medium term) What modules might you take next semester and next year that build on or are related to 380CT?
  • (Long term) Do you think you might do postgraduate study or have a job career in Theoretical Computer Science (TCS) or Algorithms Design and Analysis?