Assignment 5 22.1-1 Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? How long does it take to compute the in-degrees? 22.2-5 Argue that in a breadth-first search, the value u:d assigned to a vertex u is inde- pendent of the order in which the vertices appear in each adjacency list. Using Figure 22.3 as an example, show that the breadth-first tree computed by BFS can depend on the ordering within adjacency lists. 22.3-1 Make a 3-by-3 chart with row and column labels WHITE, GRAY, and BLACK. In each cell (i, j), indicate whether, at any point during a depth-first search of a directed graph, there can be an edge from a vertex of color i to a vertex of color j. For each possible edge, indicate what edge types it can be. Make a second such chart for depth-first search of an undirected graph. 23.1-3 Show that if an edge (u, v) is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph. 23.1-5 Let e be a maximum-weight edge on some cycle of connected graph G = (V, E). Prove that there is a minimum spanning tree of G = (V, E – {e}) that is also a minimum spanning tree of G. That is, there is a minimum spanning tree of G that does not include e. 23.2-2 Suppose that we represent the graph G = (V,E) as an adjacency matrix. Give a simple implementation of Prim's algorithm for this case that runs in O(V2) time. 34.1-4 Is the dynamic-programming algorithm for the 0-1 knapsack problem that is asked for in Exercise 16.2-2 (Below) a polynomial-time algorithm? Explain your answer. 16.2-2 Give a dynamic-programming solution to the 0-1 knapsack problem that runs in O(n W) time, where n is the number of items and W is the maximum weight of items that the thief can put in his knapsack.