UGC NET CS 2014 June-paper-2
December 5, 2023Question 2525 – Process-Threads
December 5, 2023UGC NET CS 2008-june-Paper-2
| Question 2 |
The complexity of Kruskal’s minimum spanning tree algorithm on a graph with ‘n’ nodes and ‘e ’ edges is :
| O (n) | |
| O (n log n) | |
| O (e log n) | |
| O (e) |
Question 2 Explanation:
MST-KRUSKAL(G,w)
1. A=∅
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v)∈G.E, taken in nondecreasing order by weight
6. if FIND-SET(u)≠FIND-SET(v)
7. A=A∪{(u,v)}
8. UNION(u,v)
9. return A
Analysis:
The running time of Kruskal’s algorithm for a graph G=(V,E) depends on how we implement
the disjoint-set data structure.
→ Initializing the set A in line 1 takes O(1) time, and the time to sort the edges in line 4 is O(ElgE). (We will account for the cost of the |V| MAKE-SET operations in the for loop of lines 2–3 in a moment.)
→ The for loop of lines 5–8 performs O(E) FIND-SET and UNION operations on the disjoint-set forest.
→ Along with the |V| MAKE-SET operations, these take a total of O((V+E)α(V)) time,
where α is the very slowly growing function.
→ Because we assume that G is connected, we have |E|>=|V|-1, and so the disjoint-set operations take O(Eα(V)) time.
→ Moreover, since α |V|=O(lg V)=O(lg E), the total running time of Kruskal’s algorithm is O(ElgE)
→ Observing that |E|<|V|2 , we have lg |E|=O(lg V), and so we can restate the running time of Kruskal’s algorithm as O(E lg V)
1. A=∅
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v)∈G.E, taken in nondecreasing order by weight
6. if FIND-SET(u)≠FIND-SET(v)
7. A=A∪{(u,v)}
8. UNION(u,v)
9. return A
Analysis:
The running time of Kruskal’s algorithm for a graph G=(V,E) depends on how we implement
the disjoint-set data structure.
→ Initializing the set A in line 1 takes O(1) time, and the time to sort the edges in line 4 is O(ElgE). (We will account for the cost of the |V| MAKE-SET operations in the for loop of lines 2–3 in a moment.)
→ The for loop of lines 5–8 performs O(E) FIND-SET and UNION operations on the disjoint-set forest.
→ Along with the |V| MAKE-SET operations, these take a total of O((V+E)α(V)) time,
where α is the very slowly growing function.
→ Because we assume that G is connected, we have |E|>=|V|-1, and so the disjoint-set operations take O(Eα(V)) time.
→ Moreover, since α |V|=O(lg V)=O(lg E), the total running time of Kruskal’s algorithm is O(ElgE)
→ Observing that |E|<|V|2 , we have lg |E|=O(lg V), and so we can restate the running time of Kruskal’s algorithm as O(E lg V)
Correct Answer: C
Question 2 Explanation:
MST-KRUSKAL(G,w)
1. A=∅
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v)∈G.E, taken in nondecreasing order by weight
6. if FIND-SET(u)≠FIND-SET(v)
7. A=A∪{(u,v)}
8. UNION(u,v)
9. return A
Analysis:
The running time of Kruskal’s algorithm for a graph G=(V,E) depends on how we implement
the disjoint-set data structure.
→ Initializing the set A in line 1 takes O(1) time, and the time to sort the edges in line 4 is O(ElgE). (We will account for the cost of the |V| MAKE-SET operations in the for loop of lines 2–3 in a moment.)
→ The for loop of lines 5–8 performs O(E) FIND-SET and UNION operations on the disjoint-set forest.
→ Along with the |V| MAKE-SET operations, these take a total of O((V+E)α(V)) time,
where α is the very slowly growing function.
→ Because we assume that G is connected, we have |E|>=|V|-1, and so the disjoint-set operations take O(Eα(V)) time.
→ Moreover, since α |V|=O(lg V)=O(lg E), the total running time of Kruskal’s algorithm is O(ElgE)
→ Observing that |E|<|V|2 , we have lg |E|=O(lg V), and so we can restate the running time of Kruskal’s algorithm as O(E lg V)
1. A=∅
2. for each vertex v∈ G.V
3. MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v)∈G.E, taken in nondecreasing order by weight
6. if FIND-SET(u)≠FIND-SET(v)
7. A=A∪{(u,v)}
8. UNION(u,v)
9. return A
Analysis:
The running time of Kruskal’s algorithm for a graph G=(V,E) depends on how we implement
the disjoint-set data structure.
→ Initializing the set A in line 1 takes O(1) time, and the time to sort the edges in line 4 is O(ElgE). (We will account for the cost of the |V| MAKE-SET operations in the for loop of lines 2–3 in a moment.)
→ The for loop of lines 5–8 performs O(E) FIND-SET and UNION operations on the disjoint-set forest.
→ Along with the |V| MAKE-SET operations, these take a total of O((V+E)α(V)) time,
where α is the very slowly growing function.
→ Because we assume that G is connected, we have |E|>=|V|-1, and so the disjoint-set operations take O(Eα(V)) time.
→ Moreover, since α |V|=O(lg V)=O(lg E), the total running time of Kruskal’s algorithm is O(ElgE)
→ Observing that |E|<|V|2 , we have lg |E|=O(lg V), and so we can restate the running time of Kruskal’s algorithm as O(E lg V)