Here’s a sample solution for our Bloom Filter notes. It’s put together quickly; so, let me know if you see problems!
Last Lecture Day!
We’ll have a party and also maybe talk about some random problems I brainstormed. I don’t have answers for these, but they seem fun 🙂
Today we’ll talk about Bloom Filters. Finally! 🙂
- Here are today’s notes on Bloom Filters.
- If you’d like to read about them, the Wikipedia entry is a good place to start.
- There is one more (fun!) pre-class quiz. Please be sure to submit it by Wednesday at 4:05PM (different time from usual). I need prep time!
- Remember that there is a quiz this week in tutorial.
Today we’ll finish discussing NP-completeness.
- Here is a sample solution to part 3 of the NP-completeness handout.
- For Monday, please read Section 8.10 one more time now that we’ve made our way through most of the rest of Chapter 8. There will be no pre-class quiz for Monday.
Today we’ll continue with the Steiner Tree Problem. We’ve just about got a reduction; so, it’s time to prove our reduction is correct.
- Here are today’s new notes on the proof (part 3 of the series).
- Here’s a solution to the second part of our SP notes.
- For next time, please read Section 8.8. (It’s got a lovely little discussion of dynamic programming as well!) There will be no reading quiz.
- Assignment due tomorrow!
Today we’ll make a reduction to prove the Steiner Tree Problem is NP-hard (and therefore NP-complete, since it’s in NP). We won’t prove the reduction correct quite yet, however.
Note: this is a doozy of a reduction. So, it’s good practice for us, but much harder than, e.g., the SAT/ELEC problem on the assignment!
- Here is the new handout on NP-hardness of SP.
- For Wednesday, please read section 8.7 of the textbook (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!
- No quiz for Wednesday.
- Keep trucking on the assignment due Thursday!
Part 1 of Pipe-Laying, Sample Solution
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.
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.