Algorithms explained

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 1 Contents TASK 1: SCENARIO..................................................................................................................................2 SOLUTION: TASK 1...................................................................................................................................3 a) Adjacency list & Adjacency Matrix..................................................................................................3 ADJACENCY MATRIX......................................................................................................................3 ADJACENCY LIST .............................................................................................................................4 b) Pseudo code of Prim’s Algorithm & Kruskal’s Algorithm...................................................................5 PRIM’S ALGORITHM-Pseudo code...................................................................................................5 KRUSKAL’S ALGORITHM-Pseudo code..........................................................................................7 c) EXECUTION OF PRIM’S & KRUSKAL’S ALGORITHM...............................................................9 Execution step for Prim’s Algorithm........................................................................................................9 EXECUTION OF KRUSKAL’S ALGORITHM ...................................................................................15 d) EFFICIENCY OF KRUSKAL’S & PRIM’S ALGORITHM IN TERM OF BIG-OH & BIG- THETA ...................................................................................................................................................20 TASK 2: INSERTION & DELETION IN B-TREE...................................................................................22 SOLUTION: TASK 2.................................................................................................................................23 a) INSERTION OF ELEMENTS IN B-TREE. ..................................................................................23 PSEUDOCODE FOR INSERTION ...................................................................................................26 b) DELETION OF ELEMENTS:........................................................................................................28 PSEUDOCODE FOR DELETION.....................................................................................................32 TASK 3: COMPLEXITY CLASSES .........................................................................................................35 SOLUTION: TASK 3.................................................................................................................................35 a) CONCEPT OF COMPLEXITY CLASS ........................................................................................35 b) EXAMPLES OF PROBLEMS FOR EACH COMPLEXITY CLASS...........................................37 REFERENCES ...........................................................................................................................................40

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 2 TASK 1: SCENARIO Imagine that you work for the Cable Company and your task is to provide cable lines to a village with 10 houses, each labeled H1 through H10. Specifically this involves running a single cable that connects each home. That is, the cable must run through houses H1, H2, and so forth, up through H10. Due to geographic obstacles—hills, trees, rivers, and so on—it is not feasible to necessarily run the cable from one house to another. Figure 1 show this problem depicted as a graph. Each node is a house, and the edges are the means by which one house can be wired up to another. The weights of the edges dictate the distance between the houses. Your task is to wire up all ten houses using the least amount of cable possible. Figure 1: Graphical representation of hooking up of 10-houses in village with cable. 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 to find the Minimum Spanning Tree (MST) of the given graph with Prim’s and Kruskal’s algorithmic approaches. d. Compare the efficiencies of both the algorithms in terms of big-Oh and big-Theta

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 3 SOLUTION: TASK 1 a) Adjacency list & Adjacency Matrix ADJACENCY MATRIX H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H1 0 20 45       45 H2 20 0 30  25   100  30 H3 45 20 0 45       H4   45 0 75 40     H5  25  75 0 75  90   H6    40 75 0   40  H7      80 0 15 0  H8  100   90  15 0 45 50 H9      40  45 0  H10 45 30      50  0

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 4 ADJACENCY LIST H1 0 H2 20 H3 45 H10 45 H2 0 H1 20 H3 30 H5 25 H8 100 H5 0 H2 25 H4 75 H6 75 H8 90 H6 0 H4 40 H5 75 H7 80 H9 40 H7 0 H6 80 H9 0 H6 40 H8 45 H10 0 H1 45 H2 30 H8 50 H3 0 H1 45 H2 30 H4 45 H4 0 H3 45 H5 75 H6 40 H10 30 H8 15 H8 0 H2 100 H5 90 H7 15 H9 45 H10 50

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 5 b) Pseudo code of Prim’s Algorithm & Kruskal’s Algorithm PRIM’S ALGORITHM-Pseudo code Input: A connected undirected graph G = (V,E) with edge weights r Output: A minimum spanning tree. MST-PRIM(G,r) /* G = (V,E) */ START For each u in V u.dist =  u.pred = NIL r.dist = 0 Create a min-priority queue Q for V according to values of dist While Q is not empty u = EXTRACT-MIN(Q) For each v adjacent to u if v exists in Q and weight of (u,v) < v.dist v.pred = u v.dist = weight of (u,v) STOP Step by step Explanation of the algorithm: MST_PRIM (G,r)/*G=(V,E)*/ The graph’s definition is given by G=(V,E) where V denotes the set of each vertex of the graph and E is the set of each edge of the graph. The MST_PRIM algorithm is being applied which takes two arguments. One is the graph G and the other is the root vertex, r. START STEP 1 For each u in V We take any random vertex u from the set of vertices V of the graph. This is done to apply initialization on each vertex. STEP 2 u.dist = ∞ For each vertex u, define u.dist as distance, ie. u.dist is the weight of the edge connecting u and its closest neighbor in the growing tree. This closest neighbor is defined as u.pred. We initialize the distance of every vertex of the graph to ∞. STEP 3 u.pred=NIL The closest neighbor of vertex u is referred to as u.pred. we assume this predecessor vertex of all other vertex in the graph to be equal to NIL. END For

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 6 STEP 4 r.dist = 0 Initializing the distance of the root node to be equal to zero(0). STEP 5 Create a min-priority queue Q for V according to values of dist Based on the u.dist (distance of vertices from the source node), all vertices that are not in the tree reside in a minimum priority queue Q. Thus, in this step we are creating a minimum priority queue Q. Note: STEP 1 TO 5 are used to set the key of each vertex to ∞ (except for the root r, whose key is set to 0 so that it will be the first vertex processed), set the parent of each vertex to NIL and initialize the minimum priority queue Q to contain all the vertices. STEP 6 While Q is not empty Iteration of While loop is done STEP 7 u = EXTRACT_MIN(Q) EXTRACT_MIN(Q) algorithm is called which identifies a vertex having a light weight and thus belonging to the minimum priority queue Q. This vertex is removed from Q and it is then assigned to the random vertex u of the min-priority queue Q. STEP 8 For each v adjacent to u The For loop checks and updates the u.dist and u.pred fields of every vertex v adjacent to u but not in the tree. STEP 9 If v exists in Q and weight of (u,v) < u.dist This step checks the membership of each vertex in Q by keeping a bit of each vertex and also confirms if the weight of the edge u-v is less that the distance of u from its current predecessor. It then updates the bit when the vertex is removed from Q in the following steps. STEP 10 v.pred = u If the condition checked in STEP 9 results to be true, the predecessor of the vertex v is changed and u is made the new predecessor. STEP 11 v.dist = weight of (u,v) The distance of v is updated and the weight of edge u-v is made the new distance of v. END If END For END While STOP

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 7 KRUSKAL’S ALGORITHM-Pseudo code MST-KRUSKAL(G) /* G = (V,E) */ A =  For each vertex v in V MAKE-SET(v) Sort the edges of E into nondecreasing order by the weight For each edge (u,v) in E, taken in nondecreasing order by weight if FIND-SET(u)  FIND-SET(v) A = A U {(u,v)} UNION(u,v) return A Step by step explanation of the algorithm: MST_KRUSKAL (G) The graph’s definition is given by G=(V,E) where V denotes the set of each vertex of the graph and E is the set of each edge of the graph. The MST_KRUSKAL algorithm takes only one argument, i.e., the graph G itself. START STEP 1 A =  An empty set A is considered which will later contain all the vertices forming the MST. STEP 2 For each vertex v in V Randomly a vertex v is chosen out of the set of all the vertices V of the graph G to represent rest of the vertices of the graph by undergoing the iteration steps of the FOR loop. STEP 3 MAKE-SET(v) Algorithm MAKE_SET(v) is used to make a separate set of each vertices by executing the For loop for each vertex of the graph. STEP 4 Sort the edges of E into non-decreasing order by the weight The edges are being sorted into increasing order of their weights. Note: In STEP 5 TO 8, the For loop checks for each edge (u,v), whether the endpoints u and v belong to the same tree. If they do, then the edge (u,v) cannot be added to the forest without creating a cycle, and the edge is discarded. Otherwise, it is confirmed that the vertices belong to different trees. In this case, the edge (u,v) is added to A (STEP 7) and the vertices in the two trees are merged (STEP 8). STEP 5 For each edge (u,v) in E, taken in non-decreasing order by weight The smallest edge is selected from the set of all edges E of the graph. The vertex u and vertex v are two arbitrary vertices of G. Edge (u,v) forms the edge of the minimum weight.

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 8 STEP 6 if FIND_SET(u)  FIND_SET(v) The algorithm FIND_SET() takes one argument as a vertex of the graph and returns the name of the set containing the given elements. In this step, we check whether both the arbitrary vertices belong to the same tree or different trees. STEP 7 A = A U {(u,v)} If the arbitrary vertices belong to the same tree, they get discarded. It not, they get added to the set A. STEP 8 UNION(u,v) UNION() algorithm is called so that it would take two set of vertices u and v namely, as inputs and execute a Union operation over them. END IF END FOR STEP 9 return A This step returns a set A which contains all those edges which will be forming a minimum spanning tree.

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 9 c)EXECUTION OF PRIM’S & KRUSKAL’S ALGORITHM Execution step for Prim’s Algorithm STEP 1 It has been mentioned in the scenario that the cable company wants the cable to run from house H1, then to H2 and up to H10. So, it will be better to start the wiring of cable from house H1. Vertices H1 H2 H3 H4 H5 H6 H7 H8 H8 H10 distance 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ predecessor NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL DESCRIPTION GRAPH This step initializes the predecessor of every vertex as NIL and their distance as ∞. The vertices are also being placed in a minimum priority queue from where minimum weighted vertices will be extracted from time to time. The root vertex is made brown to indicate that we are considering the adjacent vertex of H1. H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP 2 In this step, vertex H1 will be deleted from the priority queue and all the vertices adjacent to the root vertex will be considered. The distance of the adjacent vertices will get modified to the distance from the root and the parent will be modified from NIL to H1. Vertices H2 H3 H4 H5 H6 H7 H8 H8 H10 distance 20 45 ∞ ∞ ∞ ∞ ∞ ∞ 45 predecessor H1 H1 NIL NIL NIL NIL NIL NIL H1

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 10 DESCRIPTION GRAPH H1 has been deleted from the priority queue and the status of the adjacent vertices is updated. H1 has been made the predecessor of each adjacent vertex and their distance is modified with the distance from H1. Since the distance of H2 from H1 is the minimum as compared to the other adjacent vertices, it has been made brown in color in the graph alongside and the color of H1 is made Black. H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP 3 Vertices H3 H4 H5 H6 H7 H8 H9 H10 Distance 30 ∞ 25 ∞ ∞ 100 ∞ 30 Predecessor H2 NIL H2 NIL NIL H2 NIL H2 DESCRIPTION GRAPH H2 has been deleted from the priority queue and the status of the vertices adjacent to H2 has been updated with the values available in the graph given. H5 is identified as the next vertex having the minimum priority. Hence, H5 has been made brown in color and the color of the vertex H1 and H2 are made black. H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP 4 Vertices H3 H4 H6 H7 H8 H9 H10 Distance 30 75 75 ∞ 90 ∞ 30 Predecessor H2 H5 H5 NIL H5 NIL H2

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 11 DESCRIPTION GRAPH H5 has been deleted after considering all its adjacent vertices. The status of distance and predecessor of the vertices adjacent to H5 has been updated accordingly. We may take any of H3 and H10 as minimum priority vertex because both vertexes have same priority value. But we will be choosing H3 and will make it brown. H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP 5: The adjacent vertices from H3 are H1, H2 and H4. Since H1 and H2 are not present in the priority queue so we have considered only H4. Vertices H4 H6 H7 H8 H9 H10 distance 45 75 ∞ 90 ∞ 30 predecessor H3 H5 NIL H5 NIL H2 DESCRIPTION GRAPH After deleting H3, its color is changed to black and the newly considered vertex of the minimum priority queue will be made brown in color. In next step, H10 will be considered as the minimum weighted vertex in the priority queue. This vertex will be deleted at a later stage. H10 will be added to the MST. H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP 6: Vertices H4 H6 H7 H8 H9 distance 45 75 ∞ 50 ∞ predecessor H3 H5 NIL H10 NIL DESCRIPTION GRAPH

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 12 Vertex H10 is deleted and all its adjacent vertices i.e., H1, H2 and H8 are to be considered. We have to consider H8 only as H1 & H2 are not present in the priority queue. The previous distance of H8 from H5 has been updated from 90 to 50 considering H10 as its predecessor. H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP 7: In this step, H4 will be considered as the minimum priority vertex and after considering all its adjacent vertices, this vertex will be deleted. Vertices H6 H7 H8 H9 Distance 40 ∞ 50 ∞ Predecessor H4 NIL H10 NIL DESCRIPTION GRAPH Vertex H4 has been deleted. The adjacent vertices from H4 are H3, H5 and H6. Since H3 and H5 are not present in the priority queue, only H6 will be considered. The previous distances of the vertex H6 was 75 from H5 which have updated to 40 considering H4 as its predecessor. H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP 8: In this step, H6 will be considered as the minimum priority vertex and after considering all its adjacent vertices, this vertex will get deleted. Vertices H7 H8 H9 Distance 80 50 40 Predecessor H6 H10 H6

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 13 DESCRIPTION GRAPH Vertex H6 has been deleted. Its adjacent vertices are H4, H5, H7 and H9. Since H4 and H5 are not present in the priority queue so we have considered only H7 and H9. H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP 9 In this step, H9 will be taken as the minimum priority vertex and its adjacent vertices will be taken into consideration. Vertices H7 H8 distance 15 45 predecessor H8 H9 DESCRIPTION GRAPH H9 has been deleted from the minimum priority queue and it has been made black in color. The adjacent vertices of H9 are brought into consideration. The adjacent vertices of H9 are H6 and H8. Since, H6 is not in the minimum priority anymore, we consider only vertex H8. Hence, we make the color of vertex H8 as brown. H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP 10 We make H8 as the minimum priority vertex. The adjacent vertex of H8 is H7, H9, H10. But since H9 and H10 are not in the minimum priority queue, we consider only H7 as the adjacent vertex. H8 gets deleted and H7 is made brown. These results in the final MST we were looking for. Finally, we get our MST as:

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 14 H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 15 EXECUTION OF KRUSKAL’S ALGORITHM STEP 1: Make individual sets of all the vertices given. {H1}, {H2}, {H3},{H4},{H5},{H6},{H7},{H8},H9},{H10} STEP 2: Make a set of edges and arrange them in a priority queue, starting from the minimum weighted edge to the maximum weighted edge. (H8, H7), ( H1, H2), (H2, H5), (H2,H10), (H2,H3), (H4,H10), (H6,H9), (H1,H10), (H3,H4), (H8,H9), (H8,H10), (H5,H4), (H5,H6), (H6,H7), (H5,H8), (H8,H2) SET S WEIGHT GRAPH (H8, H7) 15 ( H1, H2) 20 (H2, H5) 25 (H2,H10) 30(H2,H3) (H4,H6) 40 (H6,H9) 45 (H1,H10) (H3,H4) (H8,H9) (H8,H10) 50 (H5,H4) 75 (H5,H6) (H6,H7) 80 (H5,H8) 90 (H8,H2) 100

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 16 STEP: 1 DESCRIPTION GRAPH Choose an edge of minimum weight from the above set S that is edge (H8,H7). Add it to Minimum spanning tree set MST: {(H8,H7)}. S: {H8,H7} H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP: 2 DESCRIPTION GRAPH Choose another edge of minimum weight from the above set S that is edge (H1,H2). Thus edge (H1,H2) is not forming a cycle with the edges already included in MST set so add it to Minimum spanning tree set. MST: {(H8,H7) (H1,H2)}. S: {H1,H2,H8,H7} H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP: 3 DESCRIPTION GRAPH Choose another edge of minimum weight from the above set S that is edge (H2,H5). Thus edge (H2,H5) is not forming a cycle with the edges already included in MST set so add it to Minimum spanning tree set. MST: {(H8, H7) (H1,H2),(H2,H5)}. S: {H1,H2,H5,H8,H7} H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP: 4 DESCRIPTION GRAPH

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 17 Choose another edge of minimum weight from the above set S that is edge (H2,H10). Thus edge (H2,H10) is not forming a cycle with the edges already included in MST set so add it to Minimum spanning tree set. MST:{(H8, H7) (H1,H2),(H2,H5),(H2,H10)}. S: {H1,H2,H5,H8,H7,H10} H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP: 5 DESCRIPTION GRAPH Choose another edge of minimum weight from the above set S that is edge (H2,H3). Thus edge (H2,H3) is not forming a cycle with the edges already included in MST set so add it to Minimum spanning tree set. MST:{(H8,H7),(H1,H2),(H2,H5),(H2,H10), (H2,H3)}. S: {H1,H2,H3,H5,H7,H8,H10} H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP: 6 DESCRIPTION GRAPH Choose another edge of minimum weight from the above set S that is edge (H4,H6). Thus edge (H4,H6) is not forming a cycle with the edges already included in MST set so add it to Minimum spanning tree set. MST:{(H8,H7),(H1,H2),(H2,H5),(H2,H10) , (H2,H3),(H4,H6)}. S: {H1,H2,H3,H4,H5,H6,H7,H8,H10} H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 18 STEP: 7 DESCRIPTION GRAPH Choose another edge of minimum weight from the above set S that is edge (H6,H9). Thus edge (H6,H9) is not forming a cycle with the edges already included in MST set so add it to Minimum spanning tree set. MST:{(H8,H7),(H1,H2),(H2,H5),(H2,H10), (H2,H3),(H4,H6), (H6,H9)}. S: {H1,H2,H3,H4,H5,H6 H7,H8,H9,H10} H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP: 8 DESCRIPTION GRAPH Choose another edge of minimum weight from the above set S that is edge (H1,H10). But this edge is forming a cycle so we leave it take other edge that is (H3,H4). Thus edge (H3,H4) is not forming a cycle with the edges already included in MST set so add it to Minimum spanning tree set. MST:{(H8,H7),(H1,H2),(H2,H5),(H2,H10 ), (H2,H3),(H4,H6), (H6,H9), (H3,H4)}. S: {H1,H2,H3,H4,H5,H6 H7,H8,H9,H10} H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 STEP: 9 DESCRIPTION GRAPH Choose another edge of minimum weight from the above set S that is edge (H8, H9). Thus edge (H8, H9) is not forming a cycle with the edges already included in MST set so add it to Minimum spanning tree set. MST:{(H8,H7),(H1,H2),(H2,H5),(H2,H10), (H2,H3),(H4,H6), (H6,H9),(H8,H9)}. S: {H1,H2,H3,H4,H5,H6 H7,H8,H9,H10} H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 19 STEP: 10 DESCRIPTION GRAPH The rest of the vertices (H5,H4),(H5,H6),(H6,H7),(H5,H8),(H8,H 2) cannot be added to the Minimum Spanning tree because they are forming a cycle with their adjacent edges. So, these edges automatically get rejected. Now, we are left with the following set of MST: MST:{(H8,H7),(H1,H2),(H2,H5),(H2,H1 0), (H2,H3),(H4,H6), (H6,H9),(H8,H9)}. S:{H1,H2,H3,H4,H5,H6 H7,H8,H9,H10} H1 H3 H4 H6 H5 H2 H9 H7 H8 H10 45 45 45 30 20 25 75 75 40 40 80 45 90 50 15 30 100 EDGE WEIGHT SET RESULT (H8, H7) 15 {H1},{H2},{H3},{H4},{H5},{H6},{H7,H8},H9},{H10} Accepted ( H1, H2) 20 {H1,H2},{H3},{H4},{H5},{H6},{H7,H8},H9},{H10} Accepted (H2, H5) 25 {H1,H2,H5},{H3},{H4},{H6},{H7,H8},H9},{H10} Accepted (H2,H10) 30 {H1,H2,H5,H10},{H3},{H4},{H6},{H7,H8},{H9} Accepted (H2,H3) 30 {H1,H2,H3,H5,H10},{H4},{H6},{H7,H8},{H9} Accepted (H4,H6) 40 {H1,H2,H3,H5,H10},{H4,H6},{H7,H8},{H9} Accepted (H6,H9) 40 {H1,H2,H3,H5,H10},{H4,H6,H9},{H7,H8} Accepted (H1,H10) 45 {H1,H2,H3,H5,H10},{H4,H6,H9},{H7,H8} Rejected (H3,H4) 45 {H1,H2,H3, H4,H5,H6,H9,H10},{H7,H8} Accepted (H8,H9) 45 {H1,H2,H3, H4,H5,H6, H7,H8,H9,H10} Accepted (H8,H10) 50 {H1,H2,H3, H4,H5,H6, H7,H8,H9,H10} Rejected (H5,H4) 75 {H1,H2,H3, H4,H5,H6, H7,H8,H9,H10} Rejected (H5,H6) 75 {H1,H2,H3, H4,H5,H6, H7,H8,H9,H10} Rejected (H6,H7) 80 {H1,H2,H3, H4,H5,H6, H7,H8,H9,H10} Rejected (H5,H8) 90 {H1,H2,H3, H4,H5,H6, H7,H8,H9,H10} Rejected (H8,H2) 100 {H1,H2,H3, H4,H5,H6, H7,H8,H9,H10} Rejected Total weight of the edges of MST: 15+20+25+30+30+40+40+45+45=290

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 20 d) EFFICIENCY OF KRUSKAL’S & PRIM’S ALGORITHM IN TERM OF BIG-OH & BIG-THETA Note: This time complexity of Prim’s & Kruskal’s algorithm is calculated keeping in consideration the pseudo code of Prim’s & Kruskal’s algorithm explained above in Task 1(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.  After 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 be 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 o the other steps. So, total running time complexity of Prim’s Algorithm = O (E lg V). 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 ad 3 have their runtime = O(V). This loop depends on V.  Step 3 & 4 are storing the edges and they will have equal runtime = O (E log E).

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 21  Step6, step7 and step 8 depends on the number of vertices V & are running inside a loop. Thus, their run time = O(E log V).  Step 9 will have complexity =O(1) as it is running only once. Sum of the 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, Total running time for Kruskal’s algorithm = O(E log V).

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 22 TASK 2: INSERTION & DELETION IN B- TREE Starting with the B-tree of order 5 shown in Figure 2, perform the operations as indicated along with proper explanation. Figure 2: B-Tree of order 5 a. Write a Pseudo-code to insert an element in a B-tree. Show all the steps to insert 13, 50, 76, 62, 77. b. Write a Pseudo-code to delete an element from the B-tree. Show all the steps to delete 54, 46, 78, 75, 68

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 23 SOLUTION: TASK 2 a) INSERTION OF ELEMENTS IN B-TREE. Steps to be followed during insertion in a B-Tree: 1. Attempt to insert the new key into a leaf 2. If this would result in that leaf becoming too big, split the leaf into two, promoting the middle key to the leaf’s parent 3. If this would result in the parent becoming too big, split the parent into two, promoting the middle key 4. This strategy might have to be repeated all the way to the top 5. If necessary, the root is split in two and the middle key is promoted to a new root, making the tree one level higher Elements to enter: (13, 50, 76, 62, 77) The given tree is: 42 53 75 10 24 25 27 44 46 52 54 55 68 73 78 92 INSERT 13 When we attempt to insert the key 13 in the leaf in the left sub-tree, it has to be inserted between element 13 and 24. This results in this leaf becoming too big and hence, now we need split the leaf in two and promote the middle element to its parent. Since the parent leaf is still having a place o hold one more key element, it can allow the middle element from its child to take place between elements 42 and 53. 42 53 75 13 24 25 27 44 46 52 54 55 68 73 78 9210

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 24 The resulting tree would be like: 42 53 75 13 24 25 27 44 46 52 54 55 68 73 78 9210 INSERT 50 Splitting of leaf or promoting of middle key to its parent is not required if the key to be inserted do not result in over-sizing of the leaf it is being inserted into. In this step, key 50 can easily be inserted in the 3rd leaf of the tree and no splitting is required. 42 53 75 13 24 25 27 44 46 50 54 55 68 73 78 9210 52 INSERT 76 Similarly as the above step, insertion of 76 also does not lead to any splitting of leaf or promoting of middle key to its parent leaf. It can easily occupy a place on the right sub- tree of key 75 and can be attached to the leaf containing other keys like 78 and 92. 42 53 75 13 24 25 27 44 46 50 54 55 68 73 76 7810 52 92

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 25 INSERT 62 Insertion of key 62 is to be done in the 4th leaf, between elements 55 and 68. This leads to the over-sizing of the leaf and hence, this leaf will have to be split into two and the middle element has to be promoted to its parent leaf. Thus, key 62, being the middle element of the 4th leaf, has to be promoted to its parent leaf. 42 53 75 13 24 25 27 44 46 50 54 55 62 68 76 7810 52 9273 Promotion of key 62 to the parent results in a bigger parent size. Hence, this requires splitting up of the parent and the middle key element should be promoted to a newer root and thus taking the tree to one level higher. The middle element 53 in the root of the tree will have to be promoted to a new root. Rest of the elements will split and form two sub-tree nodes. 42 53 75 13 24 25 27 44 46 50 54 55 62 68 76 7810 52 9273 INSERT 77 Key 53 moves to one step higher and forms the only root of the tree. This promotes the tree to one level higher. Now, key 77 can easily be inserted in the 6th leaf of the tree, between elements 76 and 78. This requires no further leaf splitting or promotion of middle elements to higher level.

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 26 42 53 75 13 24 25 27 44 46 50 54 55 62 68 76 7710 52 7873 92 PSEUDOCODE FOR INSERTION B-Tree-SPLIT-CHILD(x, i, y) 1. z ALLOCATE-NODE() * 2. Leaf[z] leaf[y] 3. n[z] t -1 4. For j 1 to t-1 5. do key j [z] key j+t [y] 6. If not leaf [y] 7. Then for j 1 to t 8. do Cj [z] Cj+t [y] 9. n [y] t-1 10. For j n [x] + 1 downto i + 1 11. do Cj+1 [x] Cj [x] 12. Ci+1[x] z 13. for j n [x] 14. do keyj+1 [x] keyj [x] 15. keyi [x] 16. n [x] 17. DISK-WRITE (y) 18. DISK-WRITE (x) 19. DISK-WRITE (z) B-TREE-INSERT (T, k) 1. r root [T] 2. if n [r] = 2t-1 3. then s ALLOCATE-NODE() 4. root [T] s

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 27 5. leaf [s] FALSE 6. n [s] 0 7. C1 [s] r 8. B-TREE-SPLIT-CHILD(s,1,r) 9. B-TREE-SPLIT-NONFULL(s, k) 10. else B-TREE-SPLIT-NONFULL(r, k) B-TREE-INSERT-NONFULL(x, k) 1. i n [x] 2. if leaf [x] 3. then while i ≥ and k < keyi [x] 4. do key i+1 [x] keyi [x] 5. i i -1 6. keyi+1 [x] k 7. n [x] n[x] + 1 8. DISK-WRITE(x) 9. else while I ≥ 1 and k < keyi [x] 10. do i i – 1 11. i i +1 12. DISK-READ(Ci [x] ) 13. if n[Ci [x]] = 2t-1 14. Then B-TREE-SPLIT-CHILD(x,i,Ci[x]) 15. if k > keyi [x] 16. then i i+1 17. B-TREE-INSERT-NONFULL(Ci[x],k)

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 28 b)DELETION OF ELEMENTS: Steps to be followed during deletion of elements from the tree: 1) If the key is already in a leaf node, and removing it doesn’t cause that leaf node to have too few keys, then simply remove the key to be deleted. 2) If the key is not in a leaf then it is guaranteed (by the nature of a B-tree) that its predecessor or successor will be in a leaf -- in this case we can delete the key and promote the predecessor or successor key to the non-leaf deleted key’s position. 3) If (1) or (2) lead to a leaf node containing less than the minimum number of keys then we have to look at the siblings immediately adjacent to the leaf in question:  If one of them has more than the min. number of keys then we can promote one of its keys to the parent and take the parent key into our lacking leaf  If neither of them has more than the min. number of keys then the lacking leaf and one of its neighbours can be combined with their shared parent (the opposite of promoting a key) and the new leaf will have the correct number of keys; if this step leave the parent with too few keys then we repeat the process up to the root itself, if required The tree that resulted from the insertion of elements in the previous question will be used for deleting elements from it. DELETE 54 According to the 3rd rule of deletion, if deleting an element (54 in this case) from a leaf node results in the leaf node containing less than the minimum number of keys then we have to look at the siblings immediately adjacent to the leaf in question. But the leaf adjacent to key 54 does not have more than the minimum number of keys. Hence, it will be combined to the leaf having key 54 and the parent key will be brought and added to this leaf. 42 53 75 13 24 25 27 44 46 50 54 55 62 68 76 7710 52 7873 92

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 29 The parent key 62 is brought down to its child and combined to form a new leaf. Now, deletion of key 54 can be done and this won’t leave the leaf with a size less than the required leaf size. 42 53 75 13 24 25 27 44 46 50 54 55 62 68 76 7710 52 7873 92 But the above deletion leads to a smaller size of the parent of the 4th leaf. This would now require itself to be combined with the neighboring node and also share space with its parent. Thus, now we need to combine keys 24, 42, 53 and 75 and this will act as the only parent node of the tree. 42 53 75 13 24 25 27 44 46 50 55 62 68 76 7710 52 7873 92 Resultant tree is as follows (after combining the remaining element with its neighbor and the parent element): 42 53 75 13 24 25 27 44 46 50 55 62 68 76 7710 52 7873 92

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 30 42 53 75 13 24 25 27 44 46 50 55 62 68 76 7710 52 7873 92 DELETE 46 Even if we delete the key 46, this won’t affect the leaf it was in because even after the deletion of 46, the leaf will have 3 more elements and that is enough for a leaf to be kept attached to its parent. 42 53 75 13 24 25 27 44 50 55 62 68 76 7710 52 7873 92 DELETE 78 Similar to the above step, removing the key 78 doesn’t cause that leaf node to have too few keys. Hence, we do not have to face any problem in simply deleting the key element 78 from its leaf. 42 53 75 13 24 25 27 44 50 55 62 68 76 7710 52 7873 92 DELETE 75 After removing key 78, the resultant tree would be like as follows.

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 31 42 53 75 13 24 25 27 44 50 55 62 68 76 7710 52 73 92 According to the rule 2 of deletion of elements, the key 75 which is in a non-leaf node, its predecessor key 73 is in a leaf. In this case we can delete the key and promote the predecessor key 73 to the non-leaf deleted key’s position. Thus, key 73 will replace key 75. 42 53 13 24 25 27 44 50 55 62 68 76 7710 52 73 92 DELETE 68 Key 73 replaced key 75. We can see that, in the 4th leaf below, the leaf has 3 elements and deletion of one element out of these three won’t affect the leaf much as this does not result in the leaf with too few keys. Hence, we can easily remove element 68 from that leaf. 42 53 73 13 24 25 27 44 50 55 62 68 76 7710 52 92 The final tree after deletion of all the required elements will be as follows:

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 32 42 53 73 13 24 25 27 44 50 55 62 76 7710 52 92 PSEUDOCODE FOR DELETION B-Tree-Delete-key(x,k) 1. i  1 2. while i <= n[x] and k > keyi[x] 3. do ii+1 4. if i<=n[x] and k=keyi[x] and leaf[x] 5. then while i<n[x] //case 1 6. do keyi[x]  keyi+1[x] 7. n[x]  n[x]-1 8. Disk-Write(x) 9. return 10. if i<=n[x] and k=keyi[x] //case 2 11. then Disk-Read(ci[x]) 12. y  ci[x] 13. if n[y] >= t 14. then k’=keyn[y][y] //case 2a 15. B-Tree-Delete-key(y,k’) 16. keyi[x]  k’ 17. Disk-Write(x) 18. return 19. Disk-Read(ci+1[x]) 20. z  ci+1[x] 21. if n[z] >= t 22. then k’=key1[z] //case 2b 23. B-Tree-Delete-key(z,k’) 24. keyi[x]  k’ 25. Disk-Write(x) 26. return 27. keyt[y]  keyi[x] //case 2c 28. for j  i to n[x]-1 29. do keyj[x]  keyj+1[x] 30. cj+1[x]  cj+2[x] 31. n[x]  n[x]-1 32. Disk-Write(x)

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 33 33. for j  t+1 to 2t-1 34. do keyj[y]  keyj-t[z] 35. cj[y]  cj-t[z] 36. c2t[y]  ct[z] 37. n[y]=2t-1 38. Disk-Write(y) 39. De-Allocate-Node(z) 40. B-Tree-Delete-key(y,k) 41. return 42. if not leaf[x] 43. then s  ci[x] 44. Disk-Read(s) //case 3 45. 46. if n[s] = t-1 then 47. Disk-Read(ci-1[x]) 48. if n[ci-1[x]] > t-1 then //3a left sibling 49. n[s]  n[s]+1 50. for j=n[s] downto 2 51. do keyj[s]  keyj-1[s] 52. cj+1[s]  cj[s] 53. key1[s]  keyi-1[x] 54. c1[s]  cn[ci-1[x]]+1[ci-1[x]] 55. keyi-1[x]  keyn[ci-1[x]][ci-1[x]] 56. n[ci-1[x]]  n[ci-1[x]]-1 57. Disk-Write(x) 58. Disk-Write(ci-1[x]) 59. Disk-Write(s) 60. 61. Disk-Read(ci+1[x]) 62. if n[ci+1[x]] > t-1 then //3a right sibling 63. n[s]  n[s]+1 64. keyt[s]  keyi[x] 65. ct+1[x]  c1[ci+1[x]] 66. keyi[x]  key1[ci+1[x]] 67. for j=1 to n[ci+1[x]]-1 68. do keyj[ci+1[x]]  keyj+1[ci+1[x]] 69. cj[ci+1[x]]  cj+1[ci+1[x]] 70. cn[ci+1[x]][ci+1[x]]  cn[ci+1[x]]+1[ci+1[x]] 71. n[ci+1[x]]  n[ci+1[x]] –1 72. Disk-Write(x) 73. Disk-Write(ci+1[x]) 74. Disk-Write(s) 75. 76. keyt[s]  keyi[x] //case 3b 77. z ci+1[x] 78. for j  i to n[x]-1

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 34 79. do keyj[x]  keyj+1[x] 80. cj+1[x]  cj+2[x] 81. n[x]  n[x]-1 82. Disk-Write(x) 83. for j  t+1 to 2t-1 84. do keyj[s]  keyj-t[z] 85. cj[s]  cj-t[z] 86. c2t[s]  ct[z] 87. n[s]=2t-1 88. Disk-Write(s) 89. De-Allocate-Node(z) 90. B-Tree-Delete-key(s,k) //delete k in the subtree size > t-1

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 35 TASK 3: COMPLEXITY CLASSES a. Discuss the concept of complexity class and differentiate between the various complexity classes. b. Explain (at least two (2)) example of problems for each complexity class. c. Categorize the algorithms discussed in Task 1 and Task 2 based on the complexity classes. Also give justification as to why the problems belong to respective classes. SOLUTION: TASK 3 a) CONCEPT OF COMPLEXITY CLASS It is an unexplained phenomenon that for many problems we know and study, the best algorithms for their solutions have computing times that cluster into two groups. The first group consists of problems whose solution time is bounded by polynomials of small degree. Examples include ordered searching which is O(log n), polynomial evaluation which is O(n), sorting which is O(n log n) and string editing which is O (mn). The second group is made up of those problems whose best-known algorithms fall in the non-polynomial category. Examples for such problems include the travelling salesperson decision problems (these are similar to the directed Hamiltonian problems) and the knapsack problems for which the best algorithms have complexities O(n^2 2^2n) and O(2^n/2) respectively. Prior to discuss over the complexity classes, we need to understand what is meant by polynomial time and polynomial time algorithms. Polynomial time An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is for some nonnegative integer , where is the complexity of the input. Polynomial-time algorithms are said to be "fast." Most familiar mathematical operations such as addition, subtraction, multiplication, and division, as well as computing square roots, powers, and logarithms, can be performed in polynomial time. Computing the digits of most interesting mathematical constants, including and , can also be done in polynomial time. A problem can fall into either of the following categories:

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 36 TRACTABLE INTRACTABLE UNKNOWN We have polynomial time algorithms coming under this category. It has been proved that there can be no polynomial time algorithms. There is no polynomial time algorithm, but it has never been proved that such an algorithm cannot exist. The P Class The Class P algorithms come under the category of deterministic algorithms which has the property that the result of every operation is uniquely defined. Such algorithms agree with the way programs are executed on a computer. If we think about the problems we actually present to the computer we note that not too many computations require more than O(n3 ) or O(n4 ) time. In fact, most of the important algorithms we compute are somewhere in the O(log n) to O(n3 ) range. Thus we shall state that practical computation resides within polynomial time bounds. There is a name for this class of problems. The class of polynomially solvable problems, P contains all sets in which membership may be decided by an algorithm whose running time is bounded by a polynomial. Ref: http://www.cs.uky.edu/~lewis/cs-heuristic/text/class/p-np.html Besides containing all of what we have decided to consider practical computational tasks, the class P has another attractive attribute. Its use allows us to not worry about our machine model since all reasonable models of computation (including programs and Turing machines) have time complexities, which are polynomially related. The NP Class Let us consider a class of problems, which all seem very complex, but have solutions, which are easily checked. Here is a class, which contains the problems for which solutions can be verified in polynomial time. The class of nondeterministic polynomially acceptable problems, NP, contains all sets in which membership can be verified in polynomial time. Note: A non-deterministic algorithm terminates unsuccessfully if and only if there exists no set of choices leading to a success signal. The computing times for Choice, Success and Failure are taken to be O(1). Class NPC

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 37 There may be many problems coming under the category of NPC. But before attempting to solve them, it is important to confirm whether they are tractable or intractable. So far, researches have shown that NP Complete problems are intractable. A problem that is NP-Complete has the property that it can be solved in polynomial time if and only if all other NP-complete problems can be solved in polynomial time. All NP-Complete problems are also referred as NP-hard problems. Class P Class NP Class NPC Solvable in Polynomial- time ( O(nk ) ) for some constant k  “Verifiable” in polynomialtime  Given a “certificate” of a solution, we can verify that the certificate is correct in O(nk ) time. This is the class of NP Complete problems which are in NP and as hard as a NP problem. P is a set of all decision problems solvable by deterministic algorithms in polynomial time It is the set of all such problems that can be solvable by non-deterministic polynomial time algorithms. Since deterministic algorithms are just a special case of non-deterministic ones, we can conclude that P  NP. b) EXAMPLES OF PROBLEMS FOR EACH COMPLEXITY CLASS EXAMPLES OF CLASS P PROBLEMS All those problems that can be solved within a polynomial time using a deterministic approach comes under the category of Class P problems. Some examples for such problems are:  Ordered searching which is O(log n)  Polynomial evaluation which is O(n)  Sorting which is O(n log n)  String editing which is O (mn)  Minimum Weighted Spanning Tree  Kruskal’s algorithm with complexity O(n2). CLASS P CLASS NP NP P

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 38 EXAMPLES OF CLASSS NP PROBLEMS Some of the problems belonging to the NP class are:  The travelling salesperson decision problems (these are similar to the directed Hamiltonian problems)  The knapsack problems 1) The Travelling–salesman problem In the travelling-salesman problem, which is closely related to the undirected Hamiltonian cycle problems, a salesman is required to visit n cities. Modeling the problem as a complete graph, we can say that the salesman decides to make a Hamiltonian cycle, visiting each city not more than once and finishing at the city he starts. This total tour cost should be the minimum i.e., the sum of the individual costs along the edges of the tour. For example, in the following figure, the minimum cost tour is (a, b, c, d, a) with cost 7. a b cd 3 4 2 5 1 1 Application of Travelling Salesperson Problems:  Transportation and Logistics – E.g. arranging bus facility in a city for children.  Circuit boards  Telecommunication networks 2) The Knapsack Problems Given a set of items, each with a cost and a value, determine the number of each item to include in a collection so that the total cost is less than some given cost and the total value is as large as possible. Suppose 5 items are available and their weights and values are given. The problem is to find a packing of largest possible total value with a total weight not exceeding 9.

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 39 Item A B C D E Weight 3 8 6 4 2 Value 2 12 9 3 5 Value/Weight 2.5 1.5 1.5 0.75 0.67 We calculate the Value/Weight value for each item available and arrange them according to their descending order. Hence, the order of items will be: E, B, C, D, A. In the above selection, 1 means that an item is chosen; while 0 means that an item is not chosen. At the later steps, we choose the branch which appears to be most promising. This step is repeated until we get the packing of the largest possible total value with a weight not exceeding 9. In the solution to the above problem, there are 25 =32 possible solutions. EXAMPLES OF NP-complete Problems  Directed Hamiltonian Circuits decision problem  Boolean satisfiability problem  Clique Decision Problems (CDP)

