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
Write short notes on
Define software quality. Briefly explain McCall’s quality factors.
What is ISO 9000 Certification? How to Get ISO 9000 Certification?
Describe Cost of Software Quality
What do you mean by software crisis & its solution.
Write a C program to find the roots of a quadratic equation.
