Answer True or False to each of the questions below, and explain briefly why you think the answer is correct..

(a) The following three algorithms are examples of greedy algorithms: Dijkstras shortest path algorithm, Kruskals minimum spanning tree algorithm, Prims minimum spanning tree algorithm.

(b) In the Bellman-Ford algorithm, the maximum number of times that the distance label of a given node i can be reduced is less than or equal to n 1, where n is the number of nodes in the graph.

(c) Bellman-Ford algorithm can be used for finding the longest path in a graph.

(d) In Floyds algorithm for finding all-pairs shortest paths, after each major outer loop k, upper bounds are computed on shortest distances D(i, j) between each pair of nodes i, j. These upper bounds correspond to the shortest distance among all paths between nodes i and j which use only intermediate nodes in {1, . . . , k}.

(e) Consider a directed, weighted graph where every arc in the graph has weight 100. For this graph, executing Dijkstras algorithm to find a shortest path tree starting from a given node is equivalent to performing breadth first search.

(f) Consider a directed, capacitated graph, with origin node O and destination node D. The maximum flow which can be sent from O to D is less than or equal to the minimum of the following two quantities: the sum of the capacities of the arcs leaving O, and the sum of the capacities of the arcs entering D.

(g) In Dijkstras algorithm, the temporary distance labels D assigned to nodes which have not yet been scanned can be interpreted as the minimum distance among all paths with intermediate nodes restricted to the nodes already scanned.

(h) The worst case complexity of the fastest minimum spanning tree algorithm is O(Nlog(N)), where N is the number of nodes in the graph.

(i) Consider an undirected graph where, for every pair of nodes i, j, there exists a unique simple path between them. This graph must be a tree.

(j) Consider a minimum spanning tree T in a connected undirected graph (N, A) which has no two arcs with equal weights. Then, an arc i,j in T must be either the minimum weight arc connected to node i or the minimum weight arc connected to node j.