Suppose the degree requirements for a CS major are organized as a DAG, where ver

Question

Suppose the degree requirements for a CS major are organized as a DAG, where vertices are required courses and an edge (x, y) means course x must be completed prior to the beginning of course y. Make the following assumptions:

- All prerequisites must be obeyed.

- There is a course, CS1, that must be taken before any other courses.

- Every course is offered every semester and there is no limit to the number of courses you can take in one semester.

Describe an efficient algorithm and its pseudocode to compute the minimum number of semester required to complete the degree and analyze its running time.

Explanation / Answer

Solution:

Algorithm:

The above algorithm will give us optimal size assigned tasks to the machines

Correctness: Since we are sorting the prerequisites in the non-decreasing order and then scheduling the tasks according to from smallest to largest, this means while assigning the tasks no prerequisites will be overlapping or not covered. This way we can maximize the number of taks being assigned as well.

Running time:

The above algorithm is sorting the prerequisites so, suppose there are p prerequisites for the task to be assigned then the sorting part will be p log p time to execute and after that every task is being processed

so this will take O(n) time, considering there are n tasks in the machine

So, the time complexity will be

T(n)= O(p log p) + O(n)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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