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.
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.
Here’s the assignment version of the Tue 1PM quiz.
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.
Here’s the assignment version of the Mon 3PM quiz.
Here’s the assignment version of the Mon 9AM quiz.
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.