CS 331-01 Design and Analysis of Algorithms

Homework #3

1. Let G = (V,E) be an undirected graph. A node cover of G is a subset U of the vertex set V such that every edge in E is incident to at least one vertex in U. A minimum node cover is one with the fewest number of vertices. Consider the following greedy algorithm for this problem. Give a counterexample to show that COVER does not always generate a minimum node cover.

procedure COVER (V, E)

{

U = Ø;

loop

let v in V be a vertex of maximum degree;

//if there is more than one choice, arbitrarily select one

U = U  {v};

V = V  {v};

E = E  {(u,w) such that u=v or w=v}

until E == Ø;

return (U);

}

2. Let An = { a1, a2, ..., an } be a finite set of distinct coin types (e.g., a1= 50 cents, a2= 25 cents, a3= 10 cents etc.). We assume each ai is an integer and that a1 > a2 > ... > an. Each type is available in unlimited quantity. The coin changing problem is to make up an exact amount C using a minimum total number of coins. C is an integer > 0.

(a) Assume an = 1, a greedy solution to the problem will make change by using the coin types in the order a1, a2, ..., an. When coin type ai is being considered, as many coins of this type as possible will be given. Write an algorithm based on this strategy.

(b) Give a counterexample to show that the algorithm in (a) doesn't necessarily generate solutions that use the minimum total number of coins. You need to come up with one that’s different than the one covered in the lecture.

3. Let X be a set of n elements to be maintained as a linked list:

X X1 X2 X3 ...

Assume that the cost of examining a particular element Xi is Ci. Note that to examine Xi, one needs to scan through all elements in front of Xi. Let Pi be the probability of searching for element Xi, so the total cost for all searches is

n j

 [ Pj •  Ci ]

j=1 i=1

(a) Give a counterexample to show that storing elements in non-increasing order of Pi does not necessarily minimize the total cost.

(b) Prove that the total cost is minimized when the elements are stored in non-increasing order of Pi/Ci. (Hints: proof by contradiction)