# Shared Flashcard Set

## Details

CSCE 411
Algorithm Design and Analysis
12
Computer Science
12/10/2016

Term
 Give an example of a graph for which APPROX-VERTEX-COVER always yields asuboptimal solution.
Definition
 [image][image]
Term
 Give an efficient greedy algorithm that finds an optimal vertex cover for a tree inlinear time.
Definition
 for each non leaf vertex, trim off each edge.(the non-leafvertex 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
 [image]
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 exactlyonce. Show that the language HAM-PATH D fhG; u; i W there is a hamiltonianpath from u to  in graph Gg belongs to NP.
Definition
 Certificate: Set of vertices ycreate algorithm and show it runs in poly time.
Term
 The subgraph-isomorphism problem takes two undirected graphs G1 and G2, andit asks whether G1 is isomorphic to a subgraph of G2. Show that the subgraphisomorphismproblem is NP-complete.
Definition
 [image][image]
Term
 Suppose we perform a sequence of n operations on a data structure in which the i thoperation costs i if i is an exact power of 2, and 1 otherwise. Use aggregate analysisto determine the amortized cost per operation.
Definition
 [image]
Term
 When the summation is infinite and jxj < 1, we have the infinite decreasing geometricseries
Definition
 [image]
Term
 Formula for geometric/exponential series
Definition
 [image]
Term
 For positive integers n, the nth harmonic number is
Definition
 [image]
Term
 Suppose we perform a sequence of n operations on a data structure in which the i thoperation costs i if i is an exact power of 2, and 1 otherwise. Use the accounting methodto determine the amortized cost per operation.
Definition
 [image]
Term
 Suppose we perform a sequence of n operations on a data structure in which the i thoperation costs i if i is an exact power of 2, and 1 otherwise. Use the potential methodto determine the amortized cost per operation.
Definition
 [image]
Supporting users have an ad free experience!