Category Archives: Handouts

You can find the longest increasing subsequence classroom handout and solution here:

Handout

Solution

Here are sample solutions to the three parts of the Steiner Tree Problem worksheets:

1. part 1 on understanding the problem and showing it is in NP
2. part 2 on developing a reduction showing the problem is NP-hard
3. part 3 on proving the reduction correct

We’ve now analysed the original Steiner Tree Problem, turned it into a decision problem (SP), shown that SP is in NP (by finding a polynomial-time verifiable certificate), and laid out a polynomial-time reduction from 3-SAT to SP. Now, we need to prove our reduction correct in order to show SP is NP-hard. Together SP being in NP and NP-hard shows SP is NP-complete.

Here is a sample solution to the notes on using reduction for NP-completeness proofs.

Here’s the second in a series of worksheets on NP-completeness in association with a problem in laying pipe that UBC solved a couple years back: Pipe, part 2

Here’s the first in a series of worksheets on NP-completeness in association with a problem in laying pipe that UBC solved a couple years back.

We’re going back to reductions again! Here is a worksheet on a new way to think about and use reductions.

For sample solutions to the live-coding of LCS in various formats, check out:

• Jupyter Notebook
• Python
• HTML
• PDF