Suppose you\'re given a DAG where nodes are courses and edges represent prereq-

Question

Suppose you're given a DAG where nodes are courses and edges represent prereq- uisite relationships. Recall that if you can only take one course per semester, then you could satisfy all prerequisites by taking courses in a topological order. Now, assuming each course is offered every semester and you're willing to take an unlimited number of courses per semester, write a Python function semesters_to_graduate (adj) that returns the minimum number plete all courses while satisfying all prerequisites. For example, here's the adjacency list of a DAG where the nodes are major computer science courses, and edges represent (required or recommended) prerequisites. (This is ignoring that some COMP courses have MATH prerequisites, and that there are a bunch of gen ed requirements.) #0COMP 1900 # 1-:COMP 1950 [4, 5, 7, 8, 9], # 2 COMP 2150 3 COMP 2700 4COMP 3115 5 = COMP 3410 # 6 COMP 3825 # 7 COMP 4030 8 = COMP 4040 9COMP 4081 # 10 = COMP 4270 # 11 COMP 4601 # 12 = COMP 4882 example = [[2, 3], CI 0 [6, 71, [10], [J [12] 0 [1 011 semesters_to_graduate (example) should return 5, because an optimal schedule is to take [O, 1] in the 1st semester, [2, 3] in the 2nd semester, [4, 5, 6, 7, 8) inthe 3rd semester, [9, 10, 11] in the 4th semester, and [12] in the 5th semester. The algorithm should run in time O(n + m). It can be classified as greedy: in each semester you should take all the courses with indegree 0 (after having deleted the courses already taken).

Explanation / Answer

Python code:

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.