Algorithms

Algorithmics (CE00333-3) Individual Assignment PT1181106 TABLE OF CONTENTS TASK 1: SCENARIO....................................................................................................................... 3 TASK 1: SOLUTION ...................................................................................................................... 4 a) Adjacency Matrix & Adjacency List .............................................................................................................................4 ADJACENCY MATRIX ................................................................................................................................................................ 4 ADJACENCY LIST ....................................................................................................................................................................... 5 b) Pseudo-codes for the BFS, DFS and Dijkstra’s Algorithm ...................................................................................6 Pseudo code for Breadth First Search (BFS) ALGORITHM ............................................................................................ 6 Pseudo code for Depth First Search (DFS) ALGORITHM ................................................................................................ 7 Pseudo code for Dijkstra’s ALGORITHM ............................................................................................................................. 8 c) Step by step solution for the BFS, DFS and Dijkstra’s of the give n graph. ...................................................9 Step by step solution of BFS ALGORITHM (unweighted) ................................................................................................ 9 Step by step solution of DFS ALGORITHM (unweighted) ..............................................................................................16 Step by step solution of Dijkstra’s Algorithm ..................................................................................................................26 d) Efficiencies for the BFS, DFS and Dijkstra’s Alg orithm .................................................................................... 36 Time Complexity of BFS Algorithm ....................................................................................................................................36 Time Complexity of DFS Algori thm ....................................................................................................................................36 Time Complexity of DIJKSTRA Algorithm.........................................................................................................................36 TASK 2: SCENARIO..................................................................................................................... 37 TASK 2: SOLUTION .................................................................................................................... 38 a) Adjacency Matrix & Adjacency List .......................................................................................................................... 38 ADJACENCY MATRIX ..............................................................................................................................................................38 ADJACENCY LIST .....................................................................................................................................................................39 b) Pseudo-codes for the Prim’s and Kruskal’s Alg orithm .................................................................................... 40 Pseudo code for Prim’s ALGORIT HM .................................................................................................................................40 Pseudo code for Kruskal’s ALGORITHM ...........................................................................................................................41 c) Step by step solution for the Prim’s and Kruskal’s of the given graph. ..................................................... 42 Step by step solution of PRIM’s ALGORITHM ..................................................................................................................42 Step by step solution of KRUSKAL’s ALGORITHM..........................................................................................................62 d) Efficiency of the Prim’s and Kruskal’s algorithms in terms of big -oh. ....................................................... 67 TIME COMPLEXIT Y OF PRIM’S ALGORITHM: ..................................................................................................................67 TIME COMPLEXIT Y OF KRUSKAL’ S ALGORITHM: .........................................................................................................68 TASK 3: SCENARIO..................................................................................................................... 69 Level-3 Asia Pacific Institute of Information Technology Page 1 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 TASK 3: SOLUTION .................................................................................................................... 69 a) All phases of insert operations .................................................................................................................................. 69 b) All phases of deleteMin operations .......................................................................................................................... 71 c) Complexity of Heap Sort in terms of Big -oh Notation....................................................................................... 84 REFERENCES ............................................................................................................................................................................... 85 Websites: ...................................................................................................................................................................................85 Books:.........................................................................................................................................................................................85 Level-3 Asia Pacific Institute of Information Technology Page 2 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 TASK 1: SCENARIO Graph theory has many practical applications in the real world. One such application is to determine how a network of interconnected places can be optimized in order to ensure that commuters can travel as efficiently as possible. For this specific assignment, the first graph problem is represented hereby: Fig. 1 Graph Theory Problem (for BFS, DFS & Dijkstra’s SSSP) The nodes in the above diagram represent the various places scattered across a country, while the edges represent the roads running between them. The weight of each edge represents the distance between the two places along the edge. You have to deliver a solution for the problem mentioned above by completing the following tasks: a. Draw adjacency list and adjacency matrix of the graph given. b. Write the pseudo-codes for the BFS, DFS and Dijkstra’s algorithm along with their explanation. c. Provide step by step solution for the BFS, DFS and Dijkstra’s of the given graph.(For BFS and DFS algorithm consider the graph as unweighted one) d. Compute the efficiencies of the above algorithms in terms of big-Oh. Level-3 Asia Pacific Institute of Information Technology Page 3 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 TASK 1: SOLUTION a) Adjacency Matrix & Adjacency List ADJACENCY MATRIX ADJACENCY MATRIX A B C D E F G H I J A 0 3 0 0 1 0 0 5 0 0 B 0 0 4 0 0 0 0 0 0 0 C 0 0 0 1 0 4 0 0 0 0 D 0 0 0 0 0 2 0 0 0 0 E 0 0 1 0 0 0 0 2 3 0 F 0 0 0 0 0 0 4 0 0 6 G 0 0 0 5 0 0 0 0 0 1 H 0 0 0 0 0 0 0 0 0 0 I 0 0 7 0 0 2 0 6 0 3 J 0 0 0 0 0 0 0 0 0 0 Level-3 Asia Pacific Institute of Information Technology Page 4 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 ADJACENCY LIST ADJACENCY LIST A 0 B 3 E 1 H 5 B 0 C 4 C 0 D 1 F 4 D 0 F 2 E 0 C 1 H 2 I 3 F 0 G 4 J 6 G 0 D 5 J 1 H 0 I 0 C 7 F 2 H 6 J 3 J 0 Level-3 Asia Pacific Institute of Information Technology Page 5 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 b) Pseudo-codes for the BFS, DFS and Dijkstra’s Algorithm Pseudo code for Breadth First Search (BFS) ALGORITHM S. No. BFS Algorithm Explanation BFS(G,s) /* G = (V,E) */ Graph G is represented by adjacency list G 1. For each vertex u in V - {s} Here u is the vertices of the graph G and V is the set of vertices. 2. u.color = WHITE Color of all the vertices will be white in color. 3. u.distance =  The distance of all the vertices is initialized with ∞, except the root (source) vertex. 4. u. predecessor = NIL The parents of all the vertices are set as NIL. 5. s.color = GRAY The root (source) vertex will be gray in color. 6. s.distance = 0 The distance of root vertex has been initialized with 0 as it is the first vertex to be processed. 7. s. predecessor = NIL The parent of the root vertex is set as NIL. 8. While Q is equal to empty (= ) Initially the queue Q is empty. 9. ENQUEUE(Q,s) Inserting the source vertex s in Queue. 10. While Q is not empty ( ) While loop has been put with the condition of non – empty queue (Q) until the queue is empty. 11. u = DEQUEUE The DEQUEUE elements are stored in u. 12. For each v adjacent to u For loop has been put for each vertex v which are adjacent to vertex u. 13. if v.color = WHITE In explored state, vertex v is in white color 14. v.color = GRAY Color of vertex v is now changed to gray color 15. v.distance = u.distance + 1 The distance of vertex v is the sum of distance of parent and 1. 16. u = DEQUEUE The DEQUEUE elements are stored in u. 17. v. predecessor = u The parent of the vertex v is set as u. 18. ENQUEUE(Q,v) The vertex v is inserted in the queue (Q). 19. u.color = BLACK The color of the explored node is changed to black color. Level-3 Asia Pacific Institute of Information Technology Page 6 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Pseudo code for Depth First Search (DFS) ALGORITHM S. No. DFS Algorithm Explanation DFS(G,s) /*G = (V,E)*/ Graph G is represented by adjacency list G 1. For each vertex u in V Here u is the vertices of the graph G and V is the set of vertices. 2. do u.color = WHITE Initialize color of each vertex is white in color. 3. u. predecessor = NIL Initially the parent of each vertex is NIL. 4. time = 0 The starting time of the source node is zero 5. For each vertex v adjacent to u The for loop consider each vertex v in the adjacency list of u. 6. do if u.color = WHITE The condition if the color of the vertex is white 7. then DFS - VISIT(u) If the color is white, then DFS VISIT is applied on u. S. No. DFS - VISIT(u) Explanation 8. u.color = GRAY When adjacent node u is visited or explored then its color changes from white to gray. 9. time = time + 1 The starting time is increased by 1. 10. For each vertex v adjacent to u Each vertex v adjacent to u and visits v if it is white. 11. do if v.color = WHITE It examines whether the color of vertex is white or not and then it proceeds. 12. then v.pred = u The parent of visited node is updated. 13. DFS–VISIT(u) Again DFS–VISIT is applied on the vertex which was explored recently. 14. u.color = BLACK Finally the color of the vertex which is fully explored is set as black. Level-3 Asia Pacific Institute of Information Technology Page 7 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Pseudo code for Dijkstra’s ALGORITHM S. No. Dijkstra Algorithm Explanation DFS(G,s) INITIALIZE SINGLE-SOURCE Graph G is represented by adjacency list G and the source vertex is s 1. For each vertex v in V Here for all the vertex, we set the vertex in graph 2. v.distance =  Initialize the distance of each vertex be infinity 3. v.predecessor = NIL Initially the parent of each vertex is NIL. 4. s.distance = 0 Initially the distance of source vertex is set to 0. 5. S =  Initially the set S is set as null or empty. 6. Q V(G) Initially the min-priority queue Q contains all the vertices in V which is in ascending order by weight 7. While Q ≠  Initialize the min-priority queue Q 8. u = EXTRACT-MIN(Q) Each time when while loop is called a vertex u is extracted from queue Q 9. S = S U{u} Perform relaxation for each vertex v adjacent to u 10. For each vertex v adjacent to u While loop has been put with the condition of non – empty queue (Q) until the queue is empty. 11. u = DEQUEUE The DEQUEUE elements are stored in u. 12. For each vertex v adjacent to u Examines each vertex v adjacent to u and also visits v 13. //Relax (u,v,w) 14. if v.distance >(u.distance + edge-weight( u,v)) Check the minimum distance of vertex 15. then v.distance = u.distance + edge-weight(u,v) Update the distance of vertex 16. v.predecessor = u Update the predecessor of the vertex Level-3 Asia Pacific Institute of Information Technology Page 8 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 c) Step by step solution for the BFS, DFS and Dijkstra’s of the given graph. Step by step solution of BFS ALGORITHM (unweighted) Here it has been mentioned in the scenario that we have to assume that the graph is unweighted. Initially the color of the entire vertex is white and its distance is initialized to ∞. The parent or predecessor of all the vertices is initially NIL. The BFS uses First in First Out queue (FIFO) to store vertices which become gray after traversal. A Step 1: GRAPH DESCRIPTION B C H G D J I E F All the vertices will be in WHITE in color. Distance of all the vertices will be ∞ Parent of all the vertices will be = NIL Let’s assume the source vertex is node A. So first discover the source vertex A and add into queue Q. Also change the color of vertex A to gray and it distance and predecessor to 0. All other vertices will be white in color. GRAPH DESCRIPTION B C H G D J I E F A Source node = A [Let] A.Color = GRAY Q A Distance = 0 Predecessor = NIL Level-3 Asia Pacific Institute of Information Technology Page 9 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 2: All the adjacent white vertices (B, E, H) of gray vertex A must be explored and added in the queue. Now change the color of adjacent vertices of parent A to gray. As all the white adjacent vertices of A are explored, there is no need to check vertex A further so change the color of parent vertex A to black and delete it from the queue Q. GRAPH DESCRIPTION D B C H G J I E F A A.Color = BLACK B.Color = GRAY E.Color = GRAY H.Color = GRAY Q B E H Distance 1 1 1 Predecessor A A A Step 3: As in queue three vertices are present so we will first explore the white adjacent vertex of the vertex which enter first in the queue i.e. B whose white adjacent vertex is only C. We have to add that vertex in queue and update the queue. There is no further need to check vertex B so change the color of parent vertex to black and delete it from the queue Q. GRAPH DESCRIPTION B C H G D J I E F A B.Color = BLACK E.Color = GRAY H.Color = GRAY C.Color = GRAY Q E H C Distance 1 1 2 Predecessor A A B Level-3 Asia Pacific Institute of Information Technology Page 10 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 4: As there are three vertices in the queue Q following FIFO, we will explore the adjacent vertex of vertex E as it enters into the queue first. E is having only one white adjacent vertex i.e. I. We have to add that vertex in queue and update the queue Q. There is no further need to check the vertex I, as all the adjacent vertex of E is explored so change the color of parent vertex to black and delete it from the queue Q. GRAPH DESCRIPTION B C H G D J I E F A E.Color = BLACK H.Color = GRAY C.Color = GRAY I.Color = GRAY Q H C I Distance 1 2 2 Predecessor A B E Step 5: As there are three vertices in the FIFO queue Q, we will explore the white adjacent vertex of vertex H as it enters into the queue first. There are no white adjacent vertices of H. There is no further need to check the vertex H, as all the adjacent vertex of H is explored so change the color of parent vertex to black and delete it from the queue Q. GRAPH DESCRIPTION B C H G D J I E F A H.Color = BLACK C.Color = GRAY I.Color = GRAY Q C I Distance 2 2 Predecessor B E Level-3 Asia Pacific Institute of Information Technology Page 11 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 6: As there are two vertices in the FIFO queue Q, we will explore the white adjacent vertex of vertex C as it enters into the queue first. There are two white adjacent vertex of C i.e. D and F. We will add the vertex D into the queue Q and update the queue Q. There is no further need to check the vertex C, as all the adjacent vertex of C is explored so change the color of parent vertex to black and delete it from the queue Q. GRAPH DESCRIPTION B C H G D J I E F A C.Color = BLACK I.Color = GRAY D.Color = GRAY F.Color = GRAY Q I D F Distance 2 3 3 Predecessor E C C Step 7: As there are three vertices in the FIFO queue Q, we will explore the adjacent vertex of vertex I as it enters into the queue first. The white adjacent vertex of I is only vertex J. We will add the vertex J into the queue Q and update the queue. There is no further need to check the vertex I, as all the adjacent vertex of I is explored so change the color of parent vertex to black and delete it from the queue Q. GRAPH DESCRIPTION B C H G D J I E F A I.Color = BLACK D.Color = GRAY F.Color = GRAY J.Color = GRAY Q D F J Distance 3 3 3 Predecessor C C I Level-3 Asia Pacific Institute of Information Technology Page 12 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 8: As there are three vertices in the FIFO queue Q, we will explore the adjacent vertex of vertex D as it enters into the queue first among the three vertices. There is no further need to check the vertex D, as all the adjacent vertex of D is explored so change the color of parent vertex to black and delete it from the queue Q. GRAPH DESCRIPTION D B C H G J I E F A D.Color = BLACK F.Color = GRAY J.Color = GRAY Q F J Distance 2 3 Predecessor D I Step 9: We will explore the adjacent vertex F as it enters into the queue first. The white adjacent vertex of F is only vertex G. We will add the vertex G into the queue Q and update the queue. There is no further need to check the vertex F, as all the adjacent vertex of F is explored so change the color of parent vertex to black and delete it from the queue Q. GRAPH DESCRIPTION B C H G D J I E F A F.Color = BLACK J.Color = GRAY G.Color = GRAY Q J G Distance 3 4 Predecessor I F Level-3 Asia Pacific Institute of Information Technology Page 13 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 10: We will explore the vertex J as it enters into the queue first. There is no white adjacent vertex left to vertex J. There is no further need to check the vertex J, as all the adjacent vertex of J is explored so change the color of parent vertex to black and delete it from the queue Q. GRAPH DESCRIPTION B C H G D J I E F A J.Color = BLACK G.Color = GRAY Q G Distance 4 Predecessor F Step 11: There is no white adjacent vertex left to vertex G. All the adjacent vertices of G are already deleted and since vertex G is the only vertex left in the queue, so there is no further need to check the vertex G, as all the adjacent vertex of G is explored so change the color of parent vertex to black and delete it from the queue Q. GRAPH DESCRIPTION B C H G D J I E F A G.Color = BLACK Q ɸ Now the queue becomes empty so no more nodes are left to check, that means Traversal is complete. Level-3 Asia Pacific Institute of Information Technology Page 14 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 After Breadth First traversal, the final graph is: B C H I E A Tree after Breadth First Traversal A B E D J H I J F C D G G F Path of traversal of graph according to Breadth First Traversal are: A, B, E, H, C, I, D, F, J, G Level-3 Asia Pacific Institute of Information Technology Page 15 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step by step solution of DFS ALGORITHM (unweighted) Here it has been mentioned in the scenario that we have to assume that the graph is unweighted. Initially the color of the entire vertex is white and its distance is initialized to ∞. The parent or predecessor of all the vertices is initially NIL. B.pred=NIL B.color=WHITE A GRAPH DESCRIPTION C.pred=NIL C.color=WHITE D.pred=NIL D.color=WHITE B C D G.pred=NIL G.color=WHITE E.pred=NIL E.color=WHITE F.pred=NIL F.color=WHITE E F G H I J A.pred=NIL A.color=WHITE J.pred=NIL J.color=WHITE I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE Step 1: B.pred=NIL B.color=WHITE A GRAPH DESCRIPTION C.pred=NIL C.color=WHITE D.pred=NIL D.color=WHITE B C D G.pred=NIL G.color=WHITE E.pred=NIL E.color=WHITE F.pred=NIL F.color=WHITE E F G H I J 1 A.pred=NIL A.color=GRAY J.pred=NIL J.color=WHITE I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE All the vertices will be WHITE in color. The distance of all the vertices will be ∞. Predecessor of all the vertices will be NIL. Let’s assume the source vertex is node A. So first discover the source vertex A and make its color to GRAY. As this is the first node to be traversed so mark it as 1 and predecessor to NIL. Level-3 Asia Pacific Institute of Information Technology Page 16 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 2: B.color=GRAY A GRAPH DESCRIPTION C.pred=NIL C.color=WHITE D.pred=NIL D.color=WHITE 2 B C D G.pred=NIL G.color=WHITE B.pred=A E.pred=NIL E.color=WHITE F.pred=NIL F.color=WHITE E F G H I J 1 A.pred=NIL A.color=GRAY J.pred=NIL J.color=WHITE I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE Step 3: B.color=GRAY A GRAPH DESCRIPTION C.pred=B C.color=GRAY D.pred=NIL D.color=WHITE 2 3 B C D G.pred=NIL G.color=WHITE B.pred=A E.pred=NIL E.color=WHITE F.pred=NIL F.color=WHITE E F G H I J 1 A.pred=NIL A.color=GRAY J.pred=NIL J.color=WHITE I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE There are three adjacent vertices of A i.e. B, E & H. Now explore any one of the adjacent vertex of A which I chose is B. Color the vertex B as GRAY and predecessor of B is A. As we visit the node on second number, so we mark it as 2. We will explore the white adjacent vertex of B which is C. The color of the vertex C will be GRAY and predecessor of C is B. As we visit the node on third number, so we mark it as 3. Level-3 Asia Pacific Institute of Information Technology Page 17 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 4: B.color=GRAY A GRAPH DESCRIPTION C.pred=B C.color=GRAY D.pred=C D.color=GRAY 2 3 4 B C D G.pred=NIL G.color=WHITE B.pred=A E.pred=NIL E.color=WHITE F.pred=NIL F.color=WHITE E F G H I J 1 A.pred=NIL A.color=GRAY J.pred=NIL J.color=WHITE I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE Step 5: B.color=GRAY A GRAPH DESCRIPTION C.pred=B C.color=GRAY D.pred=C D.color=GRAY 2 3 4 B C D G.pred=NIL G.color=WHITE B.pred=A E.pred=NIL E.color=WHITE F.pred=D F.color=GRAY E 5 F G H I J 1 A.pred=NIL A.color=GRAY J.pred=NIL J.color=WHITE I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE After exploring C, we will explore one of the white adjacent nodes of C which is D. Change the color of vertex D to GRAY and predecessor of D is C. As we visit the node on forth number, so we mark it as 4. After exploring D, we will explore one of the white adjacent nodes of D which is F. Change the color of vertex F to GRAY and predecessor of F is D. As we visit the node on fifth number, so we mark it as 5. Level-3 Asia Pacific Institute of Information Technology Page 18 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 6: B.color=GRAY A GRAPH DESCRIPTION C.pred=B C.color=GRAY D.pred=C D.color=GRAY 2 3 4 B C D G.pred=NIL G.color=WHITE B.pred=A E.pred=NIL E.color=WHITE F.pred=D F.color=GRAY E 5 F G H I J 1 A.pred=NIL A.color=GRAY 6 J.pred=F J.color=GRAY I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE Step 7: B.color=GRAY A GRAPH DESCRIPTION C.pred=B C.color=GRAY D.pred=C D.color=GRAY 2 3 4 B C D G.pred=NIL G.color=WHITE B.pred=A E.pred=NIL E.color=WHITE F.pred=D F.color=GRAY E 5 F G H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE After exploring F, we will explore one of the white adjacent nodes of F which is J. Change the color of vertex J to GRAY and predecessor of J is F. As we visit the node on sixth number, so we mark it as 6. After visiting vertex J, we found that there are no adjacent vertices which can be explored further. We will change the color of vertex J to BLACK and predecessor of J will remain same i.e. F. We will mark it as 6/7 and move further. Level-3 Asia Pacific Institute of Information Technology Page 19 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 8: B.color=GRAY A GRAPH DESCRIPTION C.pred=B C.color=GRAY D.pred=C D.color=GRAY 2 3 4 B C D G.pred=J G.color=BLACK B.pred=A E.pred=NIL E.color=WHITE F.pred=D F.color=GRAY E 5 F G H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE 8/9 Step 9: B.color=GRAY A GRAPH DESCRIPTION C.pred=B C.color=GRAY D.pred=C D.color=GRAY 2 3 4 B C D G.pred=J G.color=BLACK B.pred=A E.pred=NIL E.color=WHITE F.pred=D F.color=BLACK E 5/10 F G H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE 8/9 After visiting vertex G, we found that there are no white adjacent vertices which can be explored. So we will change the color of vertex G to BLACK and predecessor of G is J. As we are moving backward, so we will mark G as 8/9. As moving backtrack, we reach to the node F and as no node is left which is white. It means exploration of F is complete so change the color of vertex F to BLACK and predecessor of F will be same i.e. D. Mark it 5/10 and move to the parent node D. Level-3 Asia Pacific Institute of Information Technology Page 20 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 10: B.color=GRAY A GRAPH DESCRIPTION C.pred=B C.color=GRAY D.pred=C D.color=BLACK 2 3 4/11 B C D G.pred=J G.color=BLACK B.pred=A E.pred=NIL E.color=WHITE F.pred=D F.color=BLACK E 5/10 F G H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE 8/9 Step 11: GRAPH DESCRIPTION C.pred=B C.color=BLACK D.pred=C D.color=BLACK B.color=GRAY 2 3/12 4/11 B C D A G.pred=J G.color=BLACK B.pred=A E.pred=NIL E.color=WHITE F.pred=D F.color=BLACK E 5/10 F G H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE 8/9 As moving backtrack, we reach to the node D and as no node is left which is white. It means exploration of D is complete so change the color of vertex D to BLACK and predecessor of D will be same i.e. C. Mark it 4/11 and move to the parent node C. As moving backtrack, we reach to the node C and as no node is left which is white. It means exploration of C is complete so change the color of vertex C to BLACK and predecessor of C will be same i.e. B. Mark it 3/12 and move to the parent node B. Level-3 Asia Pacific Institute of Information Technology Page 21 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 12: GRAPH DESCRIPTION C.pred=B C.color=BLACK D.pred=C D.color=BLACK B.color=BLACK 2/13 3/12 4/11 B C D A G.pred=J G.color=BLACK B.pred=A E.pred=NIL E.color=WHITE F.pred=D F.color=BLACK E 5/10 F G H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE 8/9 Step 13: GRAPH DESCRIPTION C.pred=B C.color=BLACK D.pred=C D.color=BLACK B.color=BLACK 2/13 3/12 4/11 B C D A G.pred=J G.color=BLACK B.pred=A E.color=GRAY F.pred=D F.color=BLACK E F G E.pred=A 14 8/9 5/10 H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=NIL I.color=WHITE H.pred=NIL H.color=WHITE As moving backtrack, we reach to the node B and as no node is left which is white. It means exploration of B is complete so change the color of vertex B to BLACK and predecessor of B will be same i.e. A. Mark it 2/13 and move to the parent node A. As moving backtrack, we reach to the node A but node A is having white adjacent vertex i.e. E & H, so I chose E and move further. We will change the color of vertex E to GRAY as it was not visited before and the predecessor of E will be A. Mark it as 14. Level-3 Asia Pacific Institute of Information Technology Page 22 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 14: GRAPH DESCRIPTION C.pred=B C.color=BLACK D.pred=C D.color=BLACK B.color=BLACK 2/13 3/12 4/11 B C D A G.pred=J G.color=BLACK B.pred=A E.color=GRAY F.pred=D F.color=BLACK E F G E.pred=A 14 8/9 5/10 15 H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=E I.color=GRAY H.pred=NIL H.color=WHITE Step 15: GRAPH DESCRIPTION C.pred=B C.color=BLACK D.pred=C D.color=BLACK B.color=BLACK 2/13 3/12 4/11 B C D A G.pred=J G.color=BLACK B.pred=A E.color=GRAY F.pred=D F.color=BLACK E F G E.pred=A 14 8/9 5/10 16 15 H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=E I.color=GRAY H.pred=I H.color=GRAY As moving forward, we reach to the node I which was white in color and was also not visited before, so we will change the color of vertex I to GRAY and the predecessor of I will be E. Mark it as 15. As moving forward, we reach to the node H which was white in color and was also not visited before, so we will change the color of vertex H to GRAY and the predecessor of H will be I. Mark it as 16. Level-3 Asia Pacific Institute of Information Technology Page 23 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 16: GRAPH DESCRIPTION C.pred=B C.color=BLACK D.pred=C D.color=BLACK B.color=BLACK 2/13 3/12 4/11 B C D A G.pred=J G.color=BLACK B.pred=A E.color=GRAY F.pred=D F.color=BLACK E F G E.pred=A 14 8/9 5/10 16/17 15 H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=E I.color=GRAY H.pred=I H.color=BLACK Step 17: GRAPH DESCRIPTION C.pred=B C.color=BLACK D.pred=C D.color=BLACK B.color=BLACK 2/13 3/12 4/11 B C D A G.pred=J G.color=BLACK B.pred=A E.color=GRAY F.pred=D F.color=BLACK E F G E.pred=A 14 8/9 5/10 16/17 15/18 H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=E I.color=BLACK H.pred=I H.color=BLACK As moving further, we found that all nodes are visited. So we will move back to the parent node and node H will be marked as 16/17. The color of node H will be changed to BLACK and predecessor of H will be same i.e. I. As moving backtrack, we reach to the node I and no node of I is left which is white. It means exploration of I is complete, so change the color of node I to BLACK and mark it as 15/18 and will move back to the parent node i.e. E. Level-3 Asia Pacific Institute of Information Technology Page 24 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 18: GRAPH DESCRIPTION C.pred=B C.color=BLACK D.pred=C D.color=BLACK B.color=BLACK 2/13 3/12 4/11 B C D A G.pred=J G.color=BLACK B.pred=A E.color=BLACK F.pred=D F.color=BLACK E F G E.pred=A 14/19 8/9 5/10 16/17 15/18 H I J 1 A.pred=NIL A.color=GRAY 6/7 J.pred=F J.color=BLACK I.pred=E I.color=BLACK H.pred=I H.color=BLACK Step 19: GRAPH DESCRIPTION C.pred=B C.color=BLACK D.pred=C D.color=BLACK B.color=BLACK 2/13 3/12 4/11 B C D A G.pred=J G.color=BLACK B.pred=A E.color=BLACK F.pred=D F.color=BLACK E F G E.pred=A 14/19 8/9 5/10 16/17 15/18 H I J 1/20 A.pred=NIL A.color=BLACK 6/7 J.pred=F J.color=BLACK I.pred=E I.color=BLACK H.pred=I H.color=BLACK As moving backtrack, we reach to the node E and no node of E is left which is white. It means exploration of E is complete, so change the color of node E to BLACK and mark it as 14/19 and will move back to the parent node i.e. A. As moving backtrack, we reach to the last node A and no node of A is left which is white. It means exploration of A is complete, so change the color of node A to BLACK and mark it as 1/20. Predecessor of node A will remain as NIL. Level-3 Asia Pacific Institute of Information Technology Page 25 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step by step solution of Dijkstra’s Algorithm Here it has been mentioned in the scenario that we have to assume that the graph is weighted. Initially the color of the entire vertex is white and its distance is initialized to ∞ except the source vertex A whose distance will be 0. The parent or predecessor of all the vertices is initially NIL. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 Source vertex = A [Let] The distance of all the vertices will be ∞ except the source vertex A whose distance will be 0. Predecessor of all the vertices will be NIL. Queue A B C D E F G H I J Distance 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ Predecessor NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL Step 1: As we have assumed the source node as vertex A, A is having the minimum distance as 0. Add it to S and relax all the nodes adjacent to source node A. The adjacent nodes of A are B, E & H. Update all the predecessor of all the adjacent nodes and we will dequeue the source node A. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 Adjacent nodes of A = B, E, H Predecessor of B, E and H = A and rest all the vertices will be NIL. Distance of all the adjacent nodes will be updated. Level-3 Asia Pacific Institute of Information Technology Page 26 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 For vertex B: if B.distance > A.distance + wt.(A,B) => ∞ > 0+3 (True), then B.distance = 3, B.predecessor = A For vertex E: if E.distance > A.distance + wt.(A,E) => ∞ > 0+1 (True), then E.distance = 1, E.predecessor = A For vertex H: if H.distance > A.distance + wt.(A,H) => ∞ > 0+5 (True), then H.distance = 5, H.predecessor = A Queue A B C D E F G H I J Distance 0 3 ∞ ∞ 1 ∞ ∞ 5 ∞ ∞ Predecessor NIL A NIL NIL A NIL NIL A NIL NIL Graph: S = {A} Step 2: A We have to chose the minimum distance node which is at priority in the queue Q i.e. vertex E. We will add the vertex E into the set S and relax all the adjacent nodes of E which are C, H, I. The predecessor of all the adjacent nodes will get updated and node E will be dequeued. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 Adjacent nodes of E = C, H, I Predecessor of C, H and I = E and rest all the vertices will be NIL. Distance of all the adjacent nodes will be updated and E will be dequeued. For vertex C: if C.distance > E.distance + wt.(E,C) => ∞ > 1+1 (True), then C.distance = 2, C.predecessor = E Level-3 Asia Pacific Institute of Information Technology Page 27 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 For vertex H: if H.distance > E.distance + wt.(E,H) => 5 > 1+2 (True), then H.distance = 3, H.predecessor = E For vertex I: if I.distance > E.distance + wt.(E,I) => ∞ > 1+3 (True), then I.distance = 4, I.predecessor = E H distance will be replaced from 5 to 3 as recent distance of H was greater than parent distance + edge length from parent node. Queue A B C D E F G H I J Distance 0 3 2 ∞ 1 ∞ ∞ 3 4 ∞ Predecessor NIL A E NIL A NIL NIL E E NIL Graph: S = {A, E} Step 3: A E 1 We have to delete the minimum distance node which is at priority in the queue Q i.e. vertex C and then add the vertex C into the set S by relaxing all the adjacent nodes of C which are D and F. Now the predecessor of all the adjacent nodes will get updated and node C will be dequeued. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 Adjacent nodes of C = D, F Predecessor of D and F = C Distance of all the adjacent nodes will be updated. For vertex D: if D.distance > C.distance + wt.(C,D) => ∞ > 2+1 (True), then D.distance = 3, D.predecessor = C Level-3 Asia Pacific Institute of Information Technology Page 28 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 For vertex F: if F.distance > C.distance + wt.(C,F) => ∞ > 2+4 (True), then F.distance = 6, F.predecessor = C Queue A B C D E F G H I J Distance 0 3 2 3 1 6 ∞ 3 4 ∞ Predecessor NIL A E C A C NIL E E NIL Graph: S = {A, E, C} Step 4: A E C 1 1 We have to delete the minimum distance node which is at priority in the queue Q i.e. vertex B and then add the vertex B into the set S by relaxing all the adjacent nodes of B which is C. But C is already deleted from the queue so no need to relax it and node B will be dequeued. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 Adjacent nodes of B = C Predecessor of B will remain same i.e. A No node will be updated as B does not have any adjacent node left. Queue A B C D E F G H I J Distance 0 3 2 3 1 6 ∞ 3 4 ∞ Predecessor NIL A E C A C NIL E E NIL Graph: S = {A, E, C, B} Level-3 Asia Pacific Institute of Information Technology Page 29 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 5: B 3 1 A E C 1 We have to delete the minimum distance node which is at priority in the queue Q i.e. vertex D and then add the vertex D into the set S by relaxing all the adjacent nodes of D which is F. Now the predecessor of all the adjacent nodes will get updated and node D will be dequeued. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 Adjacent nodes of D = F Predecessor of F will be D Distance of all the adjacent nodes will be updated. For vertex F: if F.distance > D.distance + wt.(D,F) => 6 > 3+2 (True), then F.distance = 5, D.predecessor = C F distance will be replaced from 6 to 5 as recent distance of F was greater than parent distance + edge length from parent node. Queue A B C D E F G H I J Distance 0 3 2 3 1 5 ∞ 3 4 ∞ Predecessor NIL A E C A D NIL E E NIL Level-3 Asia Pacific Institute of Information Technology Page 30 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Graph: S = {A, E, C, B, D} Step 6: B 3 1 A E C D 1 1 We have to delete the minimum distance node which is at priority in the queue Q i.e. vertex H and then add the vertex H into the set S. Since there is no adjacent node of vertex H so delete the vertex H from the queue. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 There is no adjacent node of H so no update in the queue. Queue A B C D E F G H I J Distance 0 3 2 3 1 5 ∞ 3 4 ∞ Predecessor NIL A E C A D NIL E E NIL Graph: S = {A, E, C, B, D, H} B 3 1 A E C D 1 2 1 H Level-3 Asia Pacific Institute of Information Technology Page 31 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 7: We have to delete the minimum distance node which is at priority in the queue Q i.e. vertex I and then add the vertex I into the set S by relaxing all the adjacent nodes of I which is C, H, F and J. But C and H is already deleted from the queue so no need to relax it. Now the predecessor of all the adjacent nodes F and J will get updated and node I will be dequeued. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 Adjacent node of I = C, H, F and J Predecessor of F and J = I Node I will be dequeued. For vertex F: if F.distance > I.distance + wt.(I,F) => 5 > 4+2 (False), then F.distance = 5, F.predecessor = D For vertex J: if J.distance > I.distance + wt.(I,J) => ∞ > 4+3 (True), then J.distance = 7, J.predecessor = D Queue A B C D E F G H I J Distance 0 3 2 3 1 5 ∞ 3 4 7 Predecessor NIL A E C A D NIL E E I Graph: S = {A, E, C, B, D, H, I} B 3 A E C D 1 H I 2 1 3 1 Level-3 Asia Pacific Institute of Information Technology Page 32 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 8: We have to delete the minimum distance node which is at priority in the queue Q i.e. vertex F and then add the vertex F into the set S by relaxing all the adjacent nodes of F which is G and J. Now the predecessor of all the adjacent nodes G and J will get updated and node F will be dequeued. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 Adjacent nodes of F = G and J Predecessor of G will be F and J will be I Distance of all the adjacent nodes will be updated. For vertex G: if G.distance > F.distance + wt.(F,G) => ∞ > 5+4 (True), then F.distance = 5, F.predecessor = D For vertex J: if J.distance > F.distance + wt.(F,J) => 7 > 5+4 (False), then J.distance = 7, J.predecessor = D Queue A B C D E F G H I J Distance 0 3 2 3 1 5 9 3 4 7 Predecessor NIL A E C A D F E E I Graph: S = {A, E, C, B, D, H, I, F} B 3 A E C D H I 1 F 2 1 3 2 Level-3 Asia Pacific Institute of Information Technology Page 33 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 9: We have to delete the minimum distance node which is at priority in the queue Q i.e. vertex J and then add the vertex J into the set S. As there are no adjacent nodes of vertex J, so no need to check further and therefore node J will be dequeued. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 No adjacent nodes of J The distance will not be updated. Queue A B C D E F G H I J Distance 0 3 2 3 1 5 9 3 4 7 Predecessor NIL A E C A D F E E I Graph: S = {A, E, C, B, D, H, I, F, J} B 3 A E C D 1 H I 1 F J 2 3 3 2 1 Level-3 Asia Pacific Institute of Information Technology Page 34 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 10: Now we are left with only one vertex i.e. G. So we have to delete the vertex G from the queue and then add the vertex G into the set S. As there are no adjacent nodes of vertex G, so no need to check further and therefore node G will be dequeued and the queue will be empty. GRAPH DESCRIPTION A 4 1 B C D 3 1 5 4 2 1 4 E F G 3 2 7 5 2 6 3 6 H I J 1 No adjacent nodes of G The distance will not be updated. Q A B C D E F G H I J Distance 0 3 2 3 1 5 9 3 4 7 Predecessor NIL A E C A D F E E I Graph: S = {A, E, C, B, D, H, I, F, J, G} B 3 A E C D 1 H I F 4 J G 1 2 3 1 3 2 As all the nodes are added in set S and the minimum priority Q is empty so it means stop there. Queue = {ɸ} Level-3 Asia Pacific Institute of Information Technology Page 35 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 d) Efficiencies for the BFS, DFS and Dijkstra’s Algorithm Time Complexity of BFS Algorithm The space complexity of BFS is expressed as O|V|. Every vertex is added only once in the queue thus occupies O(1) space and vertex V occupies O(V). As every vertex is initialized, added in the queue and dequeued from the queue at most once. The operation of enqueuing takes O(1) time so the total time taken by V vertex is O(V). Because adjacency vertex of each vertex is scanned only when vertex is de-queued, so each adjacent vertex is discovered at least once when directed and two times when undirected. The for-loop inside the while loop is executed at most |E| times if G is a directed graph or 2|E| times if G is undirected. Time Complexity of DFS Algorithm In the case of DFS, each vertex is initialized once and initialization of source node takes O(V) times and DFS-VISIT takes place only once for each vertex in which check white vertex and make it GRAY in color by traversing all its adjacent node which take at most O(E) time and thus complexity is O(V+E). The complexity of DFS is O(V+E). Time Complexity of DIJKSTRA Algorithm EXTRACT-MIN is invoked once per vertex i.e., V times and each EXTRACT-MIN operation takes O(V) time since we have to search through the entire array. Each edge in the adjacency list Adj[v] is examined exactly once during the course of the algorithm. Since the total number of edges in all the adjacency lists is |E|, there a total of |E| iterations of this for loop. These operations are known as DECREASE-KEY operations. Other operations inside the for loop take O(1) time. Time = |V| O (V) + |E| O (1) = O (V2 + E) = O (V2) The above running time resulted from assuming that Q is implemented as an array. The time depends on different Q implementations. The efficiency of Dijkstra’s algorithm can be increased when using binary heap or Fibonacci heap. Complexity: depends on the complexity of the min-heap implementation. Level-3 Asia Pacific Institute of Information Technology Page 36 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 TASK 2: SCENARIO Graph theory has many practical applications in the real world. One such application is to determine how a network of interconnected oil stations can be optimized in order to ensure that pipe lines used for connecting the stations can be reduced to minimum possible. For this specific assignment, the second graph problem is represented hereby: N 5 4 1 1 3 3 3 4 1 5 I 4 2 1 2 4 6 F G H J K L O 2 2 Fig. 2 Graph Theory Problem (MST) 7 1 C 2 4 B 4 2 6 3 3 8 2 P Q 7 4 A D E M R The nodes in the above diagram represent the various oil stations scattered across a country, while the edges represent the oil pipelines running between them. The weight of each edge represents the distance between two stations along the edge. You have to deliver a solution for the problem mentioned above by completing the following tasks: a. Draw adjacency list and adjacency matrix of the graph given. b. Write the pseudo-codes for the Prim’s and Kruskal’s algorithm along with their explanation. c. Provide step by step solution for the Prims’s and Kruskal’s algorithm of the given graph. d. Compute the efficiencies of the above the algorithms in terms of big-Oh. Level-3 Asia Pacific Institute of Information Technology Page 37 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 TASK 2: SOLUTION a) Adjacency Matrix & Adjacency List ADJACENCY MATRIX ADJACENCY MATRIX A B C D E F G H I J K L M N O P Q R A 0 4 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 B 4 0 4 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 C 0 4 0 2 0 0 4 0 0 0 0 0 0 0 0 0 0 0 D 0 0 2 0 2 0 0 1 0 0 3 0 0 0 0 0 0 0 E 7 0 0 2 0 0 0 0 0 0 0 6 0 0 0 0 0 0 F 0 3 0 0 0 0 1 0 3 0 0 0 0 0 0 0 0 0 G 0 0 4 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 H 0 0 0 1 0 0 1 0 4 0 2 0 0 0 0 0 0 0 I 0 0 0 0 0 3 0 4 0 4 0 0 5 2 0 0 0 0 J 0 0 0 0 0 0 0 0 4 0 1 0 0 2 2 0 0 0 K 0 0 0 3 0 0 0 2 0 1 0 4 0 0 0 0 0 0 L 0 0 0 0 6 0 0 0 0 0 4 0 0 0 6 0 0 0 M 0 0 0 0 0 0 0 0 5 0 0 0 0 1 0 4 0 0 N 0 0 0 0 0 0 0 0 2 2 0 0 1 0 5 0 3 0 O 0 0 0 0 0 0 0 0 0 2 0 6 0 5 0 0 3 8 P 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 2 0 Q 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 2 0 7 R 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 7 0 Level-3 Asia Pacific Institute of Information Technology Page 38 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 ADJACENCY LIST ADJACENCY LIST A 0 B 4 E 7 B 0 A 4 C 4 F 3 C 0 B 4 D 2 G 4 D 0 C 2 E 2 H 1 K 3 E 0 A 7 D 2 L 6 F 0 B 3 G 1 I 3 G 0 C 4 F 1 H 1 H 0 D 1 G 1 I 4 K 2 I 0 F 3 H 4 J 4 M 5 N 2 J 0 I 4 K 1 N 2 O 2 K 0 D 3 H 2 J 1 L 4 L 0 E 6 K 4 O 6 M 0 I 5 N 1 P 4 K 2 N 0 I 2 J 2 M 1 O 5 Q 3 0 0 J 2 L 6 N 5 Q 3 R 8 P 0 M 4 Q 2 Q 0 N 3 O 3 P 2 R 7 R 0 O 8 Q 7 Level-3 Asia Pacific Institute of Information Technology Page 39 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 b) Pseudo-codes for the Prim’s and Kruskal’s Algorithm Pseudo code for Prim’s ALGORITHM S. No. PRIM’s Algorithm Explanation MST- PRIM(G,s) /* G = (V,E) */ V denotes the set of each vertex and E is the set of each edge of the graph. One is Graph G and the other is source vertex s. 1. For each vertex u in V For each vertex in set of vertex V 2. u.distance =  Initialize the distance of every vertex to . 3. u.predecessor = NIL Initialize the predecessor of all other vertex in the graph to be equal to NIL. 4. s.distance = 0 Initializing the distance of the source vertex to be equal to 0. 5. Q V{G} Create a minimum-priority queue Q for V according to values of distance. 6. While Q is not empty ( ) Assume queue Q is not empty it contains all the vertices of graph. Iteration of While loop is done. 7. u = EXTRACT-MIN (Q) Extract minimum vertex from queue Q. 8. For each v adjacent to u The for loop checks and updates the distance and predecessor of u of every vertex v adjacent to u. 9. if v exists in Q and weight of (u, v) < v.distance Checks the distance of the vertex v and then update it. 10. v.predecessor = u If the condition in step 9 results to be true, the predecessor of the vertex v is changed and u is updated as new predecessor. 11. v.distance = weight of (u,v) The distance of vertex v is updated and the weight of edge u-v is made the new distance of v. Level-3 Asia Pacific Institute of Information Technology Page 40 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Pseudo code for Kruskal’s ALGORITHM S. No. KRUSKAL’s Algorithm Explanation MST- KRUSKAL(G,s) /* G = (V,E) */ V denotes the set of each vertex and E is the set of each edge of the graph. One is Graph G and the other is source vertex s. 1. A is empty set(= ) Initialize the set A to the empty set 2. For each vertex v in V Randomly vertex v is chosen out of the set of all the vertices V of the graph G. 3. MAKE-SET (v) MAKE-SET (v) creates a new set whose only member is pointed to by v and for this v must be in a set. 4. Sort the edges of E into non-decreasing order by the weight The edges are being sorted into increasing order of their weights. 5. For each edge (u, v) in E, taken in non-decreasing order by weight It takes all the edges in increasing order. Edge (u, v) forms the edge of the minimum weight. 6. If FIND-SET (u) ≠ FIND-SET (v) Checks for each edge (u, v) whether the endpoint u and v belongs to the same set or tree. If they belong to the same set it means they can create cycle and cannot be added to the tree, and the edge is discarded. 7. A = A U {(u, v)} If the arbitrary vertices belong to the same tree, they get discarded. If not, then they get added to the set A. 8. UNION (u,v) The vertices of two trees are merged in the same set by UNION function. 9. return A When all the vertices come into same set A then algorithm terminate. Level-3 Asia Pacific Institute of Information Technology Page 41 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 c) Step by step solution for the Prim’s and Kruskal’s of the given graph. Step by step solution of PRIM’s ALGORITHM Step 1: GRAPH DESCRIPTION Initialize all the nodes with predecessor as NIL and distance as infinity (∞) except the source node whose distance is zero (0). Consider A as the source node and start moving one by one to rest of the nodes. The source node is made Gray in color to indicate that we are considering the adjacent vertex of A. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ Predecessor N N N N N N N N N N N N N N N N N N Level-3 Asia Pacific Institute of Information Technology Page 42 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 2: GRAPH DESCRIPTION A has been deleted from the priority queue and the adjacent vertices are updated. A will be the predecessor of each adjacent vertex. Distance of (A, B) = 4 and distance of (A, E) = 7, so now distance is minimum as (A, B) = 4 so it extracted from the minimum priority queue and after that we will move to the next node B and check its neighbours. So the vertex B is made Gray in color and color of A will be Black. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 ∞ ∞ 7 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ Predecessor N A N N A N N N N N N N N N N N N N Level-3 Asia Pacific Institute of Information Technology Page 43 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 3: GRAPH DESCRIPTION B has been deleted from the priority queue and the vertices adjacent to B have been updated with the distance given in the graph. F is identified as the next vertex having minimum priority. Hence F is changed to Gray color and B as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 4 ∞ 7 3 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ Predecessor N A B N A B N N N N N N N N N N N N Level-3 Asia Pacific Institute of Information Technology Page 44 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 4: GRAPH DESCRIPTION F has been deleted from the priority queue and the vertices adjacent to F have been updated with the distance given in the graph. G is identified as the next vertex having minimum priority. Hence G is changed to Gray color and F as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 4 ∞ 7 3 1 ∞ 3 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ Predecessor N A B N A B F N F N N N N N N N N N Level-3 Asia Pacific Institute of Information Technology Page 45 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 5: GRAPH DESCRIPTION G has been deleted from the priority queue and the vertices adjacent to G have been updated with the distance given in the graph. H is identified as the next vertex having minimum priority. Hence H is changed to Gray color and G as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 4 ∞ 7 3 1 1 3 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ Predecessor N A B N A B F G F N N N N N N N N N Level-3 Asia Pacific Institute of Information Technology Page 46 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 6: GRAPH DESCRIPTION H has been deleted from the priority queue and the vertices adjacent to H have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. D is identified as the next vertex having minimum priority. Hence D is changed to Gray color and H as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 4 1 7 3 1 1 4 ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ Predecessor N A B H A B F G H N H N N N N N N N Level-3 Asia Pacific Institute of Information Technology Page 47 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 7: GRAPH DESCRIPTION D has been deleted from the priority queue and the vertices adjacent to D have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. C is identified as the next vertex having minimum priority. Hence C is changed to Gray color and D as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 4 ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ Predecessor N A D H D B F G H N H N N N N N N N Level-3 Asia Pacific Institute of Information Technology Page 48 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 8: GRAPH DESCRIPTION C has been deleted from the priority queue but C does not have any adjacent vertex so we will check other adjacent node that comes first in queue with minimum priority. E is identified as the next vertex having minimum priority. Hence E is changed to Gray color and C as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 4 ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ ∞ Predecessor N A D H D B F G H N H N N N N N N N Level-3 Asia Pacific Institute of Information Technology Page 49 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 9: GRAPH DESCRIPTION E has been deleted from the priority queue and the vertices adjacent to E have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. K is identified as the next vertex having minimum priority. Hence K is changed to Gray color and E as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 4 ∞ 2 6 ∞ ∞ ∞ ∞ ∞ ∞ Predecessor N A D H D B F G H N H E N N N N N N Level-3 Asia Pacific Institute of Information Technology Page 50 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 10: GRAPH DESCRIPTION K has been deleted from the priority queue and the vertices adjacent to K have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. J is identified as the next vertex having minimum priority. Hence J is changed to Gray color and K as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 4 1 3 4 ∞ ∞ ∞ ∞ ∞ ∞ Predecessor N A D H D B F G H K D K N N N N N N Level-3 Asia Pacific Institute of Information Technology Page 51 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 11: GRAPH DESCRIPTION J has been deleted from the priority queue and the vertices adjacent to J have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. O is identified as the next vertex having minimum priority. Hence O is changed to Gray color and N as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 4 1 3 4 ∞ 2 2 ∞ ∞ ∞ Predecessor N A D H D B F G H K D K N J J N N N Level-3 Asia Pacific Institute of Information Technology Page 52 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 12: GRAPH DESCRIPTION O has been deleted from the priority queue and the vertices adjacent to O have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. N is identified as the next vertex having minimum priority. Hence N is changed to Gray color and O as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 4 1 3 4 ∞ 2 2 ∞ 3 8 Predecessor N A D H D B F G H K D K N J J N O O Level-3 Asia Pacific Institute of Information Technology Page 53 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 13: GRAPH DESCRIPTION N has been deleted from the priority queue and the vertices adjacent to N have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. M is identified as the next vertex having minimum priority. Hence M is changed to Gray color and N as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 2 1 3 4 1 2 2 ∞ 3 8 Predecessor N A D H D B F G N K D K N J J N O O Level-3 Asia Pacific Institute of Information Technology Page 54 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 14: GRAPH DESCRIPTION M has been deleted from the priority queue and the vertices adjacent to M have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. I is identified as the next vertex having minimum priority. Hence I is changed to Gray color and M as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 2 1 3 4 1 2 2 4 3 8 Predecessor N A D H D B F G N K D K N J J M O O Level-3 Asia Pacific Institute of Information Technology Page 55 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 15: GRAPH DESCRIPTION I has been deleted from the priority queue and the vertices adjacent to I have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. Q is identified as the next vertex having minimum priority. Hence Q is changed to Gray color and I as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q R O L 2 1 K 4 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 2 1 3 4 1 2 2 4 3 8 Predecessor N A D H D B F G N K D K N J J M O O Level-3 Asia Pacific Institute of Information Technology Page 56 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 16: GRAPH DESCRIPTION Q has been deleted from the priority queue and the vertices adjacent to Q have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. P is identified as the next vertex having minimum priority. Hence P is changed to Gray color and Q as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N Q R O L 2 1 K 4 2 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 2 1 3 4 1 2 2 2 3 7 Predecessor N A D H D B F G N K D K N J J Q O Q Level-3 Asia Pacific Institute of Information Technology Page 57 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 17: GRAPH DESCRIPTION P has been deleted from the priority queue and the vertices adjacent to P have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. L is identified as the next vertex having minimum priority. Hence L is changed to Gray color and P as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N Q R O L 2 1 K 4 2 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 2 1 3 4 1 2 2 2 3 7 Predecessor N A D H D B F G N K D K N J J Q O Q Level-3 Asia Pacific Institute of Information Technology Page 58 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 18: GRAPH DESCRIPTION L has been deleted from the priority queue and the vertices adjacent to L have been updated with the distance given in the graph. The predecessor of the respective vertex will also get updated likewise. R is identified as the next vertex having minimum priority. Hence R is changed to Gray color and L as Black in color. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N Q R O L 2 1 K 4 2 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 2 1 3 4 1 2 2 2 3 7 Predecessor N A D H D B F G N K D K N J J Q O Q Level-3 Asia Pacific Institute of Information Technology Page 59 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 19: GRAPH DESCRIPTION R has been deleted from the priority queue and it is colored as Black. As we know all the edges are deleted from the queue and the queue becomes empty. So no further traversal and finding of minimum path is complete. A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N Q R O L 2 1 K 4 2 7 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 Queue A B C D E F G H I J K L M N O P Q R Distance 0 4 2 1 2 3 1 1 2 1 3 4 1 2 2 2 3 7 Predecessor N A D H D B F G N K D K N J J Q O Q Level-3 Asia Pacific Institute of Information Technology Page 60 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 The complete minimum spanning tree is A 3 F B 4 E C D 1 G H I M P J N 2 Q R O L 1 K 7 3 1 2 2 1 2 1 4 2 2 2 Weight of minimum-spanning tree (MST) = AB + CD + DH + ED + BF + FG + GH + HK + KJ + KL + JO+ JN + NI + NM + NQ + QP +QR = 4 + 2 + 1 + 2 + 3 + 1 + 1 + 2 + 1 + 4 + 2 + 2 + 2 + 1 + 3 + 2 + 7 = 40 Level-3 Asia Pacific Institute of Information Technology Page 61 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step by step solution of KRUSKAL’s ALGORITHM A 3 3 F B 4 E 4 C D 1 G H 5 I M P 4 4 2 J N 2 Q 7 R O L 2 1 K 4 3 8 3 1 1 4 2 1 3 6 6 4 2 2 5 7 2 All the sets are = {A},{B},{C},{D},{E},{F},{G},{H},{I},{J},{K},{L},{M},{N},{O},{P},{Q},{R} Distance of the edge Edges Considered in Ascending Order 1 DH, FG, GH, JK, MN 2 CD, DE, HK, IN, JN, JO, PQ 3 BF, DK, FI, NQ, OQ 4 AB, BC, CG, HI, IJ, KL, MP 5 IM, NO 6 EL, LO 7 AE, QR 8 OR Level-3 Asia Pacific Institute of Information Technology Page 62 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Edge Considered Sets Status MST Edges Step 1: {D,H} Separate Set {A}, {B}, {C}, {D,H}, {E}, {F}, {G}, {I}, {J}, {K}, {L}, {M}, {N}, {O}, {P}, {Q}, {R} Selected {D,H} Step 2: {F,G} Separate Set {A}, {B}, {C}, {D,H}, {E}, {F,G}, {I}, {J}, {K}, {L}, {M}, {N}, {O}, {P}, {Q}, {R} Selected {D,H}, {F,G} Step 3: {G,H} Separate Set {A}, {B}, {C}, {D,F,G,H}, {E}, {I}, {J}, {K}, {L}, {M}, {N}, {O}, {P}, {Q}, {R} Selected {D,H}, {F,G}, {G,H} Step 4: {J,K} Separate Set {A}, {B}, {C}, {D,F,G,H}, {E}, {I}, {J,K}, {L}, {M}, {N}, {O}, {P}, {Q}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K} Step 5: {M,N} Separate Set {A}, {B}, {C}, {D,F,G,H}, {E}, {I}, {J,K}, {L}, {M,N}, {O}, {P}, {Q}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N} Step 6: {C,D} Separate Set {A}, {B}, {C,D,F,G,H}, {E}, {I}, {J,K}, {L}, {M,N}, {O}, {P}, {Q}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D} Step 7: {D,E} Separate Set {A}, {B}, {C,D,E,F,G,H}, {I}, {J,K}, {L}, {M,N}, {O}, {P}, {Q}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E} Step 8: {H,K} Separate Set {A}, {B}, {C,D,E,F,G,H,J,K}, {I}, {L}, {M,N}, {O}, {P}, {Q}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K} Step 9: {I,N} Same Set {A}, {B}, {C,D,E,F,G,H,J,K}, {I,M,N}, {L}, {O}, {P}, {Q}, {R} Rejected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N} Step 10: {J,N} Separate Set {A}, {B}, {C,D,E,F,G,H,I,J,K,M,N}, {L}, {O}, {P}, {Q}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N} Step 11: {J,O} Separate Set {A}, {B}, {C,D,E,F,G,H,I,J,K,M,N,O}, {L}, {P}, {Q}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O} Step 12:{P,Q} Separate Set {A}, {B}, {C,D,E,F,G,H,I,J,K,M,N,O}, {L}, {P,Q}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q} Step 13: {B,F} Separate Set {A}, {B,C,D,E,F,G,H,I,J,K,M,N,O}, {L}, {P,Q}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F} Step 14:{D,K} Same Set {A}, {B,C,D,E,F,G,H,I,J,K,M,N,O}, {L}, {P,Q}, {R} Rejected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {D,K} Level-3 Asia Pacific Institute of Information Technology Page 63 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 15: {F,I} Same Set {A}, {B,C,D,E,F,G,H,I,J,K,M,N,O}, {L}, {P,Q}, {R} Rejected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {D,K}, {F,I} Step 16:{N,Q} Separate Set {A},{B,C,D,E,F,G,H,I,J,K,M,N,O,P,Q}, {L}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {N,Q} Step 17:{O,Q} Same Set {A},{B,C,D,E,F,G,H,I,J,K,M,N,O,P,Q}, {L}, {R} Rejected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {N,Q}, {O,Q} Step 18: {A,B} Separate Set {A,B,C,D,E,F,G,H,I,J,K,M,N,O,P,Q}, {L}, {R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {N,Q}, {A,B} Step 19:{B,C} Same Set {A,B,C,D,E,F,G,H,I,J,K,M,N,O,P,Q}, {L}, {R} Rejected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {N,Q}, {A,B}, {B,C} Step 20:{C,G} Same Set {A,B,C,D,E,F,G,H,I,J,K,M,N,O,P,Q}, {L}, {R} Rejected {D,H}, {F,G}, {G,H}, {J,,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {N,Q}, {A,B}, {B,C}, {C,G} Step 21: {H,I} Same Set {A,B,C,D,E,F,G,H,I,J,K,M,N,O,P,Q}, {L}, {R} Rejected {D,H}, {F,G}, {G,H}, {J,,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {N,Q}, {A,B}, {B,C}, {C,G}, {H,I} Step 22: {I,J} Same Set {A,B,C,D,E,F,G,H,I,J,K,M,N,O,P,Q}, {L}, {R} Rejected {D,H}, {F,G}, {G,H}, {J,,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {N,Q}, {A,B}, {B,C}, {C,G}, {H,I}, {I,J} Step 23: {K,L} Separate Set {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q}, {R} Selected {D,H},{F,G},{G,H},{J,K},{M,N}, {C,D}, {D,E},{H,K},{I,N},{J,N}, {J,O},{P,Q}, {B,F}, {N,Q},{A,B},{K,L} Step 24:{M,P} Same Set {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q}, {R} Rejected {D,H},{F,G},{G,H},{J,K},{M,N}, {C,D}, {D,E}, {H,K},{I,N},{J,N}, {J,O},{P,Q}, {B,F}, {N,Q},{A,B}, {K,L}, {M,P} Level-3 Asia Pacific Institute of Information Technology Page 64 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 25: {I,M} Same Set {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q}, {R} Rejected {D,H},{F,G},{G,H},{J,K},{M,N}, {C,D},{D,E},{H,K},{I,N},{J,N}, {J,O},{P,Q},{B,F},{N,Q},{A,B}, {K,L}, {M,P},{I,M} Step 26:{N,O} Same Set {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q}, {R} Rejected {D,H},{F,G},{G,H},{J,K},{M,N}, {C,D},{D,E},{H,K},{I,N},{J,N}, {J,O},{P,Q},{B,F},{N,Q},{A,B}, {K,L}, {M,P},{I,M},{N,O} Step 27:{E,L} Same Set {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q}, {R} Rejected {D,H},{F,G},{G,H},{J,K},{M,N}, {C,D},{D,E},{H,K},{I,N},{J,N}, {J,O},{P,Q},{B,F},{N,Q},{A,B}, {K,L},{M,P},{I,M},{N,O},{E,L} Step 28:{L,O} Same Set {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q}, {R} Rejected {D,H},{F,G},{G,H},{J,K},{M,N}, {C,D},{D,E},{H,K},{I,N},{J,N}, {J,O},{P,Q},{B,F},{N,Q},{A,B}, {K,L},{M,P},{I,M},{N,O},{E,L}, {L,O} Step 29:{A,E} Same Set {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q}, {R} Rejected {D,H},{F,G},{G,H},{J,K},{M,N}, {C,D},{D,E},{H,K},{I,N},{J,N}, {J,O},{P,Q},{B,F},{N,Q},{A,B}, {K,L},{M,P},{I,M},{N,O},{E,L}, {L,O},{A,E} Step 30:{Q,R} Separate Set {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q, R} Selected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {N,Q}, {A,B}, {K,L}, {Q,R} Step 31:{O,R} Same Set {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q, R} Rejected {D,H}, {F,G}, {G,H}, {J,K}, {M,N}, {C,D}, {D,E}, {H,K}, {I,N}, {J,N}, {J,O}, {P,Q}, {B,F}, {N,Q}, {A,B}, {K,L},{Q,R},{O,R} Level-3 Asia Pacific Institute of Information Technology Page 65 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Minimum Spanning tree = DH+ HG+ GF+ KJ+ NM+ ED+ DC+ OJ + NI+ JN+ HK+ QP+ BF+ NQ+ AB+ LK+ QR =1+ 1+ 1+ 1+ 1+ 2+ 2+ 2+ 2+ 2+ 2+ 2+ 3+ 3+ 4+ 4+ 7 = 40 3 F B D C 1 G H I M P J N 2 Q R O L 2 1 K 7 3 1 2 1 2 1 4 2 2 E Level-3 Asia Pacific Institute of Information Technology Page 66 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 d) Efficiency of the Prim’s and Kruskal’s algorithms in terms of big-oh. Note: The time complexity of Prim’s & Kruskal’s algorithm is explained in the pseudo code in the above Task 2(b). Time Complexity of Kruskal’s Algorithm: O(n log n) or O(n log V) Justification:  Sorting of edges: O(n log n) time  Affter sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take at most: O(log V) time.  So overall complexity = O(n log n + n log V) time.  Since, the value of E can be = V^2. So O(log V) are O(log n) same. Therefore, overall time complexity for the Kruskal’s Algorithm is = O(n log n) or O(n log V). TIME COMPLEXITY OF PRIM’S ALGORITHM:  Step 1 to 3 will be having the equal running time – O(V). Run time will be maximum depending on the total number of vertices.  Run time for step 4 and 5 = O(1). These statements will eb executed only once.  Run time for step 6 and 7 = O(V log V). The loop in step 6 is iterating V times, hence the combined runtime = O(V log V).  The number of edges will affect the runtime of step 9. We can compare maximum up to E times. Thus, the complexity of this step will be O(E). The further steps have dependency over the edges E, and since they are still present in the loop, their complexity will be O(E log V). Total run time = O(V) + O(1) + O(V log V) + O(E) + O(E log V) O(E log V) is the maximum complexity involved in this algorithm and hence, this will affect the runtime to the greater extent as compared to the complexities of the other steps. So, total running time complexity of Prim’s Algorithm = O(E log V). Level-3 Asia Pacific Institute of Information Technology Page 67 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 TIME COMPLEXITY OF KRUSKAL’S ALGORITHM:  The first step will have a runtime of O(1) and this will remain constant as it do not depend on any other factor.  Step 2 and 3 have their runtime = O(V). This loop depends on V.  Step 3 and 4 are storing the edges and they will have equal runtime = O(E log E)  Step 6, step 7 and step 8 depend on the number of vertices V and are running inside the loop. Thus, their run time = O(E log V)  Step 9 will have complexity = O(1) as it is running only once. Sum of total running times = O(1) + O(V) + O(E log E) + O(E log V) + O(1). O(E log V) is the maximum running time that affects the running time of the Kruskal’s Algorithm. Thus, the total running time for Kruskal’s algorithm = O(E log V). Level-3 Asia Pacific Institute of Information Technology Page 68 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 TASK 3: SCENARIO Given the following elements: 12, 9, 3, 4, 8, 2, 11, 5 apply the Heap Sort algorithm to sort them. Show all phases during the sort. You have to deliver a solution for the problem mentioned above by completing the following tasks a. Provide all phases of insert operations when building a heap out of these elements. b. Provide all phases of deleteMin operations when removing the minimal elements and storing them into the sorted array c. Discuss the complexity of the Heapsort in terms of the Big-Oh notation. TASK 3: SOLUTION a) All phases of insert operations Heap Sort = 12, 9, 3, 4, 8, 2, 11, 5 INDEX NO. 1 2 3 4 5 6 7 8 ELEMENTS 12 9 3 4 8 2 11 5 12 1 9 3 2 4 3 5 6 7 4 8 2 11 5 5 Total number of node = n/2 + 1 = 8/2 + 1 = 4 + 1 = 5 Level-3 Asia Pacific Institute of Information Technology Page 69 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Now apply Max-Heap, Step 1: Step 2: 2 3 3 1 Now node number 4 will exchange to the node number 8 4 5 6 7 4 8 2 11 1 12 12 9 2 3 9 3 5 8 4 5 6 7 5 8 2 11 4 8 Here node number 3 is exchanged with node 7 Level-3 Asia Pacific Institute of Information Technology Page 70 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 3: 8 Step 4: 1 12 2 3 9 11 4 5 6 7 5 8 2 3 4 Here node 3 has exchanged with node 7 Now the elements are: ELEMENTS 12 9 11 5 8 2 3 4 b) All phases of deleteMin operations Now apply Heap-sort on the elements given in the above table: 1 12 2 3 9 11 4 5 6 7 5 8 2 3 4 8 Here node number 1 has exchanged with last node number 8 Level-3 Asia Pacific Institute of Information Technology Page 71 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 5: 4 5 6 7 According to the algorithm, here delete the last node number 8 elements. 12 11 22 8 The elements are: ELEMENTS 4 2 3 9 11 1 5 8 2 3 4 9 11 5 8 2 3 12 Step 6: Now apply Heapify, 1 4 2 3 9 11 4 5 6 7 5 8 2 3 Here node number 1 exchange with the node number 3 Level-3 Asia Pacific Institute of Information Technology Page 72 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 7: 2 3 4 1 4 5 6 7 5 8 2 3 The elements are: 11 9 Here node number 1 will be exchanged with the node number 3 ELEMENTS 11 9 4 5 8 2 3 Step 8: 1 11 2 3 9 4 Apply algorithm and node 1 is replaced with the last node 7 4 5 6 7 5 8 2 3 Level-3 Asia Pacific Institute of Information Technology Page 73 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 9: 2 3 4 1 4 5 6 7 5 8 2 11 The elements are: ELEMENTS 3 9 Here after exchanging the elements delete the node number 7 element 3 9 4 5 8 2 11 12 Apply Heapify, 1 3 Here after exchange elements the node number 1 with node 2 element 2 3 9 4 5 6 5 8 2 4 Level-3 Asia Pacific Institute of Information Technology Page 74 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 10: Step 11: Here exchange the element of node 2 with node 5 Here exchange the element of node 3 with node 5 The Elements are: ELEMENTS 1 2 3 4 5 6 5 8 2 1 9 9 3 2 3 8 4 5 6 5 3 2 4 9 8 4 5 3 2 4 Level-3 Asia Pacific Institute of Information Technology Page 75 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 12: 4 5 6 Step 13: 1 2 3 5 3 2 1 9 8 4 2 3 4 5 6 5 3 9 The elements are: ELEMENTS 2 8 4 Apply algorithm and node number 1 exchange with last node element 6 Here deleting the last node element 2 8 4 5 3 9 11 12 Level-3 Asia Pacific Institute of Information Technology Page 76 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 14: Now apply Heapify, Here node number 1 exchange with the node number 2 4 5 The elements are: 2 3 5 3 Elements 1 2 4 2 8 4 5 3 Step 15: 1 8 2 3 2 8 4 5 5 3 4 Here node number 2 exchange with the node number 4 Level-3 Asia Pacific Institute of Information Technology Page 77 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 16: Here node number 2 exchange with the node number 4 Step 17: 1 8 2 3 5 4 5 2 3 2 3 4 5 2 8 The elements are: Elements 1 3 5 4 4 Now apply algorithm and node 1 element exchange with last node element 5 3 5 4 2 8 9 11 12 Level-3 Asia Pacific Institute of Information Technology Page 78 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 18: Apply Heapify, Here exchange node no 1 element with node number 2 element The elements are: 2 4 Elements 1 3 2 3 5 4 3 5 4 2 1 5 2 3 3 2 4 4 Level-3 Asia Pacific Institute of Information Technology Page 79 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 19: Here Apply algorithm and exchange node no 1 element with node no 4 and deleting the node no 4 The elements are: Elements 1 2 2 3 3 5 4 4 2 3 4 5 8 9 11 12 Step 20: Now apply Heapify, The elements are: 1 2 3 3 4 Elements 2 2 3 4 Here exchanging the node no 1 with the node number 3 Level-3 Asia Pacific Institute of Information Technology Page 80 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 Step 21: Step 22: The Elements are: Elements 1 4 2 3 3 2 1 2 2 3 3 4 Apply Algorithm exchange the node 1 element with last node element 3 Here deleting the last node of element 2 3 4 5 8 9 11 12 Step 23: Now Apply Heapify, 1 2 3 2 Here exchange the node no 1 element with the node no 2 element. Level-3 Asia Pacific Institute of Information Technology Page 81 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 The elements are: Elements 2 3 Step 24: Step 25: Step 26: 1 2 2 3 1 2 1 3 2 2 3 2 Here exchange the node no 1 element with the node no 2 element. Here apply algorithm and node no 1 exchange with node no 2 Now deleting the last element of node number 2 Level-3 Asia Pacific Institute of Information Technology Page 82 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 The elements are: Elements 2 3 4 5 8 9 11 12 Step 27: Step 28: 1 2 1 2 Now apply the algorithm Now deleting the last element of node number 1 Now the final elements in the sorted form are: Elements 2 3 4 5 8 9 11 12 Level-3 Asia Pacific Institute of Information Technology Page 83 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 c) Complexity of Heap Sort in terms of Big-oh Notation MAX-HEAPIFY(A, i, n) 1. l ← LEFT(i) 2. r ← RIGHT(i) 3. if l ≤ n and A[l] > A[i] 4. then largest ←l 5. else largest ←i 6. if r ≤ n and A[r] > A[largest] 7. then largest ←r 8. if largest  i 9. then exchange A[i] ↔ A[largest] 10. MAX-HEAPIFY(A, largest, n) TASK DESCRIPTION ih n n T  i h i   0 ( ) Cost of HEAPIFY at level i  number of nodes at that level h i h i   i 0 2 Replace the values of ni and hi computed before h h  i  h  i h i 2 2 0   Multiply by 2h both at the nominator and denominator and 1 write 2i as 2  i h h k    k k 0 2 2 Change variables: k = h - i   k 2 k  0  k n The sum above is smaller than the sum of all elements to  and h = lgn The sum above is smaller than 2 Running time of BUILD-MAX-HEAP: T(n) = O(n)  O(n) Level-3 Asia Pacific Institute of Information Technology Page 84 of 85

