Exam PreReading

Here’s the promised pre-reading for your exam. Two of the problem domains will be familiar to you, but the third is a template designed to illustrate a new type of exercise we’ll most likely be asking on the exam. Feel free to discuss the solution to the sample question we posed!

Here’s a sample solution to the problem given there (corrected 2017/12/08 to have the right work per node/level). BUT, try to solve it yourself first! The sample solution is really there mainly to make sure you understand how we intend to format the answer.

NOTE that we will expect you to be very familiar with the domains already given in our assignments (including assignment #6) are actively developing exciting new questions that explore those domains in different ways from what you’ve already seen.

Protected: Assignment #6 Sample Solution

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

Notes: Longest Increasing Subsequence Handout and Solution

You can find the longest increasing subsequence classroom handout and solution here:



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

NP-completeness tutorial worksheet and notes

Here is the worksheet and sample solution from our NP-completeness tutorials this week.

And here’s a summary sheet on NP-completeness.

Assignment #6 (for practice only)

Here is Assignment #6, along with LaTeX source (as a .txt). The assignment is ungraded and not for submission, and is intended to provide you with additional practice for the final exam.

Solutions will be released on Thursday, December 7.

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.