Scribd
Upload
5 views14 pages

AAD Module 3

The document covers key concepts in algorithm analysis and design, focusing on Divide and Conquer and Greedy strategies. It details algorithms such as Merge Sort, Strassen’s Matrix Multiplication, and the Fractional Knapsack Problem, including their complexities and applications. Additionally, it discusses spanning trees, their properties, and algorithms for finding minimum spanning trees like Prim's and Kruskal's algorithms.

Uploaded by

arakkalamnazri2020
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
5 views14 pages

AAD Module 3

The document covers key concepts in algorithm analysis and design, focusing on Divide and Conquer and Greedy strategies. It details algorithms such as Merge Sort, Strassen’s Matrix Multiplication, and the Fractional Knapsack Problem, including their complexities and applications. Additionally, it discusses spanning trees, their properties, and algorithms for finding minimum spanning trees like Prim's and Kruskal's algorithms.

Uploaded by

arakkalamnazri2020
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Medute (51306-Algantm Analysis an Desig CE) Module II * Divide & Conquer and Greedy Strategy © The Control Abstraction of Divide and Conquer © 2-way Merge sort ©. Strassen’s Algorithm for Matrix Multiplication-Analysis ‘The Control Abstraction of Greedy Strategy Fractional Knapsack Problem ‘Minimum Cost Spanning Tree Computation- Kruskal’s Algorithms — Analysis Single Source Shortest Path Algorithm - Dijkstra’s Algorithm-Analysis * Divide and Conquer © Divide and conquer algorithm is having three parts: 1. Divide the problem into a number of sub-problems that are smaller instances of the same problem, 2. Conquer the sub-problems by solving them recursively. If they are small enough, solve the sub-problems as base cases. 3. Combine the solutions to the sub-problems into the solution for the original problem. divide solve subproblem solve conquer subproblem combine © Control Abstraction: It is a procedure whose flow of control is clear but whose primary operations are specified by other procedure whose precise meanings are left undefined. © Control Abstraction: Divide and Conquer Algorithm DAndC(P) { if Small(P) then return S(P) else { Divide P into smaller instances Py, P2,.... Phy KEI; apply DAndG to each of these sub-problems; return Combine(DAndC(P:), DAndC(P,), . ..., DAndC(PA)); } I + Ifthe given problem is small, return the result Modul (51206-Algantim Analy and Desig CSE] * Otherwise, divide the problem into smaller instances P,, P», Py = Apply DAndC() to each of these sub-problems. * Finally combine the results of all sub-problems * DAndCO can be described using the following recurrence relation: a(n) nis small T(n) = Tm) + T(n) +... + T(r) + f(n) Otherwise ‘© T(n): Time for divide and conquer on any input of size n ‘* f(a): Complexity of dividing the problem and combining the results. Complexity of many divide and conquer algorithms are given by the following recurrence relation TQ) n= T(n) = aT(n/b) + f(n) nel o 2 Way Merge Sort * Given a sequence of n elements afl],.....a{n]. Split this array into two sets aft],.a.{n/2] and a{(n/2)+1],...a{n}. Each set is individually sorted, and the resulting sorted sequences are merged to produce a single sorted sequence of n element. Algorithm MergeSort(low, high) { mid = (low + high )/2; MergeSort(low, mid); MergeSort(mid+1, high); Merge(low, mid, high); + Algorithm Merge(low, mid, high) { i= low; x= low; y= mid + 1; while((x < mid) and (y < high)) do { if (alx] k=log n] nT(1)+enlogn an*cnlogn O(n log n) Best Case, Average Case and Worst Case Complexity of Merge Sort = O(n log n) © Divide and Conquer Matrix Multiplication «Native matrix multiplication complexity = O(n’) = Divide and Conquer Matrix Multiplication Algorithm 1, We have to compute the product of 2 nxn matrices A and B. 2. Assume that n is the power of 2. That is n=2" If nis not a power of 2, then enough rows and columns of 0’s can be added to both A and B so that the resulting dimensions are the power of two. 3. Then partition A and B into 4 square matrices, each of size w2 x n/2 4. AB can be computed using the formula Cu = Au Bu + Av Bar Cx = Au Biz + Ar Baa Cay = Ani Bu + Azz Bar Cx2 = Aoi Biz + Azz Bor 5. If n=2, these formulas are computed using a multiplication operation for the elements of Aand B 6. If n>2, the elements of C can be computed using matrix multiplications and addition operations applied to the matrices of size n/2 x n/2 7. This algorithm will continue applying itself to smaller sized sub-matrices until n becomes suitably small(n=2) so that the product is computed directly. * Complexity © For multiplying two matrices of size n x n, we make 8 recursive calls above, each on a matrix with size n/2 x m2. Addition of two matrices takes O(n’) time. Time complexity = 8 T(n/2) + O(n’) = O(n’) [By Master's Theorem] © Strassen’s Matrix Multiplication = Algorithm 1. Aand B are the matrices with dimension nxn 2. If'mis not a power of 2, then enough rows and columns of 0’s ean be added to both A and B so that the resulting dimensions are the power of two. 3, Partition A and B in to 4 square matrices of size n/2 x n/2 Medtle (657306 Agoritam Analysis and DesgnS6 CSE) a,b, cand d are sub-matrices of A, of size n/2 x n/2 ¢, f, g and h are sub-mattices of B, of size n/2 x 2 ‘Compute 7 1/2 x n/2 matrices Pi=a(f-h) Pr=h(atb) Py=e(ctd) Py=d(g—e) P5=(a+d)(e+h) Po=(b-d)(g +h) Pr =(a-o)(e+f) It requires 7 matrix multiplications and 10 matrix additions and subtractions ‘Then compute C GG GC Ci=Py+ Pe PoP C.=Pi+P: Cy=P3+ Pa, Ca= Pr Ps + Ps Pr c Complexity For multiplying two matrices of size n x n, we make 7 matrix multiplications and 10 matrix additions and subtractions Addition/Subtraction of two matrices takes O(n’) time. Time complexity 7 T(w2) + O(n?) = O(n"*’) = OM") [By Master’s Theorem] T(n) = b ifn<2 7 T(n/2) + cn? Otherwise T(n) = 7'T(n/2) + en? PT(n/2*) + 7c nid +c n* ere) Te ntidee 7 ent 2 Tiw2') +7 ena Tenis ¥en PrQv2') + (MIA) ont... 47/4) ent en? Pp 2") + [14(7/4) +. + (FA) Jon? MT (n2") + [14(7/4) +. Jen? Tr 2") + [(1-(7/4))] cn? 7% °T(1) -[4/3] cn” [Assume that n/2* = 1 > k = log n) = n!70(1) -[4/3] en? = O(n") = O(n"*) Medute (57 306- Algorithm Anais and DesiontS6 CSE) © Example 1. Multiply the following two matrices using Strassen’s Matrix Multiplication Algorithm 6 8 2 5) a-| a-| 9 7 3 6 © Greedy Strategy x= Select(a); if Feasible(solution, x) then solution = Union(solution, x); } return solution; + Seleci() selects an input from the array al] and remove it. ‘The selected input value is assigned to x. + Feasible() is a Boolean valued function that determines whether x can be included into the solution subset. + Union() combines x with the solution and updates the objective function. + Fractional Knapsack Problem © We are given with n objects and a knapsack(or bag) of capacity m. The object i has weight W: and profit P,. Ifa fraction X; is placed into the knapsack, then a profit P,X, is obtained. The objective is to obtain an optimal solution of the knapsack that maximizes the total profit eamed. ©. The total weight of all the chosen objects should not be more than m, © Fractional knapsack problem can be stated as Maximize Df, PiXi Subject to Di, Wixi < n— (2) 0 U then break; .0 uU-wlil; } Iti snthen x{i] =U/ wlils } © Time Complexity * The for loop will execute maximum n times. So the time complexity = O(n) © Example 1. Find the optimal solution for the following fractional Knapsack problem. n=7, m=15, P={10, 5, 15, 7, 6, 18, 3} and W={2, 3,5, 7, 1,4, 1) ‘* Arrange the objects in the descending order of profit/weight iH bk % 3 4 5 6 7} P ={ 1 5 15 7% 6 18 3} 2 3 5 7% Lb 4 Oo 5 166, 3 1, 6 45, 3} Now the i, P and W arrays are 6 3 7% 2 4} 18, 15, 3 5, 7} 4 5 1 3 7} Wi Xi U=U-Wi 1 1 14 2 1 2 4 1 8 5 1 3 1 1 2 3 23 0 7 0 0 ‘Total weight of the chosen objects are Pay WiXi = 2x1 + 3x2/3 + SL + 7x0 +1x1 + 4x1 + 1x1 © Profit earned is Y"_, PiXi = 10x1 + 5x2/3 + 15x1 + 7x0 + 6x1 + 18x1 + 3x1 = 55.33 * Solution vector X={1, 2/3, 1, 0, 1, 1, 1} o Examples 1. Find the optimal solution for the following fractional Knapsack problem. Given number of items(n)=4, capacity of sack(m) = 60, W={40,10,20,24} and P={280,100,120,120} 2. Find an optimal solution to the fractional knapsack problem for an instance with number of items 7, Capacity of the sack W=15, profit associated with the items (p1,p2,....p7)= (10,5,15,7,6,18,3) and weight associated with each item (w1,W2,...W7)= (23,5, * Spanning Trees © A spanning tree is a subset of undirected connected Graph G=(V,E), which has all the vertices, covered with minimum possible number of edges. Medtle (657306 Agoritam Analysis and DesgnS6 CSE) Properties of Spanning Tree = Acconnected graph G can have more than one spanning tree, + All possible spanning trees of graph G, have the same number of edges and vertices. * The spanning tree does not have any cycle (loops) = Removing one edge from the spanning tree will make the graph disconnected, ie. the spanning tree is minimally connected + Adding one edge to the spanning tree will create a circuit or loop, Le. the spanning tree is maximally acyc! = Spanning tree has n-1 edges, where n is the number of nodes. Maximum number of Spanning Trees of a graph with n nodes = Complete Graph: n* * Other Graphs 1. Create Adjacency Matrix for the given graph. 2. Replace all the diagonal elements with the degree of nodes, 3. Replace all non-diagonal 1’s with -1. 4, Total number of spanning tree for that graph = Co-factor for any element in that matrix, imum Spanning Tree (MST) = In a weighted graph, a minimum spanning tree is a spanning tree that has minimum ‘weight than all other spanning trees of the same graph. * In real-world situations, this weight can be measured as distance, congestion, traffic load or any arbitrary value denoted to the edges. * Minimum Spanning-Tree Algorithms © Prim’s Algorithm © Kruskal's Algorithm Application of Spanning Tree + Civil Network Planning Computer Network Routing Protocol Cluster Analysis Handwriting Recognition Image Segmentation Examples 1. Write the total number of spanning trees possible for a complete graph with 6 vertices Medtle 2. (s1206-Algatim Analyse and Desig CE) Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4). Entry Wij in the matrix W below is the weight of the edge i, j}. What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T? joiei4 {1 0 1249 W=|8 12 0 73 j1 4.702 l4.9 3 20) Let (u,v) be a minimum-weight edge in a graph G. Show that (u,v) belongs to some minimum spanning tree of G. © Suppose that T is a Minimum Spanning Tree, which does not include the smallest edge, E. Add E to T. Now a circle C is formed. This graph will remains connected if an edge is removed from the circle C. So remove an edge E"(except E) from C which also belongs to T This operation would result a new spanning tree whose weight is <= weight of T. ‘We have a contradiction. Hence, proved. Let G be a weighted undirected graph with distinct positive edge weights. If every edge weight is increased by same value, will the minimum cost spanning tree change. Justify your answer The Minimum Spanning Tree doesn’t change. In Kruskal’s algorithm, we will sort the edges first. IF we increase all weights, then order of edges won’t change. So, MST does not change. ‘Minimal Cost Spanning Tree Computation o Kruskal’s Algorithm. Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree. Kruskal's algorithm follows greedy approach as in each iteration it finds an edge which has least weight and add it to the growing spanning tree In this algorithm, the edges of the graph are considered in the increasing order of cost. If the selected edge will form a cycle, then discard it. This selection process continues until there are n-1 edges. Algorithm Kruskals(E, cost, n, 0) { Construct a heap out of edge costs using Heapify(); for i=1 to ndo parent(i = 1-0; mincost = 0.0; while (i < n-1) and (heap not empty) do { Delete a minimum cost edge (u, v) from the heap and reheapify using Adjust(); j= Find(u); k= Find(y); ifj#k then Medtle (651305 Agoritam Analysis and DesignS6 CSE) { is ti, =u; =v; mincost = mincost + cost{u, v]; UnionG, k); ) } if '# 0-1 then Write (“No Spanning Tree” else return mincost; t E is the set of edges and n is the number of vertices in G. cost{u,v] is the cost of edge (u, v). Lis the set of edges in the minimum cost spanning tree. The final cost is returned = Heapily() is used to construct a minheap based on the edge cost of G. = Adjust() is used to reconstruct a minheap if there is a deletion occurs. * Initially all vertices are belongs to different sets. Find() returns the set number of that particular vertex. j and k are the set number of vertex u and v respectively. = If jk means vertex u and v are belongs to the same set. Inclusion of (u, v) should definitly form a cycle. So discard it = If }#k means vertex u and v are belongs to different set. Inclusion of (u, v) will not form a cycle. So add it to the minimum spanning tree edge list. * Finally there are n-1 edges, then retrun it. Otherwise there is no spanning tree. © Complexity = The edges are maintained as a minheap, then the next edge to consider can be obtained in O(log |E)) time. Construction of heap itself takes O(|E)) time. * Overall complexity of Kruskal’s algorithm is O((E| logiE)).. © Example © Construct the minimum spanning tree for the given graph using Kruskal’s Algorithm 2 Medtle {651306 Agoritam Analysis and DesignS6 CSE) ° Soo Step 2 Step 5 Step 6 This is the minimum cost spanning tree. mincost= 10 + 25 + 22 +12 + 16 + 14= 99 o Examples 1. Find the number of distinct minimum spanning trees for the weighted graph below 2. Consider a weighted complete graph G on the vertex set {Vi,¥2,...¥a} stich that the ‘weight of the edge (vi,v) is 2]. Find the weight of a minimum spanning tree of G. 3. An undirected graph G=(V, E) contains n (n > 2.) nodes named v1,V2,....Vp. Two vertices vv,¥j are connected if and only if 0 < |i jj <= 2. Each edge (v,\)) is assigned a weight i + |. What will be the cost of the minimum spanning tree (as a function of n) of such a graph with n nodes? 4. Apply Kruskal’s algorithm on the graph given below. Medtle (657306 Agoritam Analysis and DesgnS6 CSE) 5. Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry wij in the matrix W below is the weight of the edge (i, j}. What is the Cost of the Minimum Spanning Tree T using Kruskal’s Algorithm in this graph such that vertex 0 is a leaf node in the tree T? OvaR Nwoe 49 320 6. Apply Kruskal’s algorithm on the following graph, Let A be the source vertex 7. Compute the Minimum Spanning Tree and its cost for the following graph using a's Algorithm, Indicate each step clearly ‘Single Source Shortest Path Algorithms © Theshortest path problemis the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. © Different shortest path problems are: = Single Source Shortest Path Problem: * Given a connected weighted graph G=(V,E), find the shortest path from a given source vertex s to every other vertices (V-{s}) in the graph. The weight of any path(w(p)) is the sum of the weights of its constituted edges. ‘The weight of the shortest path from u yo v = min{w(p): p is a path from u to v} Moa (37 206- gatim Anais and Desi CSE * Single Destination Shortest Path Problem: To find shortest paths from all vertices in the directed graph to a single destination vertex v * All Pairs Shortest Path Problem: To find shortest paths between every pair of vertices in the graph © Single Source Shortest Path Algorithms are: = Dijkstra’s Algorithm * Bellman Ford Algorithm © Dijkstra’s Algorithm * Given a graph and a source vertex S in graph, find shortest paths from $ to all vertices in the given graph, * Algorithm Dijkstra(G,W, S) 1. For each vertex v in G 1.1 distance[v] = infinity 1.2 previous[v] = Null 2. distance[S] = 0 Q= set of vertices of graph G 4, While Q is not empty 4.1 w= vertex in Q with minimum distance 4.2 remove u from Q 4.3 for each neighbor v of u which is still in Q 4.3.1 alt = distancefu] + W(u,¥) 4.3.2 if alt Path-2 cost So the shortest path may change. 4, Ina weighted graph, assume that the shortest path from a source ‘s’ to a destination ‘t" is correctly calculated using a shortest path algorithm, Is the following statement true? If we increase weight of every edge by 1, the shortest path always remains same. Justify your answer with proper example.

You might also like