Term
Give an example of a graph for which APPROXVERTEXCOVER 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 nonleaf 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 01 knapsack problem run in polynomial time? 

Definition
The trick is: O(nW) looks like a polynomial time, but it is not, it is pseudopolynomial. 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 HAMPATH 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 subgraphisomorphism 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 NPcomplete. 

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

