Term
Give an example of a graph for which APPROX-VERTEX-COVER always yields a
suboptimal solution. |
|
Definition
|
|
Term
Give an efficient greedy algorithm that finds an optimal vertex cover for a tree in
linear time. |
|
Definition
for each non leaf vertex, trim off each edge.
(the non-leaf
vertex always should be chosen, since it is the only one which can also cover other edges). Repeat until there's 1 edge then select either of the vertices. |
|
|
Term
| Approximate Subset Sum with Trim |
|
Definition
|
|
Term
| Does the 0-1 knapsack problem run in polynomial time? |
|
Definition
| The trick is: O(nW) looks like a polynomial time, but it is not, it is pseudo-polynomial. Time complexity measures the time that an algorithm takes as function of the length in bits of its input. The dynamic programming solution is indeed linear in the value of W but exponential in the length of W - and that's what matters. |
|
|
Term
A hamiltonian path in a graph is a simple path that visits every vertex exactly
once. Show that the language HAM-PATH D fhG; u; i W there is a hamiltonian
path from u to in graph Gg belongs to NP. |
|
Definition
Certificate: Set of vertices y
create algorithm and show it runs in poly time. |
|
|
Term
The subgraph-isomorphism problem takes two undirected graphs G1 and G2, and
it asks whether G1 is isomorphic to a subgraph of G2. Show that the subgraphisomorphism
problem is NP-complete. |
|
Definition
|
|
Term
Suppose we perform a sequence of n operations on a data structure in which the i th
operation costs i if i is an exact power of 2, and 1 otherwise. Use aggregate analysis
to determine the amortized cost per operation. |
|
Definition
|
|
Term
When the summation is infinite and jxj < 1, we have the infinite decreasing geometric
series |
|
Definition
|
|
Term
| Formula for geometric/exponential series |
|
Definition
|
|
Term
| For positive integers n, the nth harmonic number is |
|
Definition
|
|
Term
Suppose we perform a sequence of n operations on a data structure in which the i th
operation costs i if i is an exact power of 2, and 1 otherwise. Use the accounting method
to determine the amortized cost per operation. |
|
Definition
|
|
Term
Suppose we perform a sequence of n operations on a data structure in which the i th
operation costs i if i is an exact power of 2, and 1 otherwise. Use the potential method
to determine the amortized cost per operation. |
|
Definition
|
|
