Here’s a sample solution to the first part of our pipe-laying notes.
Lecture 2016/11/18
Today, we’ll lay some pipe… or not. We may just decide it’s too hard to lay pipe.
- Here again are the new notes for today on part 1 of the futility of laying pipe.
- For Monday, please read section 8.5.
- Complete the pre-class quiz on sections 8.4 and 8.5.
- Assignment #5 is due Thursday. Make progress! It’s a substantial assignment.
Lecture 2011/11/16
Today we’ll finish our first brush with NP-completeness.. and do some more!
- Here are the new notes for today on part 1 of the futility of laying pipe.
- For Friday, please read section 8.4, but there is no pre-class quiz.
- Don’t forget to get started on Assignment #5, due next Thursday.
Assignment #5, Wed Noon Edition
Here’s the full assignment, with LaTeX source (extension .txt for posting), and the figure with the boxes.
The assignment is due Thursday 24 Nov at 10PM. For more details, see the assignment itself. Have fun!
Assignment #5, Tue 1PM Edition
Here’s the assignment version of the Tue 1PM quiz.
Lecture 2016/11/14
Today we continue to talk about reductions and NP-completeness.
- Please read section 8.3 by Wednesday and complete the pre-class quiz on 8.2 and 8.3 due at noon on Wed.
- Here’s a sample solution to our current notes on reductions and NP-completeness.
- Don’t forget this week’s quiz, and start in on the assignment.
Assignment #5, Mon 3PM Edition
Here’s the assignment version of the Mon 3PM quiz.
Assignment #5, Mon 9AM Edition
Here’s the assignment version of the Mon 9AM quiz.
Protected: Sample Solution to Assignment #4
Implementations of LCS
This should be considered “just for fun” handouts, as long as you are confident you are capable of implementing something like LCS in whatever your favorite language is, given sufficient time.
With that caveat, here’s a PDF of our LCS implementation, with some extra embellishments toward the end, including patching the code we didn’t quite finish.