## 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 `http://www.google.com`

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

#### 188198812920607963838697239461650439807

#### 163563379417382700763356422988859715234

#### 665485319060606504743045317388011303396

#### 716199692321205734031879550656996221305

#### 168759307650257059

## 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

## Advertisement

### My winter and spring courses will be available at prof.ninja

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

### I will keep this course's materials online at the permanent address http://cisc320f14.prof.ninja

## 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

### 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)

## Approximations

### Much like heuristics but provably close to the answer.

## Simple Example

### Vertex Cover Approximation

```
cover = []
While E not empty:
pick (u,v) from E
cover.push(u,v)
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.

## ICUP

### 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?

## ICUP

### 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