Here is a sample solution to the third of the three SP worksheets.
Sample Solution to Steiner Tree Problem Worksheet Part 2
Sample Solution to Steiner Tree Problem Worksheet Part 1
Sample Solution to SAT/3-SAT Worksheet
Pipe-laying and NP-completeness worksheets
Here are the three parts to our last set of worksheets on pipe-laying and NP-completeness:
Sample solution to Longest Common Subsequence worksheet
Here is a sample solution to our LCS worksheet.
Boolean Satisfiability and NP-completeness
Here is our first worksheet on NP-completeness, focusing on Boolean satisfiability.
Be sure you’re keeping up with the reading! There’s a lot to NP-completeness that we won’t get a chance to discuss in class!
Making Change worksheet sample solutions
Here are sample solutions to the two parts of our making change worksheet:
DP in 2-D worksheet
Attached is our worksheet on a dynamic programming problem where our recurrence has more than one parameter (that’s critical to the recurrence).