Solutions to Lab 9 exercises & Reflection

Written solutions

The written solutions for this week can be download as PDF below.

Download Solutions to Lab 9

Video explanations of some solutions

Here is a video for question 2.

Please let me know if you want clarification on any other exercises.

Reflection

There are hundreds, if not thousands, of practical problems that are NP-hard. If one day you need to solve a practical instance of one of them... what do you do? Do you just tell the boss that this is not known to have an efficient solution? Or do you add that we can possibly approximate the solution or try some other clever ideas?

Hint

You should of course try a practical solution and not just tell the boss that the problem is too hard... (otherwise you might just loose your job!)

There are many resources for practical methods for tackling NP-hard problems (and super-efficient algorithms for easier problems). I recommend you start by exploring The Algorithm Design Manual by Steven Skiena.

Visit the "The Algorithm Design Manual" companion website

I particularly encourage you to browse through the Algorithm Repository section.

You can access a digital copy of the book through our library:

Access the book through Locate (Lanchester Library)