CPSC 320 – Page 2

Today we’ll finish up our pipe-laying. The Steiner Tree Problem is in NP and NP-hard; so, it’s in NP-complete. Woo-hoo! 🙂

If you’d like to read about Bloom Filters, the Wikipedia entry is a good place to start, but we have no pre-class reading required.
Remember that there is a quiz this week in tutorial. (Next week’s tutorial on Tue/Wed/Thu is open office hours, however; no prepared material.)

We’re closing in on finishing laying pipe. Here is the last (third) part of the handout and its sample solution.

For next time, please do one last read of 8.10, now that we’ve finished the sections of Chapter 8 we plan to assign.
Don’t forget this week’s tutorial quiz!

More pipe-laying as we establish that this fiendish problem is NP-complete.

Here are all three parts of the pipe-laying handout: part 1, part 2, part 3, with sample solutions to part1 and part2.
For next time, please read section 8.8. There’s an awesome special guest appearance by dynamic programming there.
Don’t forget our last tutorial quiz this week! (Quiz posting may work a little differently this week than usual, as we’re likely going to shorten the assignment compared to the total of the quizzes.)

Here are problem domains to help you prepare for Quiz 6. We recommend you spend a few minutes reading through all of them before your tutorial!

We’ll continue on the pipe-laying problem (here are part 1 and part 2) today.

There’s an optional review session on NP completeness at 4-5:30PM Wed Mar 29 in FSC 1001.
For next class, read section 8.7 (about the famous 3-coloring problem in graphs!). This is also a good time to go back and re-skim 8.10. You’ve seen a lot of those problems now!
Here’s a sample solution to part 1 of our pipe-laying problem.
Here’s a sample solution to part 2 of our pipe-laying problem.
Don’t forget the assignment due today (Friday)!
Next week we’ll have our last in-tutorial quiz, with a focus on NP-completeness.

We’ll start/continue on the pipe-laying problem today.

For next class, read section 8.5 and finish the pre-class quiz that has been e-mailed to you.
Here’s a sample solution to part 1 of our pipe-laying problem.
Just in case we get to it, here is part 2 of the pipe-laying problem. Note that the reduction we work through here is a doozy! So, it’s good practice for us, but much harder than we’d be likely to ask about on an exam, at least without extensive scaffolding.
Don’t forget the assignment due Friday!