Q1:
The diameter of a tree is defined to the largest of all shortest path distances in the tree. Give an efficient algorithm to compute the diameter of tree, given its root. Show that your algorithm is correct and analyze the running time of your algorithm.
Q2:
Given a list of university courses and their prerequisites, what is the minimum number of semesters needed to take all the courses? Assume that every course is offered every semester and you may take as many courses as you need to. Give an efficient algorithm for finding the minimum number of semesters, show that it is correct, and analyze the running time.
Q3:
Suppose that graph G is an undirected graph with an infinite number of vertices. Suppose that s and x are two distinct vertices in G, and that the distance between them is 2. Will BFS(s) always discover vertex x? Will DFS-Visit(s) always discover vertex x(assuming that DFS-Visit(s) is the first time DFS-Visit is called?) Justify your answers .If your answer is ’no’ to either question, are there conditions for which the answer would be ’yes?’ If so, state such conditions