Category: Readings

Here are some problems you can work on for practice if you’d like. (We don’t have sample solutions to these, but we’d be happy to answer Piazza posts about them.)

Bring a #2 pencil, a cup, and a plate to class if you can!

Don’t forget the assignment due Thursday evening.

Second-to-last day of lecture!

Today, we’ll continue with our Bloom Filters notes.

• Here are sample solutions to the Bloom Filters notes.
• There’s no pre-reading for the last day of class. Review your readings in preparation for the exam!
• Don’t forget the assignment due Thursday (different date than usual!). Please carefully read the notes on which problems to choose and how to submit them.
• Please fill out course/instructor evaluations online before 9 April.
• The last day of the (regular) term is Thursday. So, no regular tutorials/lectures/office hours after Thursday. Also, no prepared material for tutorial this week; instead, the Tue/Wed/Thu tutorial times are open office hours. We’ll post exam period office hours on Piazza soon.
• Thanks to your work gathering bonus points, we’ll have an end-of-term party on the last day of class :). We’ll also have some problems you can work on during the party.

Today we’ll finish up our pipe-laying. The Steiner Tree Problem is in NP and NP-hard; so, it’s in NP-complete. Woo-hoo! 🙂

We may also start in on our last worksheet on Bloom Filters.

• If you’d like to read about Bloom Filters, the Wikipedia entry is a good place to start, but we have no pre-class reading required.
• Remember that there is a quiz this week in tutorial. (Next week’s tutorial on Tue/Wed/Thu is open office hours, however; no prepared material.)

We’re closing in on finishing laying pipe. Here is the last (third) part of the handout and its sample solution.

• For next time, please do one last read of 8.10, now that we’ve finished the sections of Chapter 8 we plan to assign.
• Don’t forget this week’s tutorial quiz!

More pipe-laying as we establish that this fiendish problem is NP-complete.

• Here are all three parts of the pipe-laying handout: part 1, part 2, part 3, with sample solutions to part1 and part2.
• For next time, please read section 8.8. There’s an awesome special guest appearance by dynamic programming there.
• Don’t forget our last tutorial quiz this week! (Quiz posting may work a little differently this week than usual, as we’re likely going to shorten the assignment compared to the total of the quizzes.)

We’ll continue on the pipe-laying problem (here are part 1 and part 2) today.

• There’s an optional review session on NP completeness at 4-5:30PM Wed Mar 29 in FSC 1001.
• For next class, read section 8.7 (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!
• Here’s a sample solution to part 1 of our pipe-laying problem.
• Here’s a sample solution to part 2 of our pipe-laying problem.
• Don’t forget the assignment due today (Friday)!
• Next week we’ll have our last in-tutorial quiz, with a focus on NP-completeness.

We’ll start/continue on the pipe-laying problem today.

• For next class, read section 8.5 and finish the pre-class quiz that has been e-mailed to you.
• Here’s a sample solution to part 1 of our pipe-laying problem.
• Just in case we get to it, here is part 2 of the pipe-laying problem. Note that the reduction we work through here is  a doozy! So, it’s good practice for us, but much harder than we’d be likely to ask about on an exam, at least without extensive scaffolding.
• Don’t forget the assignment due Friday!

Today we’ll continue to talk about NP-completeness and reductions.

• Please read section 8.4 for next class (but the next pre-class quiz will be due before the following class).
• Here is a sample solution to our “What’s In a Reduction” handout.
• We may get a chance to start part 1 of our handout on laying pipe.
• Don’t forget the assignment due Friday!

Today we’ll continue to talk about NP-completeness and reductions.

• For next class, please read section 8.3 and complete the pre-class quiz on 8.2 and 8.3.
• Here’s a sample solution to our current notes on reductions and NP-completeness.
• Here is code implementing memoized and DP versions of Longest Common Subsequence. Here’s a Jupyter Notebook version and plain Python version. (I use the CPSC 103 test library, but it should be pretty easy to remove that dependency!)
• Start in on the assignment, due next week and posted at the end of the day Friday!

We’ll do some combination of live-coding of dynamic programming and starting in on our “what’s in a reduction” handout. (A problem by any other name would be as complete??) This is the start to our discussion on NP-completeness.

• For next time, please read Section 8.2 and skim Section 8.10. 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.)
• The reading quiz for next time is on 8.1 (the reading for last time).
• We’ll have a reading quiz due Sunday on 8.2 and 8.3. (So, get an early start on the reading if you’d like!)
• As usual for this week’s quiz, we’ll post the quizzes each day with the full assignment on Friday.