1,In any tree T with n nodes, the distance between two nodes u and v in T is the number of nodes on the path from u to v. The diameter of T is the maximum distance between two nodes in T. Describe an O(n) running time algorithm to compute the diameter of a tree using level-order traversal (also known as Breadth First Search).(using pseudo-code).
2. Prove that it is impossible to develop a comparison-based implementation of the Priority Queue ADT in which both insert and removeMin methods guarantee to use O(log log n ) comparisons in the worst case.
3. Suppose that we are given a sequence S of n elements, each of which is an integer in the range [0,n^2-1]. Describe a simple algorithm to sort S in O(n) time.
4.Show that the expected search time for hashing using open addressing is at most 1/(1- w) where w is the load fa.ctor. State your assumption.