# Monday Quizzes

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.

# Lecture 2016/11/28

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.

# Lecture 2016/11/23

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.

# Lecture 2016/11/21

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!

# Lecture 2016/11/18

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.