Could you help with Question 2: algorithm/pseudocode and time complexity if poss

Question

Could you help with Question 2: algorithm/pseudocode and time complexity if possible?

Question 1: Let G be an undirected graph. Write an algorithm that returns the set of all vertices whose degrees are strictly smaller than the degrees of all their neighbors. Question 2: Let T(V, E1) and T(V, E2) be two different spanning tree. Show that there is an edge ei E T, and an edge e2 in T2, so that T? + {e2)-{e1} and Ta + {el)-(e2} are still spanning trees. Question 3: The diameter in a tree is the length of the longest path between any two vertices in the tree. Namely, if dist(u, v) maxz,u[dist(z, w)) then dist(u, v) is the length of the unique paths between u and v in the tree.. Give an algorithm that computes the diameter of a tree. Remark: Do not use things that were not taught in this course but rather in previous courses Question 4: 1. Consider a tree T(VE) with n > 2 vertices. Show that ?veT deg(v) 2n-1 2. Say that we are given n numbers d1, d2, . . . , dn so that ?, 2n-1. Show that at least two of the numbers have value 1 3. Prove that at least one value of the dy above is at least 2 that

Explanation / Answer

The diameter of a tree can be defined as the number of nodes on the longest path between two end nodes.

Here, we can recursive method in order to calculate the diamater of the tree.

So, Diameter of the tree is the largest of following 3 things:

a) Diameter of the tree's left subtree.

b) Diameter of the tree's right subtree.

c) Longest path between end to end leaves that goes through the root of the tree. This will be computed from the heights of the subtrees.

Coming to the complexity part, this algorithm will take O(n).

Pseudocode :

1) Take the root Node and Height as the input parameter.(Initially height will be 0)

2) If root is NULL then height & diameter will be 0. Return 0 from here.

3) If root is not null Repeat step 1 recursively for left subtree & right subtree of root and store it in leftdiameter & rightdiameter(Let's say) respectively. Here, Input parameter to step 1 will be (leftsubtree node or rightsubtree node) as first parameter and second parameter will be height which will be calculated as the sum of 1 and maximum of leftheight & rightheight. (initially leftheight =0 & rightheight = 0)

4) Now, assign the height as returned from the recursive call.

5) finally, calculate Diamater of the tree as the maximum of ((1 + leftheight + rightheight), leftdiameter, rightdiameter). and return the diameter.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.