Week 10

Question 1

How are NP-hard problems dealt with?

Answer 1

Approximation and randomized algorithms
Exact exponential time algorithms (via branching + dynamic programming)
Fixed parameter tractable algorithms

Question 2

What is the recurrence featured in Vertex Cover, and how is it solved?

Answer 2

T(n) <= T(n - 1) + T(n - 3), where n = input size.

Solved by setting T(n) = x^n.

Question 3

What does n! roughly equal?

Answer 3

(n / e)^n

Question 4

PROBLEM: Set Cover

Answer 4

Given sets
U = {u1 , u2 , . . . , uN } of N elements and
S = {S1 , S2 , . . . , SM } of non-empty subsets of U such that |S| = M

Find a collection S’ from S of minimum size such that union of sets in S’ covers all elements of U.

Question 5

What is an FPT algorithm?

Answer 5

A parameterized problem with parameter k and input size n is said to be fixed-parameter tractable (FPT) if it can be solved in f (k) · n^O(1) time, for some function f , where k <= n.

Question 6

What is the k-VC problem?

Answer 6

Given an undirected graph G = (V, E) on n vertices and a parameter k, is there a set X ⊆ V of size <= k such that each edge of G has at least one end-point in X.