(2) (15 pts) Suppose we have graphs stored with the standard adjacency lists. Some times it helps to have each of the lists in the sorted order. This problem has to do with sorting the adjacency lists of a graph efficiently. (2a) Suppose we apply an optimal comparison based sorting (such as mergesort) to sort each of the adjacency lists; recall that such an algorithm can sort n integers in O(nlogn) time; this means, sorting p integers would costplogp. What is the overall complexity of such an algorithm to sort all the adjacency lists? Give as good a bound as you can. (2b) Suppose we use BinSort, looked at in class, to sort each of the adjacency lists. What is the overall complexity of the algorithm ? Clearly specify the values for k and p mentioned in BinSort. (2c) Present an O(m+n) time algorithm for undirected graphs. Hint: The previous two problems should suggest that "standard sorting" in straight forward way may not work. Think of the problem this way: given adjacency lists Adj[1] through Adj[n] for graph G, you want to build new adjacency lists nAdj[1] through nAdj[n] for G so that each of the nAdj[] lists is sorted. Build new adjacency lists from scratch in sorted fashion gradually. We want to build n Adj [] lists, starting from empty lists, so that each list is sorted. Obviously, we would like to add l's to the nAdj[] lists first, and then the 2's, and so on. If we do this, when we add 8 's, for example, any of the previously added 1 through 7 in the lists are already in a sorted order. Now, how do we know which of the nAdj[] lists should have a 1 added to them? (2) (15 pts) Suppose we have graphs stored with the standard adjacency lists. Some times it helps to have each of the lists in the sorted order. This problem has to do with sorting the adjacency lists of a graph efficiently. (2a) Suppose we apply an optimal comparison based sorting (such as mergesort) to sort each of the adjacency lists; recall that such an algorithm can sort n integers in O(nlogn) time; this means, sorting p integers would costplogp. What is the overall complexity of such an algorithm to sort all the adjacency lists? Give as good a bound as you can. (2b) Suppose we use BinSort, looked at in class, to sort each of the adjacency lists. What is the overall complexity of the algorithm ? Clearly specify the values for k and p mentioned in BinSort. (2c) Present an O(m+n) time algorithm for undirected graphs. Hint: The previous two problems should suggest that "standard sorting" in straight forward way may not work. Think of the problem this way: given adjacency lists Adj[1] through Adj[n] for graph G, you want to build new adjacency lists nAdj[1] through nAdj[n] for G so that each of the nAdj[] lists is sorted. Build new adjacency lists from scratch in sorted fashion gradually. We want to build n Adj [] lists, starting from empty lists, so that each list is sorted. Obviously, we would like to add l's to the nAdj[] lists first, and then the 2's, and so on. If we do this, when we add 8 's, for example, any of the previously added 1 through 7 in the lists are already in a sorted order. Now, how do we know which of the nAdj[] lists should have a 1 added to them
