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.

1.      Form a graph using the vertices V (projects) and the edges E such as G = (V, E)

2.      Run topological sort on the graph G.

3.      Each vertex 'u' has a cost value associated with it tu. Notice that the value is associated with vertex and not with edge.

4.      At each level, add the highest cost vertex to total cost

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:

1.      Let  list_of_critical_projects denote an empty list.

2.      Form a graph using the vertices V (projects) and the edges E such as G = (V, E)

3.      Run topological sort on the graph G.

4.      Each vertex 'u' has a cost value associated with it tu.

5.      At each level, find the highest vertices with highest cost. We may have more than 1 such vertex. Add these vertices to the list_of_critical_projects

6.      Return list_of_critical_projects

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.