Here is the worksheet from today’s exam review session, along with a sample solution.
Categories

Recent Posts
Archives
Meta
Here is the worksheet from today’s exam review session, along with a sample solution.
Here’s the promised prereading 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.
Enter your password to view comments.
Posted in Assignments
You can find the longest increasing subsequence classroom handout and solution here:
Posted in Handouts
As of the end of classes (Friday, 01 December), regularlyscheduled 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.)
Posted in Uncategorized
Enter your password to view comments.
Posted in Assignments
Here are sample solutions to the three parts of the Steiner Tree Problem worksheets:
Posted in Handouts
Here is the worksheet and sample solution from our NPcompleteness tutorials this week.
And here’s a summary sheet on NPcompleteness.
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.
Posted in Assignments
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 polynomialtime verifiable certificate), and laid out a polynomialtime reduction from 3SAT to SP. Now, we need to prove our reduction correct in order to show SP is NPhard. Together SP being in NP and NPhard shows SP is NPcomplete.
Posted in Handouts