Algorithmics (CE00333-3) Individual Assignment PT1181106 REFERENCES Websites: 1. Breadth First Search PersonalKent, (2010). Breadth First Search – PersonalKent. [online] Available at: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearc h.htm [Accessed 21 Oct. 2014] 2. Depth First Search Brpreiss, (2012). Depth First Traversal – Brpreiss, [online] Available at: http://www.brpreiss.com/books/opus4/html/page551.html Depth First Tranversal by Bruno R. Preiss, P.Eng. [Accessed 23 Oct. 2014] 3. Dijkstra Algorithm Ryan Mark (2004) Dijkstra’s Algorithm [Online]. Available from : http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/DijkstraAlgo.html [Accessed From: 28 Oct. 2014] 4. Time Complexity of Algorithm GeeksforGeeks, (2012). Greedy Algorithms | Set 2 (Kruskal’s Minimum Spanning Tree Algorithm) - GeeksforGeeks. [online] Available at: http://www.geeksforgeeks.org/greedy-algorithms- set-2-kruskals-minimum-spanning-tree-mst/ [Accessed 30 Oct. 2014]. 5. Prim’s Algorithm Papaioannou Panagiotis (1992) Prims Algorithm [Online] Available From: http://students.ceid.upatras.gr/~papagel/project/prim.htm [Accessed 1 Nov. 2014] 6. Krusk al’s Algorithm Kruskal J.B.(1989) Kruskal’s Algorithm [Online] Available from: http://lcm.csa.iisc.ernet.in/dsa/node184.html [Accessed 3 Nov. 2014] Books: 7. Data Structure and algorithm analysis Weiss, M. (1995). Data structures and algorithm analysis. Redwood City, Calif.: Benjamin/Cummings Pub. Co. 8. Fundamentals of computer algorithm Satraj sahni (2008). Fundamental of computer algorithm. 2nd ed. New delhi: Universities Press India pvt. Level-3 Asia Pacific Institute of Information Technology Page 85 of 85

Algorithms

More Related Content

What's hot

Viewers also liked

Similar to Algorithms

Recently uploaded

Algorithms