Question

Packets in Ethermet LANs are routed according to the uni que path in a tree whose vertices correspond to clients and edges correspond to physical connections between the clients. In this problem, we want to design an algorithm for finding the "worst-case route, i.e., the two clients that are furthest apart. Let Tbe a tree, where each edge is labeled with distance 1 Figure (2a) Figure (2b) Define the diam eter of Tto be the length of a longest path in T. For ex ample in figure (2a) the diameter is 6 and is associated to path HFDBEGI. In figure (2b), the diameter is 6 also and is associated to the path HDBACGI. a) Design an efficient algorithm to compute the diameter of T.[15 pts Hint: The diam eter of a tree T is the largest of the following quantities: -Diameter of Ts left subtree Diameter of T's right subtree - The longest path between leaves that go through the root of T (this can be computed from the heights of the subtrees of T) b) Determine the time complexity of the algorithm. [5 pts]

Answer 1

appwachius to hind the diameter COCN2)) a) i ub 2 omarumum(I.hiayht.th-hught土1→ mmax

殳 grootnocle DIAMETE t = DIAMETER (goot te 5) ie