Question

Suppose a CS curriculum consists of n courses, all of them mandatory. The prerequisite graph G has a node for each course, and an edge from course v to course w if and only if v is a prerequisite for w. Find an algorithm that works directly with this graph representation, and computes the minimum number of semesters necessary to complete the curriculum (assume that a student can take any number of courses in one semester). The running time of your algorithm should be linear.

Short answer

The linear algorithm that computes the minimum number of semesters necessary to complete the curriculum in linear time is as follows:

Input: Graph G

Output: number of required semesters.

Add n vertices that has $d_{in}=0$to the first queue

$n=d_{in}-1$

if $d_{in}-1=0$

add nto the second queue

process second queue

if semester coincides with class schedule

return n

Step-by-step solution

Explain the given information

Consider the CS curriculum consists of n courses. The prerequisite graph G has node for each course and an edge from course v to course w, if and only if v is a prerequisite forw

Step 2: Give the linear time algorithm that computes the minimum number of semesters

The linear algorithm that computes the minimum number of semesters necessary to complete the curriculum in linear time is as follows:

Input: Graph G

Output: number of required semesters.

Add n vertices that has $d_n=0$to the first queue

$n=d_n-1$

if $d_n-1=0$

add n to the second queue

process second queue

if semester coincides with class schedule

return n

The above algorithm runs in the linear-time.

Therefore, The linear algorithm that computes the minimum number of semesters necessary to complete the curriculum in linear time has been provided.