Question

Please explain answer a little bit I'm familiar with these all topics..just give hint with your answer... the first question is quick sort
1) (13 points)
 Show the results of pivoting the following array using  0.34 as the pivot value.
 0.34 -4.62  8.50 -5.45  7.80  8.19  9.72 -2.85  0.88 -0.07 -0.28 -3.58

2)(13 points)
Draw the graph defined by the following adjacency matrix:

     ?         ?         ?         ?       -4.8      -2.3       9.7       3.9  
     ?         ?       -4.6       5.1      -8.5       2.0      -2.2      -9.1  
     ?       -4.6         ?      -2.9      -2.4      -3.2       2.3         ?  
     ?        5.1      -2.9        ?         ?        9.0       7.4       5.0  
   -4.8      -8.5      -2.4        ?         ?       -5.0      -6.9      -9.6  
   -2.3       2.0      -3.2       9.0      -5.0         ?       5.9      -7.7  
    9.7      -2.2       2.3       7.4      -6.9       5.9         ?      -3.8 

3)(13 points)
Show the order in which the vertices of the graph from question 3 will be visited in a depth first traversal.
Use 0, 1, 2, 3, 4, 5, 6, 7 as the names of the nodes, and assume that the neighbors of any node are given in left to right order across the matrix.

4)(13 points)
Consider the following adjacency matrix.
?    4.0  3.0  1.0  
4.0  ?    8.0  1.0
3.0  8.0  ?    5.0
1.0  1.0  5.0  ?
Use Kruskal's algorithm to find a minimum spanning tree.

 
    3.9      -9.1        ?        5.0      -9.6      -7.7      -3.8         ?

Answer 1

Note-:Question 2 and 3 here are not valid,in order to create a graph,you must have a square matrix.However , the matrix given in question is 7*8.However , i will try to answer the other 2 questions.

1)Quick sort is an algorithm based on divide and concur.The idea is to separate the array into sub arrays until all arrays have only 1 elements using linear time.In above problem we are using 0.34 as pivot and divide the list into 2 parts:-

step1-:Take two variables i and j pointing to starting index of the list excluding pivot
step2-:if arr[i]<pivot , swap a[i] and a[j] , increment i , increment j
if not,increment j

In above problem->

 0.34 -4.62  8.50 -5.45  7.80  8.19  9.72 -2.85  0.88 -0.07 -0.28 -3.58

after 1st iteration-:

1st part->-4.62,-5.45,-2.85,-0.07,-0.28,-3.58

2nd part->8.50,0.88,7.80,8.19,9.72

i)i=1,j=1,

0.34>-4.62,(swap a[i],a[j])i++,j++

ii)i=2,j=2,

0.34<8.50,j++(i unchanged)

iii)i=2,j=3,

0.34<-5.45,swap i,j(i++,j++)

keep on repeating till j==size of array

for next iteration, pivot is the 1st element in both sub parts,when all the sub parts all sorted they are merged again to create a sorted array

4)Kruksal algorithm for minimum spanning tree is used to fing minimum subgraph of a graph that connects all vertices.this is based on greedy algorithm.

step1: Sort all the edges in increasing order of their weight.
step2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
step3: Repeat step 2 until there are V-1 edges in the spanning tree.

given graph is:

the graph here has 4 vertices, so number of edges in spanning tree will be 3:

weigt of edges are->

1: between 1 and 4

1: between 2 and 4

3: between 1 and 3

4: between 1 and 2

5: between 3 and 4

8: between 2 and 3

So, we take edge with weight 1 between 1 and 4,since no cycle is formed we will include it

graph is--> (1)-----------------(4)

1  

now,edge between 2 and 4 with weight 1,since no cycle is formed we will include it

graph is--> (1)------------(4)-------------(2)

1 1

now with weight 3 between 1 and 3,since no cycle is formed we will include it

minimum spanning tree is-:

(3)------------(1)--------------(4)-------------(2)

3 1 1