Handouts and Notes 2017/04/03

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.

Handouts and Notes 2017/03/31

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.)

Handouts and Readings 2017/03/27

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.)

Handouts and Readings 2017/03/24

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.

Handouts and Readings 2017/03/22

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!

Handouts and Notes for 2017/03/17

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

Handouts and Notes for 2017/03/15

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.

Spam prevention powered by Akismet