The 2016W1 (Sep-Dec 2016) CPSC 320 site has been archived to: https://blogs.ubc.ca/cpsc3202016w1/.
The 2016W2 (Jan-Apr 2017) site is at https://blogs.ubc.ca/cpsc3202016w2/.
Here’s a sample solution for our Bloom Filter notes. It’s put together quickly; so, let me know if you see problems!
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! 🙂
Today we’ll finish discussing NP-completeness.
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.
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!