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 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!
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.
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.
Today we’ll start talking about NP-completeness with special guest host and TA Raunak Kumar! Thanks, Raunak!
- Here are our notes on NP-completeness.
- Don’t forget that there’s an assignment due Thursday!
- Please read Section 8.2 and skim Section 8.10 for this coming Monday. Keep skimming 8.10 as we read each section. It will help to keep the problems straight in your head! (Note that we won’t discuss every type of problem categorized in 8.10, however.)
- No reading quiz for Monday. (It’s a long weekend; have fun, remember those who have served the country, but do think for at least a while about algorithms!)