Here is a sample solution to the third of the three SP worksheets.
Sample Solution to Steiner Tree Problem Worksheet Part 2
Protected: Assignment #5 Sample Solution
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:
Readings for 2018/04/01
Before Sunday’s pre-class quiz: Read section 8.3; theorems 8.12, 8.14 and the subsection called “General Strategy for Proving New Problems NP-Complete” from section 8.4; one of sections 8.5, 8.7, and 8.8; and again read through 8.10 to tie these together.
Assignment #5
Here is the full assignment version of Assignment #5 (and latex source with a txt file extension).
The assignment is due Thursday 5 April (later than usual!). (However, if you submit A#5 and your last submission is no later than Tuesday 3 April at 10PM, we’ll give you one course bonus point and one extra point on the assignment.)
MEANWHILE here are the collected quizzes and the collected quizzes with sample solutions.
Sample solution to Longest Common Subsequence worksheet
Here is a sample solution to our LCS worksheet.