Algorithms Assignment PT1081156 ASIA PACIFIC INSTITUTE OF INFORMATION TECHNOLOGY Page 40 REFERENCES References for Website pages 1) Time complexity of algorithm Aashish Barnwal. (2012). Greedy Algorithms | Set 2 (Kruskal’s Minimum Spanning Tree Algorithm). Available: http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals- minimum-spanning-tree-mst/. Last accessed 29th Oct 2013. 2) Complexity Classes Jessica Su. (20111). What are P, NP, NP-complete, and NP-hard?. Available: http://www.quora.com/What-are-P-NP-NP-complete-and-NP-hard. Last accessed 25th Oct 2013. 3) B-Trees Aashish Barnwal. (2012). B-Tree | Set 1 (Introduction). Available: http:// http://www.geeksforgeeks.org/b-tree-set-1-introduction-2/. Last accessed 29th Oct 2013. 4) Polynomial Time David Terr. (2012). Polynomial Time. Available: http://mathworld.wolfram.com/PolynomialTime.html. Last accessed 25th Oct 2013. Reference from Books 1) Greedy Algorithm Ellis Horowitz. (2009). The Greedy Method. In: Ellis Horowitz, Sartaj Sahni, and Sanhuthevar Rajasekaran Fundamentals of Computer Algorithms. 2nd ed. New Delhi: Galgotia Publications. 197-220. 2) P, NP, NP-COMPLETE PROBLEMS Ellis Horowitz. (2009). P, NP, NP-Complete Problems. In: Ellis Horowitz, Sartaj Sahni, and Sanhuthevar Rajasekaran Fundamentals of Computer Algorithms. 2nd ed. New Delhi: Galgotia Publications. 495-530. 3) Insertion & Deletion Pseudocodes Thomas H. Cormen. (2009). Basic Operations on B-Trees. In: Charles E. Leiserson, Clifford Stein Introduction to Algorithms. 2nd ed. New Delhi: PHI Learning Pvt. Ltd.. 444-446.

Algorithms explained

More Related Content

What's hot

Similar to Algorithms explained

Recently uploaded

Algorithms explained