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
Categories
-
Recent Posts
Archives
Meta
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
Posted in Handouts
The reading this week is 8.2, 8.3, 8.4, plus an initial quick skim of 8.10 (which will be worth skimming after each section or two that you read) in the Kleinberg and Tardos textbook. (There are two quiz questions on 8.10. Hopefully, you’ll find they’re entirely doable with a skim of 8.10.)
Posted in Readings
Enter your password to view comments.
Posted in Assignments
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.
Posted in Handouts
The reading this week is 6.5, 6.6, 6.8 and 8.1 in the Kleinberg and Tardos textbook.
(We’re finishing up Dynamic Programming and diving into NP-completeness in the readings. The readings are a bit behind class at this point. So, you may want to do 8.1 first to get in sync with class and then jump back to Chapter 6 to strengthen your understanding of dynamic programming.)
Posted in Readings
We’re going back to reductions again! Here is a worksheet on a new way to think about and use reductions.
Posted in Handouts
For sample solutions to the live-coding of LCS in various formats, check out:
Posted in Handouts
The reading for this week is section 6.4 in the textbook.
Posted in Readings
Here is a sample solution to our Longest Common Subsequence worksheet.
Posted in Handouts