1 hour
Introduction video for MST
This experiment requires you to have basic knowledge about :
And above all, a curiosity to learn and explore..!
Module | Weightage | Expectation |
---|---|---|
Pre Test | 5% | Solve All Questions |
MST | 10% | Understand concept of MST |
Kruskal's Algorithm | 20% | Understand the Kruskal's Algorithm |
Analysis of Kruskal's | 15% | Understand the time and space complexity |
Prim's Algorithm | 20% | Understand the Prim's Algorithm |
Analysis of Prim's | 15% | Understand the time and space complexity |
Post Test | 10% | Solve all Questions |
10 minutes
Given a list of random numbers, sorting means ordering the numbers in either ascending or descending order. By default, we sort numbers in an ascending order.
Picture shows sorted and unsorted array
Picture shows types of graphs
A Min-Heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.
Picture shows types of graphs
Union-Find algo has two
important components Find and Union.
In Union-Find all elements of
a tree are represented by head
element in tree and when two
trees are joined, the head of
anyone of them is taken as head of
new tree.
Find : Determine which subset (or) which tree the node belongs to.
Union : Join
two subsets or two trees
into same subset or tree.
When a new node is
joined to a differnet tree
or subset, both subsets
together will be counted as
a new subset or new tree
such that the whole subset
has a common head.
When a new edge is to be
added, it has to be checked if both
nodes of edge belong to same
tree in which case circle is
passed.
Picture helps for the visualization of Union-finds
Q1. Which of these best describes an array?
(A) A data structure that shows a hierarchical behavior
(B) Container of objects of similar types
(C) Container of objects of mixed types
(D) All of the mentioned
An array is a data structure, which can store a fixed-size collection of elements of the same data type.
Q2. What is the time complexity of insertion at any point in an array?
(A) O(N)
(B) O(N^2)
(C) O(NLogN)
(D) None of these
Taking a general example,inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n). Worst case would be when you have to insert at the starting of the array,you will need to move n elements
Q3. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
(A) X will always be a better choice for small inputs
(B) X will always be a better choice for large inputs
(C) Y will always be a better choice for small inputs
(D) X will always be a better choice for all inputs
Performance could be similar for small inputs, but definitely better for larger inputs
Q4. int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
What is the time and space complexity for the above code?
(A) O(N * M) time, O(1) space
(B) O(N + M) time, O(N + M) space
(C) O(N + M) time, O(1) space
(D) O(N * M) time, O(N + M) space
The first loop runs for O(n) time, second loop runs for O(m). Constant extra space is used for 2 variables a and b, hence O(1) space.
Q5. Choose one of the correct statements from the following?
(A) Trees may have cycles but not graphs.
(B) Graphs may have cycles but not trees
(C) Time complexity of Union-Find is O(n^{2})
(D) Time complexity of Union-Find is O(nlog(n))
Time complexity of Union-Find is O(log(N)).
Q6. What is the best possible order in which an array can be sorted?
(A) O(n^{2})
(B) O(nlog(n))
(C) O(n)
(D) O(log(n))
Best time complexity in which an array can be sorted in nlog(n).
15 minutes
Minimum Spannning Tree (MST) is defined for a weighted graph as the smallest weighted spanning tree Where Spanning Tree is a tree in graph such that it covers all edges of graph.
15 minutes
In this module, we will :
Image shows scenarios to add and when not to.
Let's take note of a few important observations :
image shows Step by Step Process for One Iteration
Video for Kruskal's Explanation
Let's have a final look at the consolidated algorithm to find MST of given graph:
image shows Iteration by Iteration Visualization of Kruskal's
Interactive artefact where user can click on Next Step or Previous Step to understand how the MST gets created at different levels.
Interactive artefact where user can click on Next Step or Previous Step to understand how the edges add to MST levels
Interactive artefact where user can generate questions and solve them, and then check the answers.
Q1. When do we add an edge to MST while running Kruskal's ?
(A) When circle is formed by the new edge
(B) when the added edge dosen't create a circle
(C) when there is no circle at all
(D) if any circle exists
An edge is added to MST when it doesn't create a circle.
Q2. Which edge gets judged if it should or shouldn't be in MST after n iterations?
(A) Smallest edge
(B) Largest Edge
(C) Middle Edge in inc order
(D) No element
Q3. How many minimum edges should we add to MST to stop checking?
(A) V edges
(B) V-1 edges
(C) E edges
(D) E-1 edges
Since min spanning tree is a tree with V vertices it contains V-1 edges.
Q4. Consider the following statements.
S1. Kruskal’s algorithm might produce a non-minimal spanning tree.
S2. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.
(A) S1 is true but S2 is false
(B) Both S1 and S2 are false
(C) Both S1 and S2 are true
(D) S2 is true but S1 is false
In Kruskal’s algorithm, the disjoint-set data structure efficiently identifies the components containing a vertex and adds the new edges. And Kruskal’s algorithm always finds the MST for the connected graph.
Q5. Which of the following is false about the Kruskal’s algorithm?
(A) It is a greedy algorithm
(B) It constructs MST by selecting edges in increasing order of their weights
(C) It can accept cycles in the MST
(D) It uses union-find data structure
Kruskal’s algorithm is a greedy algorithm to construct the MST of the given graph. It constructs the MST by selecting edges in increasing order of their weights and rejects an edge if it may form the cycle. So, using Kruskal’s algorithm is never formed.
10 minutes
While sorting, we need an extra array to store sorted array of edges (Space comlexity of O(E)), Another array for Union-Find of size O(E). So, total Space Complexity would be O(log(E)).
Q1. What is the time complexity of Kruskal's algorithm?
(A) Best case is when given graph is a tree it self
(B) Best case O(n^{2})
(C) Worst case is when all edges are to be checked.
(D) Average case O(Nlog(E)+Nlog(N))
(E) A, C, D
All statements are self explanatory
Q2. Does Kruskal's need more than one MST ?
(A) Yes
(B) No
(C) Depend
(D) Can't say
Kruskal's generate only one MSt.
Q3. Which case is the best case Time Complexity of Kruskal's ?
(A) Max.no of edges and many cycles
(B) Min.no of edges and minimum cycles
(C) Min No.of edges with max no of cycles
(D) Can't Say
Complexity is min when no of edges and cycles are Minimum.
Q4. If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ?
(A) O(m logn)
(B) O(n)
(C) O(m)
(D) O(n logm)
O(m) as you are already given edge weights in sorted order. You just have to pick the edges in the increasing order and add it to the current spanning set if its addition does not result in a cycle else throw it away.
Q5. What is the best case Time Complexity of Kruskal's?
(A) O((N-1)log(E)+Elog(E))
(B) O((N)log(N)+Elog(E))
(C) O((N)log(E)+Elog(E))
(D) Cannot Determine
Given a tree then tree itself is MST.
15 minutes
In this module, we will :
Image shows scenarios which edge to add in MST
From the mentioned algorithm, we can conclude that:
image shows Step by Step Process for One Iteration
Video for Prim's
Let's have a final look at the consolidated algorithm to find mst of given graph:
From the mentioned algorithm, we can conclude that,
image shows Iteration by Iteration Visualization of Prim's
Interactive artefact where user can click on Next Step or Previous Step to understand how the MST gets created at different levels.
Interactive artefact where user can click on Next Step or Previous Step to understand how the edges add to MST levels.
Interactive artefact where user can generate questions and solve them, and then check the answers. Ideas : find edge to be added etc
Q1. When do we add vertex adjacent to newly added vertex to MST into Min-heap?
(A) If its present in Min-heap
(B) If its neither in MSt nor in Min-heap.
(C) If its already in MSt
(D) If its in Min-heap and MSt
Self-explanatory options
Q2. How many edges are present in MST after k iterations
(A) exactly K
(B) Less than K and atmost k
(C) More than k and atleast k
(D) Can't Say
Exactly 1 edge must be added in evrey iteration so its total of K edges.
Q3. Which of the following statements are false ?
(A) Prim's algo must be started from any vertex
(B) Prim's algo defenitely takes N-1 iterations to find MST
(C) Prim's algo started from a diferent vertices may give different MSts
(D) None of the above are false
(E) One of A,B,C is false
All A,B,C are correct.
Q4. Prim’s algorithm can be efficiently implemented using _____ for graphs with greater density.
(A) d-array heap
(B) linear search
(C) fibonacci heap
(D) binary search
In Prim’s algorithm, we add the minimum weight edge for the chosen vertex which requires searching on the array of weights. This searching can be efficiently implemented using binary heap for dense graphs. And for graphs with greater density, Prim’s algorithm can be made to run in linear time using d-ary heap(generalization of binary heap).
Q5. Which of the following is false about Prim’s algorithm?
(A) It is a greedy algorithm
(B) It constructs MST by selecting edges in increasing order of their weights
(C) It never accepts cycles in the MST
(D) It can be implemented using the Fibonacci heap
Prim’s algorithm can be implemented using Fibonacci heap and it never accepts cycles. And Prim’s algorithm follows greedy approach. Prim’s algorithms span from one vertex to another
10 minutes
In this module, we will be learning about :
Lets assume that we are given V vertices and E edges in a graph for which we need to find an MST.
Comparisons :
Image shows comparision Graphs and tables
Q1. What is the time complexity of Prim's algorithm?
(A) O((V+E)log(V))
(B) O(Vlog(V)+Elog(E))
(C) O(Vlog(E)+Elog(E))
(D) O(Elog(V)+Elog(E))
Time complexity of Prim's algorithm is O((V+E)log(V)).
Q2. Is Prim's algorithm always better than Kruskal's algorithm?
(A) Yes
(B) No
(C) Depend
(D) Can't say
It depends on V,E.
Q3. What is the best case Time Complexity of Prim's algorithm?
(A) O(V)
(B) O(n^{2})
(C) Somewhere in between N and N^{2}
(D) None of the above
Complexity is E when given graph is a linear tree.
Q4. What is the worst case Time Complexity of Prim’s algorithm if adjacency matrix is used?
(A) O(log V)
(B) O(V^{2})
(C) O(E^{2})
(D) O(V log(E))
Use of adjacency matrix provides the simple implementation of the Prim’s algorithm. In Prim’s algorithm, we need to search for the edge with a minimum for that vertex. So, worst case time complexity will be O(V2), where V is the number of vertices.
Q5. Which of the following statements is true
S1 . Prim’s algorithm resembles Dijkstra’s algorithm.
S2 . Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
(A) S1 and S2 both are false
(B) S1 is false and S2 is true
(C) Both S1 and S2 are true
(D) S2 is false and S1 is true.
In Prim’s algorithm, the MST is constructed starting from a single vertex and adding in new edges to the MST that link the partial tree to a new vertex outside of the MST. And Dijkstra’s algorithm also rely on the similar approach of finding the next closest vertex. So, Prim’s algorithm resembles Dijkstra’s algorithm.
Prim’s algorithm and Kruskal’s algorithm perform equally in case of the sparse graphs. But Kruskal’s algorithm is simpler and easy to work with. So, it is best suited for sparse graphs.
10 minutes
Post Test includes questions on entire experiment concepts. Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.
Q1. Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false?
(A) Every minimum spanning tree of G must contain emin.
(B) If emax is in a minimum spanning tree, then its removal must disconnect G
(C) No minimum spanning tree contains emax
(D) G has a unique minimum spanning tree
As edge weights are
unique, there will
be only one edge
emin and that will
be added to MST,
therefore option (A)
is always true.
As spanning tree has
minimum number of
edges, removal of
any edge will
disconnect the
graph. Therefore,
option (B) is also
true.
As all edge weights
are distinct, G will
have a unique
minimum spanning
tree. So, option (D)
is correct.
Option C is false as
emax can be part of
MST if other edges
with lesser weights
are creating cycle
and number of edges
before adding emax
is less than (n-1).
Q2. What is the best case Time Complexity of Kruskal's?
(A) O((N-1)log(E)+Elog(E))
(B) O((N)log(N)+Elog(E))
(C) O((N)log(E)+Elog(E))
(D) Cannot Determine
Given a tree then tree itself is MST.
Q3. How many iterations of MST are required to run Kruskal's algorithm on a non-cyclic graph ?
(A) V
(B) V-1
(C) E
(D) E-1
MST has N-1 edges and since none forms a cycle MST will be obtained in N-1 iterations
Q4. What is the minimum and maximum number of MST's possible for a given connected undirected non cyclic graph?
(A) Min : 1, Max: 1
(B) Min : 1, Max :N
(C) Min : N, MAx : N
(D) MIN : 1, Max : E
There will only be one MST in given case.
Q5. Which of the following is false about Prim’s algorithm?
(A) It is started from an edge
(B) It constructs MSt in increasing order of their weights
(C) It never accepts cycles in MST
(D) It can be implemented using heaps
In Kruskal's MST is made with edges in increasing order and not in Prim's.
You can explore more about MST Experiment through following resources:
Useful Links :
Quizzes :