CS 330

Summer 2007

Assignment #3

Date Due: Tuesday, June 12

Reading: Chapter 15, pages 321-356 and Chapter 28, pages 725-742

Problems:

1. Page 577, problem 23-3 parts a. and b.

2. A centroid of a tree with n vertices is a vertex such that its deletion leaves no subtree with more than n/2 vertices.


         e---f
         |
         |
a---b----c
    |    |
    d    |
         g---h

Here vertex c is the centroid.

Write an algorithm to find a centroid of a tree. What is the complexity of your algorithm ?

You should be able to get a linear O(n) solution although partial credit will be given for a nonlinear algorithm.

3. i. Carry out Dijkstra's algorithm on the graph on page585, figure 24.2 of the textbook starting from vertex z.

ii. Does Dijkstra's algorithm work if you allow edge weights to be negative as well as positive ? Why or why not ?

4. Consider the greedy graph coloring algorithm given in class.

Show that for any graph G, there is an ordering of the vertices of G such that when you color G using the greedy graph coloring algorithm you get a minimal size coloring.

5. Page 627, problem 25.1-1

Do this problem only for the Faster all-pairs-shortest-paths algorithm.

6. Page 635, problem 25.2-6