Write short notes on
Kruskal’s algorithm for finding MST
A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges. A single graph can have many different spanning trees. Kruskal's algorithm is a minimum-spanning-tree algorithm where the algorithm finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm n graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
MST-KRUSKAL(G, w)
{
1. A ← Ø
2. for each vertex v belongs to V[G]
3. do MAKE-SET(v)
4. sort the edges of E into non decreasing order by weight w
5. for each edge (u, v) E, taken in non decreasing order by weight
6. do if FIND-SET(u) ≠ FIND-SET(v)
7. then A ← A {(u, v)}
8. UNION(u, v)
9. return A
}
The complexity of the algorithm is as follows:
Sorting of edges takes O(E LogE) time where E is the number of edges. After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time where V is the no of vertices. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost V2, so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)
It is a problem in which we have to color a graph in such a way that no adjacent vertices will have the same color. The minimum number of colors with which we can color a graph is called the chromatic number of the graph.
GCP algo(k)
{
G(V,E ) is a connected graph
g is the adjacency matrix
m=0(chromatic number)
T=list of distinct colors(1,2,……m)
Dead=a Boolean variable
K=next vertex to be colored
1.(i)dead=0
(ii) repeat while dead=0 through 7
2. (i)x=0
(ii) repeat while x=0 through step 5
3.(i) T[k]=(T[k+1])mod(m+1)
(ii) if T[k]=0
(a)x=1
(b) return x
4. repeat for j= 1 to n
(a) if g[k][j]!=0 and T[k]=T[j]
x=1
exit
5. if j=n+1
(a)x=0
(b)return x
6. if T[k]=0
(a)dead=0
(b) return dead
7. if k=n
(a) repeat for r=1 to n
Output T[k]
Else call GCP(k+1)
8. exit
Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.
Find the recurrence relation of binary search and derive the time complexity of binary search.
Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.
What is Decomposition in project estimation method ?
Write a C program to transpose of a matrix.
What is linear searching?
