The last class

Andy Novocin

Daily Challenge

Consider the following heuristic for vertex cover. Construct a DFS tree of the graph, and delete all of the leaves from this tree. What remains must be a vertex cover of the graph. Prove that the size of this cover is at most twice as large as optimal.

Inteview Question (IRL)

What happens when you type in a web browser address bar and press enter?

You have 45 minutes, go as deep as you want with your explanation.

Math Challenge

Factor the following integer






Practice Tests Available

Real tests can be returned

Save the whales

Go online and do your course evaluations!

Coding Theory Factoid

The previous math challenge still holds

But it is also impossible, the paper was called

Optimal binary one-error-correcting codes of length 10 have 72 codewords

A still available challenge is codes of length 16 each of which are at least 5 apart from the others

The range of possible values is 256-340


My winter and spring courses will be available at

(Statistics II, Discrete Math, Coding Theory and Cryptography, Advanced Web Technologies)

I will keep this course's materials online at the permanent address

Office hours next week

What times are best?

Plan to be around daily from 10-6

We can make a planned day (Wednesday maybe) if wanted.

PA4 Doodle

Now online at

Sorry for the delay.

ICUP reduction

Reduce 3-SAT to 0-1 Integer Programming

That is this: given \(A\) an \(n \times m\) matrix and \(b\) an \(n \times 1\) vector, find a 0-1 vector (\(m \times 1\)), \(x\) such that \(Ax \geq b\).

In other words, select which columns of \(A\) add to \(b\) if possible.

Hint: (1 minus the number of complements)


Much like heuristics but provably close to the answer.

Simple Example

Vertex Cover Approximation

cover = []  
While E not empty:
  pick (u,v) from E
  delete from E all edges incident to u or v.

How to justify it

The edges which get picked form a matching (share no edges between their incident vertices)

So each of those edges requires at least 1 vertex in ANY cover.

We kept both so we are no more than twice the number of vertices in THE OPTIMAL cover.


Devise a graph in which our approximation is always sub-optimal.

Vertex Cover to Independent Set to Clique

Take the rest of the vertices from the smallest vertex cover, is it the largest independent set?

Take the complement graph (only the edges which are not in your graph), is the largest independent set of one the largest clique of the other?


Does an approximation for Vertex Cover yield an approximation to Clique?

Proof that poly-time approximation is (sometimes) NOT possible

Knapsack problem: fit maximal valued subset of items into bag with capacity C.

Suppose that you had a polynomial time algorithm which approximates the answer to within a constant range N.

That is, it finds a subset which is valued more than the optimal value - N.

Then just have it approximate a solution where all values are multiplied by N+1

Real life approximations

It is NP-Hard to approximate the shortest vector in a lattice to within a polynomial factor

Sometimes this is enough

If you can make a solution to a derived problem from an approximation

OR if you can prove that no other answer exists that is within the approximation zone (often hard)

Practice Problems

Practice test problems or 9-7 through 9-16 or 9-25 through 9-30