T F Consider a communication network of nodes where node v needs to broadeast a single message to all the other nodes efficiently. The message should be sent to the shortest paths tree from v. T F Prim's algorithm is a greedy solution of the Minimum Spanning Tree problem. T F Bellman-Fond solves the Minimum Spanning Tree problem. T F Let T be the minimum spanning tree of a connected, undirected, and weighted graph G=(V,E). If e is a new edge, then T{e} contains a cycle. T F Let G be an edge-weighted directed graph with source vertex s and let T be a shortest path tree: from s. Suppose we add a positive constant p to the cost of every edge in G. T remains a shortest path tree from s. T F Let G=(V,E) be a weighted graph and let M be a minimum spanning tree of G. The path in M. between any pair of vertices v1 and v2 must be a shortest path in G T F Bellman-Ford algorithm works on all graphs with negative-cost edges. T F Dijkstra's algorithm works on graphs with negative-cost edges. T F Let G be an edge-weighted directed graph with source vertex s, and let T be a shortest path tree from s. If we add a positive constant p to the cost of every edge incident on s in G. T remains a shortest path tree from s. T F The running time of Dijkstra's algorithm is O(V+E) where V is the number of vertices and E is the number of edges, Problen 2 ( 6 points) Apply Beliman Ford algorithm on the graph below to solve the single source shortest path stanting from ventex S. You need to show the results of each step with all details (hint: use a table as we did in class). Ako, you need to show the final results. Problem 3 ( 6 points) Use a graphical representation to show (step by step) how Prim's algorithm constructs the minimum spanning tree of the graph in Fig. 1. You need to show the subtree resulting from every step assuming that we start from the vertex vl. Figure 1: Undirected weighted graph. Problem 4 ( 8 points) For the following problem. suggest an algorithm design technique and give a high-level description of an algorithm to solve it. (a) Scheduling n jobs of known durations for execution by a single processor where the goal is to minimize the total waiting time of all jobs. The input in this problem is an array T[] where T[i].time is the duration of the ith job and T[i].id is the ID of the ith job. (b) Prove the time complexity of your algorithm as a function of n. Problem 5 (10 points) Suppose you were to drive from Riyadh to Jeddah along a straight one way highway. Your gas tank, when full, holds enough gas to travel M miles, and you have a map that gives distances between gas stations along the route. Let di