2 Suppose that the undergraduate curriculum of SCIS consists of n courses. To get a bachelor degree, one must take all these n courses. The prerequisite graph G is a directed graph consisting of n vertices one for each course and there is an edge (u, v) = E(G) if and only if course u is a prerequisite for course v. Design an efficient algorithm which, on input prerequisite graph G, outputs the least number of semesters possible to finish all these courses (assume that a student can take any number of courses in one semester).

2 Suppose that the undergraduate curriculum of SCIS consists of n courses. To get a bachelor degree, one must take all these n courses. The prerequisite graph G is a directed graph consisting of n vertices one for each course and there is an edge (u, v) = E(G) if and only if course u is a prerequisite for course v. Design an efficient algorithm which, on input prerequisite graph G, outputs the least number of semesters possible to finish all these courses (assume that a student can take any number of courses in one semester).

Similar questions

Construct the simple graph of 4 vertices, where degree(v1)=3,degree(v2)=2,degree(v3)=2,degree(v4)=1 What is the total number of edges of the complete simple graph of 4 vertices Write a formula to find the total number of edges in a complete simple graph based on n where n is the total number of vertices. How many adjacent vertices to a vertix of degree 3
An undirected graph G = (V,E) is said to be k-colorable if all the vertices of G can be colored using k different colors such that no two adjacent vertices have the same color. Design an algorithm that runs in time O(n + e) to color a graph with two colors or determine that the graph is not 2-colorable.
Design an algorithm to find the maximum spanning tree of any graph with a run time of O(m log m).
3. Given the directed Graph as below. B A 10 C 8 2 D E Using A as the source, illustrate the Dijkstra algorithm to find the shortest path from vertex A to any other vertex. Make sure to show all the steps.
With proper explanation else skip Proper explanation got thumbs-up