Month: March 2017

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

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!

Today we’ll continue to talk about NP-completeness and reductions.

• Please read section 8.4 for next class (but the next pre-class quiz will be due before the following class).
• Here is a sample solution to our “What’s In a Reduction” handout.
• We may get a chance to start part 1 of our handout on laying pipe.
• Don’t forget the assignment due Friday!

Today we’ll continue to talk about NP-completeness and reductions.

• For next class, please read section 8.3 and complete the pre-class quiz on 8.2 and 8.3.
• Here’s a sample solution to our current notes on reductions and NP-completeness.
• Here is code implementing memoized and DP versions of Longest Common Subsequence. Here’s a Jupyter Notebook version and plain Python version. (I use the CPSC 103 test library, but it should be pretty easy to remove that dependency!)
• Start in on the assignment, due next week and posted at the end of the day Friday!