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/.
2016W1
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
Sorry for the late post! Here they are:
No assignment version this time! The remainder of your grade will come from the final exam or your highest other assignment grade.
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!