A student needs to take a certain number of courses to graduate, and these cours
ID: 3657123 • Letter: A
Question
A student needs to take a certain number of courses to graduate, and these courses have prerequisites that must be followed. Assume that all courses are offered every semester and that the student can take an unlimited number of courses. Given a list of courses and their prerequisites, compute a schedule that requires the minimum number of semesters Give clear explanations on how the problems can be solved, including: 1. How to build the graph model of the problem: what are the vertices and what are the edges representing? 2. Describe the procedure or the algorithm used to find the answerExplanation / Answer
This is a standard scheduling problem that is solved using topological sort. So, construct a directed graph G(V,E). V = {All courses that need to be taken} E= {(c1,c2) | c1 is a prerequisite for c2}. This graph is acyclic because there cannot be cycles like to take c1 you need to take c2 which needs c3 and c3 needs c1. this cannot be done. Now first do a topological sort on the graph to get a linear order c1 c2 ... cn st all pre req of ci are among {c1, c2, ... c(i-1)}. now just do a linear pass assign 1 to all courses with no pre req - these are sem 1 courses. now for each course, take the max ( # assigned to each pre req) . add 1 to it. This is the sem in which the course will be done. I have attached the topological sort algo. Let me know if you have any doubts. Input: directed acyclic graph Output: sequentially order the nodes without violating any arc ordering. Note: you may have to check for cycles - depending on the problem definition (input: directed graph). Example: course pre-requisite graph, find a linear ordering of courses. An important data: indegree of each node - number of arcs coming in (#courses pre-requisite to "this" course). A first-pass strategy: Eliminate vertices with indegree zero and their associated (outgoing) arcs (thus, reducing indegrees of the connected nodes) - after attaching an ordering-number (for output of topo-sort ordering) to these nodes, keep doing it for number-of-nodes times. If at any stage before finishing with all nodes there does not exist any node with indegree zero, then a cycle is found! A naïve way of finding vertices with indegree zero is to scan the nodes that are still left in the graph. As the loop runs for N times this leads to O(N2) algorithm.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.