You are given a dag G = (V, E) that is the prerequisite graph for a set of courses required for a degree. Each vertex corresponds to a course, and there is an edge from vertex c₁ to vertex c₂ if and only if c₁ is a prerequisite for c₂.

In this problem you will complete the implementation of an algorithm that fills out an array called semesters, so that for each course c, semesters[c] will be the minimum number of semesters that must pass before c can be taken. Assume that any course may be taken in any semester, but only if all the prerequisite courses have been taken in prior semesters. If a course has no prerequisites, the minimum number of semesters that must pass before it can be taken is zero.

For example, consider this prerequisite graph.

After running the algorithm, we would have:

semesters[A] = 0 semesters[B] = 2 semesters[C] = 4 semesters[D] = 1 semesters[E] = 3 semesters[G] = 5 semesters[F] = 6

The algorithm must run in linear time (i.e., O(E+V) for an adjacency list and O(V²) for an adjacency matrix.)

In addition to the array semesters and the graph G, the algorithm has access to G' = (V', E') = the reversed version of G.

Here is the algorithm, with some parts missing:

1) void compute () 2) for each (v in G) 3) minSemesters(v) 4) 5) void minSemesters (v) 6) int sems = 0 7) for each ______ in ______ 8) sems = ______(sems, ______) 9) ______ = sems;

Answer the following questions

On line 2 a loop iterates through the vertices of G. In what order should the iteration be performed?

-It doesn't matter

-Reverse topological sort order (from sinks to sources)

-Topological sort order (from sources to sinks)

On line 7 is a for each loop. What should go in the first blank?

(v,u)

(u,v)

u

v

What should go in the second blank on line 7?

E

V

E'

V'

What should go in the first blank on line 8?

min

max

avg

sum

What should go in the second blank on line 8?

What should go in the blank on line 9?