Futility of Laying Pipe, Part 2

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

Readings to finish for the week of Nov 20-26

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.)

Protected: Assignment #4 Sample Solution

This content is password protected. To view it please enter your password below:

NP-Completeness and the Futility of Laying Pipe

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.

Readings to finish for the week of Nov 13-19

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.)

Understanding Reductions in a New Light

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

LCS Live Coding Sample Solutions

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

Protected: 2016W2 final exam sample solutions

This content is password protected. To view it please enter your password below:

Readings to finish for the week of Nov 5-12

The reading for this week is section 6.4 in the textbook.

DP in 2-D (Longest Common Subsequence) Sample Solution

Here is a sample solution to our Longest Common Subsequence worksheet.