Author Archives: Steve

Exam Period Office Hours

As of the end of classes (Friday, 01 December), regularly-scheduled office hours ended; instead, your lovely TAs will be holding help sessions on a different schedule up until the day of the final exam. See below for this schedule. (Note that we may have updates adding or extending hours but, except for emergencies, we don’t expect to reduce or cuthours.)

  • Tue 5 Dec 1PM-3PM in ICCSX151 (Jose)
  • Wed 6 Dec 9:00-11:00AM in ICCSX237 (Setareh)
  • Wed 6 Dec 2PM-4PM in ICCS X153 (Paul)
  • Thu 7 Dec 12PM-2PM in ICCS233 (Cinda)
  • Thu 7 Dec 2PM-4PM in ICCSX141 (Adrian)
  • Fri 8 Dec 11AM-1PM in ICCS233 (Cinda)
  • Fri 8 Dec 1PM-3PM in FSC 1005 (review session w/Susanne, Adrian, Brad, Jose)
  • Fri 8 Dec 3-5PM in ICCS X141 (Farzad)
  • Sun 10 Dec 2PM-4PM in ICCS X139 (Ali)
  • Mon 11 Dec 11AM-2PM in ICCS 238 (Steve, in a larger room than his office)
  • Tue 12 Dec 10AM-12PM in ICCS 202 (Steve, in a larger room than his office)

Protected: Assignment #5 Sample Solution

This content is password protected. To view it please enter your password below:

Sample Solutions to Pipe-Laying/NP-completeness for the Steiner Tree Problem

Here are sample solutions to the three parts of the Steiner Tree Problem worksheets:

  1. part 1 on understanding the problem and showing it is in NP
  2. part 2 on developing a reduction showing the problem is NP-hard
  3. part 3 on proving the reduction correct

Futility of Laying Pipe, Part 3

We’ve now analysed the original Steiner Tree Problem, turned it into a decision problem (SP), shown that SP is in NP (by finding a polynomial-time verifiable certificate), and laid out a polynomial-time reduction from 3-SAT to SP. Now, we need to prove our reduction correct in order to show SP is NP-hard. Together SP being in NP and NP-hard shows SP is NP-complete.

Sample Solution to Understanding Reduction in a New Light

Here is a sample solution to the notes on using reduction for NP-completeness proofs.

Readings to finish for the week of Nov 27-Dec 3

The reading this final week of classes is 8.5, 8.7, 8.8, plus a complete read of 8.10 in the Kleinberg and Tardos textbook.

This is the final set of readings for the term. If you’d like to have the full set of readings collected in one place, be sure to refer to our course material post on Piazza.

Assignment #5

CORRECTIONS:

  • Clarification in 4.2.1. Note that we’re allowing a “set” to be a collection of possibly non-unique items–more like a list. Solve the (harder) problem for sets of unique items for a bonus point!
  • Typo in 4.2.1. Not “a set of positive integers S of size 2n”, but “a set of positive integers S of size 12n“.
  • Error in 1.1.2 (and the quiz problem it comes from): C(i, j) equals A[i][j] plus the minimum of the options, not just the minimum of the options. (Else the answer would always be 0!)
  • Typo on 2 (various parts) the BestDeShredScore code should have a trampoline call to its helper like “return Helper([false, false, …, false], 0)”, where there are n false entries in the initial array
  • Clarification on 4 (various parts) we said “set” and meant it, but we’re allowing “multi-set”; see @521 for more details
  • on 4, individual quiz, problem 1: S[2n-i] should be S[2n-i-1]. (Or S[i] should be S[i+1], depending on 0-based vs. 1-based indexing.)

Here is Assignment #5, composed of the collected tutorial quizzes, solutions to those quizzes, and some extra questions building on the quizzes for the assignment. (Here is LaTeX source, with a .txt extension so the blog lets us post it!)

The assignment is due on Fri 1 Dec at 10PM. Please submit it on GradeScope.

Readings to finish for the week of Nov 20-26

The reading this week is 8.2, 8.3, 8.4, plus an initial quick skim of 8.10 (which will be worth skimming after each section or two that you read) in the Kleinberg and Tardos textbook. (There are two quiz questions on 8.10. Hopefully, you’ll find they’re entirely doable with a skim of 8.10.)

Protected: Assignment #4 Sample Solution

This content is password protected. To view it please enter your password below:

NP-Completeness and the Futility of Laying Pipe

Here’s the first in a series of worksheets on NP-completeness in association with a problem in laying pipe that UBC solved a couple years back.