Material: Textbook (Goodrich/Tamassia), Chapters 6 and 7.

HOMEWORK 3 PROBLEMS

In all problems, whenever you are asked to design or describe an algorithm, show a pseudo-code and illustrate it with a simple example.

Chapter 6 Exercises.

1. R-6.1 (basic graph properties)
2. R-6.4 (topological sorting)
3. R-6.6 (graph traversal)
4. R-6.7 (graph data structures)
5. C-6.12 (graph diameter computation)

6. Transitive closure computation.
   Apply Floyd-Warshall algorithm to compute transitive closure for the following directed graph G(V,E):

   V={1,2,3,4}, E={(4,1); (4,3); (3,2); (2,3); (2,4)}

   Notation: (a,b) means a directed edge from node a to node b. Show each step of your procedure.

   Chapter 7 Exercises.

7. C-7.3 (greedy shortest path)
8. C-7.6 (longest path computation)
9. C-7.11 (a),(b), and (c).
   For parts (a) and (b), compute transitive closure for the following graph using adjacency matrix approach.
   Adjacency matrix M for the directed graph is defined as follows:
   M(i,i) = 0, and M(i,j) = 1, iff there is a directed edge (i,j) in G, and i /= j.
   Write a Floyd-Warshall algorithm to compute matrices M^k and illustrate it on the following directed graph G(V,E), for k=1, ..., n: V={1,2,3,4}, E={(4,1); (4,3); (3,2); (2,3); (2,4)}

   Note that M^k is a binary matrix, so you must follow the rules of Boolean algebra in constructing the matrix.
   How many steps do you need to compute transitive closure of G for this graph? Any comments about direted cyclic vs. directed acyclic graph (DAG)?