Algorithms (F2008)

I know that many of you are struggling with the last problem. In the short time left, I’d recommend that you do whatever triage you can and submit. If you’re able to sketch out a way of solving the problem without giving a formal proof, you will get partial credit based on how credible the approach is. So don’t make the mistake of giving up.

Another note: You may assume that undirected Hamiltonian path is also NP-Complete.

PDF and LaTeX

You’ll notice that the new clauses I construct have only 2 variables, and are thus not correct instances of planar 3SAT. It’s trivial to fix this problem, but make sure you do so.

Hi all,
sorry for the late posting. Scott’s notes for Wednesday’s lecture can be found here.

Hi all,
Scott Alfeld will be our guest lecturer for Monday’s class (and Wednesday). The material is taken from the textbook, and here are Scott’s notes.

I have apparently caused no end of consternation with the percentiles and scores that have been sent out. I want to make two points:

• in a class size of 40, a move by one changes the percentile by 2.5%. So being in the top 5 in absolute rankings (if there are ties) could mean that you’re quite low in percentile number. Case in point: someone with a 90% absolute score might actually be right in the middle of the class, percentile-wise.
• So DON’T PANIC: I do not grade on a percentile curve. I look at the absolute scores as well, and have no problems with giving large number of As if the class merits it.

so I’d recommend focusing on your absolute scores for now, and working hard on the next two assignments, and the final (which in itself counts for 30%).

PDF, and LaTeX tarball (with pics)

When would you like the final exam to be ? Some rules of the game

• It will be a take home exam
• It will not be longer than 3 days. I found a week to be too much time for the midterm
• Last class is on Wednesday Dec 10. It cannot be before then

n

A PTAS is a scheme to get an arbitrarily good approximation for an NP-complete problem. Given an input parameter , the goal is to find a -approximation that runs in time polynomial in n.

It’s often the case that such algorithms can be generated by designing an expensive dynamic program, and then adapting it. We demonstrate this idea with the KNAPSACK problem.

We covered material from Chapter 11 of KT, and considered two examples: Firstly, we looked at a simple scheduling problem and showed how to get a 2-approximation using a greedy algorithm. Then, we looked at the Travelling Salesman problem. After showing that in its most general form, no approximation ratio is possible unless P = NP, we showed that if we require that edge weights form a metric, then a heuristic attributed to Christofides enables us to get a 1.5 approximatino.