CISC4080 COMPUTER ALGORITHMS Homework 1 Assume the use of procedure GREEDY presented in the class to answer all questions below. All your answers which are based on the pseudocode you provide must be consistent with the provided pseudocode. V2 vi 04 US V6 U3 VA U5 03 v2 V6 07 V8 (a) What is the number of colors needed to color each of the graphs according to procedure GREEDY? (b) If the number of colors obtained by using procedure GREEDY results in the number of colors which is greater than the minimum number of colors needed to color the graph, provide the order of the graph vertices that would result in the minimum number of colors needed to color the graph when procedure GREEDY is used. (c) If the number of colors obtained by using procedure GREEDY results in the number of colors which is equal to the minimum number of colors needed to color the graph, provide the order of the graph vertices that would result in obtaining the number of colors larger than the minimum number of colors required to color the graph when procedure GREEDY is used. (d) What is the chromatic number for each of the graphs? (the chromatic number of a graph is the minimum number of colors needed to color the graph ). Justify your answer. (e) Provide the complete pseudocode for the program that colors a graph and uses procedure GREEDY to do so. In your answer you must provide the pseudocode for procedure GREEDY, discussed in the class, as well as the pseudocode for the driver program, i.e., the program that calls procedure GREEDY to color the graph. 1 2 then 4 5 procedure GREEDY(G, newcolor) newcolor to for each uncolored vertex v of G do if v is not adjacent to any vertex in newcolor mark v colored add v to newcolor end-if end-for end-GREEDY