Assignment 5: Spanning tree

1. Show using example how a DFS spanning tree can be built on some arbitrarily connected network (with 6 nodes and at least 15 edges).

2. Compute the message and time complexity(?) of the DFS spanning tree.

3. Design the BFS spanning tree.

4. Read(materials from website) and design your own flooding based spanning tree.

5. Explain applications of Spanning Tree in distributed systems.

6. What do you mean by broadcast and convergecast in a distributed system. How is a spanning tree is useful for achieving these two applications?

7. Explain the message complexity of DFS spanning tree construction.

8. Explain the roles of parent and reject message in DFS spanning tree construction

9. Explain the role of unexplored set in DFS tree construction. Also explain how this construction is similar to using a stack in DFS algorithm for graphs.

10. How to create an MST in distributed system?