CS 3158: Design and Analysis of Algorithms
Homework : Due Friday, 21st August 1998

1. (10 points) Let be a directed graph and be its transitive closure. Show how can be updated in time when a new edge is added to G.
2. (20 points) Let A be the adjacency matrix of a directed graph G with n vertices. Let denote the matrix obtained by multiplying A with itself n times using Boolean OR as addition and Boolean AND as multiplication.
   1. Prove that the (i,j)-th entry of is 1 iff there is a directed path of length n from i to vertex j in the graph G.
   2. Using this describe an algorithm to decide if there is a directed path from vertex i to vertex j for any pair of vertices i,j in G.
3. 1. (10 points) Let be an undirected graph. Define a binary relation on E as follows: an edge e is related to an edge f iff they both lie on a simple cycle. Prove that this relation is an equivalence relation.
   2. (5 points) Identify the equivalence classes under this relation for the graph in figure 23.10 on page 495 of the text.
4. (10 points) Exercise 22.2-2, page 446 of the text.
5. (15 points) Exercise 24.2-4, page 510 of the text.

   (Consider only the data structure used for this problem in class: linked-list representation for the sets with weighted-union heuristic - section 22.2 of the text.)

6. (15 points) Let G be a weighted connected graph and T be a minimum spanning tree in G. Let x and y be two non-adjacent vertices in G. Suppose a new edge with weight w is added to G. Describe an efficient algorithm to update the tree T so that it is a minimum spanning tree for the modified graph. Why is your algorithm correct? What is the time complexity of your algorithm?
7. (15 points) Let G be a directed graph with n vertices and m edges in which all edge weights are integers between 1 and k for some constant k. Design an O(n+m) algorithm for the single source shortest path problem for such graphs.

• About this document ...