Here is a sample solution to our first NP-completeness worksheet about SAT and 3-SAT.
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.
Protected: Assignment #4 Sample Solution
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!
Readings for 2018/03/24
Before Sunday’s pre-class quiz: Read sections 6.6 and 8.1 in your textbook. Note that as you read Chapter 8, you will want to visit and revisit 8.10 to get a high-level sense of how NP-complete problems fit into the set of problems you’re learning!
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).