CS 330

Summer 2007

Assignment #2

Date Due: Monday, June 4, 2007

Reading: Chapter 24 and Chapter 25, pages 580-636

Problems:

1. Page 58, Problem 3-3 (a). Do this only for the ten functions in the middle 2 of the 6 columns of the list of functions.

2. Page 59, problem 3-4 (g).

3. Page 530, problem 22.1-5

4. Consider the graph on the top of page 548 of the text.

i. Give a depth first search of this graph starting with vertex q.

ii. Consider the undirected version of this graph with the same (undirected) edges. Give a breadth first search of the graph starting at q.

In each case you can either use the BFS and DFS algorithms from the book or the shorter ones given in class.

5. Does Prim work if you allow edge weights to be negative as well as positive ? Why or why not ?

6. Consider the description of a MWST algorithm given in part b. 23-4 on page 578. Prove that this method sometimes fails to produces a MWST of a connected graph G. To do this you need to give a counter-example, that is a graph where the description in part b fails to result in a MWST.

7. Consider the following recursive algorithm to find the median of a list of n distinct numbers, where n is odd. (Recall the median is the number which has (n-1)/2 numbers less than it and (n-1)/2 numbers bigger than it.)

Algorithm A(L): Input is a list L of odd length.

a. If L has only one element out put it and halt.

b. Find the biggest and smallest elements in the list and throw them out of L.

c. Do A(L).

Now assume (as we showed) that it takes (3n-3)/2 comparisons to find the largest and smallest elements in an odd length list of length n. Write the recurrence relation which comes out of the above algorithm and which defines the value of C(n) = the number of comparisons algorithm A does on a list of n elements.

Now solve the recurrence relation and give a simple equation for C(n).

8. A clique in a graph G is a set of vertices U of G which form a complete subgraph of G. (So all edges between vertices in U are present in G.)

Consider the following greedy algorithm for finding the maximum size clique in a graph.

(1). Delete from the graph a vertex that is not connected to every other vertex.

(2). Repeat (1) until the remaining graph is a clique.

------------------------------------------------

(a). Give an example to show this does not always give the the optimal solution.

(b). Show that the above algorithm does not give a solution which is within a constant k times the optimal solution, for any fixed constant k.

(Note b --> a, so if you can do part b that will count for a as well. )