You are managing the creation of a large software product. You have the followin

Question

You are managing the creation of a large software product.
You have the following information:
(a) A set V of n small projects that are part of your software product.
(b) A set E of pairs of projects in V . A pair (u,v) is in E if project u must be completed before project v is started. There are no cycles in E.
(c) For each project u V , a duration t u N. This is the amount of time the project will take from start to finish.

You can do any number of projects in parallel, but you can’t start a project before all of its predecessors (according to the list E) are completed. Given this information, you want to know two things: First, how soon can each of the projects be completed? Second, which projects are critical?

We say a project is critical if increasing its duration by 1 would delay the completion of the entire product.

Give an algorithm that takes the inputs above and returns:

(a) For each project u V , the earliest possible completion time c(v).
(b) A list of the critical projects.

Give the running time and space complexity for your algorithm. Prove that your algorithm is correct. (Hint: You may want to compute the completion times c(v) first, then look for critical projects.)

Explanation / Answer

(a) This can be done by using the concept of topological sort.

c(V) = c(V) + tu

This gives the earliest possible completion time.

(b) Critical projects are those sub-projects which if delayed will delay the whole project. This is possible only with the highest cost vertices of each level. This is done similar to part (a) as follows:

Both these algorithms rely on topological sort and it is the costliest step in the algorithms. So, the time complexity is same as that of DFS (which topological sort is built upon). So it is O(|V| + |E|).

For space complexity, notice that we have to maintain an extra stack for DFS. Also a list is used to hold the critical projects in part (b).

So, extra linear space is needed. Therefore, space complexity is O(|E|) because in DFS a single path from root to leaf may be needed to be stored which may have at most |E| edges.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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