E Lesson 7

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

MCA 2 All right are reserved with CU-IDOL DESIGN AND ANALYSIS OF ALGORITHMS Course Code: MCA 632 Semester: Third e-Lesson: 7 SLM Unit: 8,9 www.cuidol.in Unit-8-9(MCA 632)

Design and Analysis of Algorithms 33 OBJECTIVES INTRODUCTION  Student will be able to learn about Dynamic  In this unit we are going to learn about approach to design the algorithm. algorithm analysis through dynamic  Student will be able to learn about transitive approach. closure, Bellman ford algorithm. Under this you will learn and understand the  Student will be able to learn knapsack problem an  concept of all pair shortest path algorithm. TSP Knapsack problem and Travelling Student will be able to learn Optimal binary search salesperson problem.  tree.  Optimal Binary Search Tree www.cuidol.in Unit-8-9(MCQA-10613)2) INSTITUTE OF DAIlSlTAriNgChEt aArNeDreOsNeLrvINeEd LwEiAthRNCIUN-GIDOL

TOPICS TO BE COVERED 4 Dynamic Programming 1: General method with Examples Multistage Graphs Transitive Closure: Warshall’s Algorithm Dynamic Programming 2: All Pairs Shortest Paths: Floyd’s Algorithm Optimal Binary Search Trees Knapsack Problem Bellman-Ford Algorithm Travelling Sales Person problem Reliability design www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Dynamic Programming 5 Dynamic Programming DP reduces computation by:  Solving sub problems in a bottom-up fashion.  Storing solution to a sub problem the first time it is solved.  Looking up the solution when sub problem is encountered again.  Key: determine structure of optimal solutions www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Steps in Dynamic Programming 6 1. Characterize structure of an optimal solution. 2. Define value of optimal solution recursively. 3. Compute optimal solution values either top-down with caching or bottom-up in a table. 4. Construct an optimal solution from computed values. www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Multistage Graphs 7 1. To find a shortest path in a multi-stage graph 327 S 1 A 4 B T 5 56 2. Apply the greedy method : Fig. 3.1: Multistage Graph 3. the shortest path from S to T : 4. 1 + 2 + 5 = 8 www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Shortest Paths in Multi stage Graph 8 A4D 1 9 18 11 S 2 B 5 E 13 T 16 2 5 C2 F Fig. 3.2: Implementation The greedy method can not be applied to this case: (S, A, D, T) 1+4+18 = 23. The real shortest path is: (S, C, F, T) 5+2+2 = 9. www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Dynamic Programming 9 (Forward Approach) A4D 1 A 2 d(A, T) 1 18 11 9 5 S 2 B 5 E 13 T S d(B, T) T 16 2 B 5 d(C, T) C2 F C d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)}  d(A,T) = min{4+d(D,T), 11+d(E,T)} A 4D d(D, T) = min{4+18, 11+13} = 22. Fig. 3.3: Dynamic Programming 11 E T d(E, T) www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Contd… 10 • d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)} = min{9+18, 5+13, 16+2} = 18. A4D 1 9 18 11 S 2 B 5 E 13 T 9 D 5 16 2 d(D, T) 16 5 d(E, T) C2 F E B T • d(C, T) = min{ 2+d(F, T) } = 2+2 = 4 d(F, T) • d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} F = min{1+22, 2+18, 5+4} = 9. • The above way of reasoning is called backward reasoning. Fig. 3.4: Backward Reasoning www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Contd… d(S, A) = 1 1 A 4D 18 11 2 13 d(S, B) = 2 S 5 11 9 2 T d(S, C) = 5 B 5E d(S,D)=min{d(S,A)+d(A,D), d(S,B)+d(B,D)} 16 2F = min{ 1+4, 2+9 } = 5 C d(S,E)=min{d(S,A)+d(A,E), d(S,B)+d(B,E)} = min{ 1+11, 2+5 } = 7 d(S,F)=min{d(S,B)+d(B,F), d(S,C)+d(C,F)} = min{ 2+16, 5+2 } = 7 www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Contd… 12 • d(S,T) = min{d(S, D)+d(D, T), d(S,E)+ A 4D d(E,T), d(S, F)+d(F, T)} 11 9 = min{ 5+18, 7+13, 7+2 } =9 B 5E 1 16 F 18 13 S2 C 2 2 T 5 www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Transitive Closure 13 Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that there is a path from vertex i to j. The reach- ability matrix is called transitive closure of a graph. 0010 3 1001 3 1 0000 1 0100 2 4 0010 2 www.cuidol.in 4 1111 Fig. 3.5: Transitive closure 0000 Unit-8-9(MCA 632) 1111 All right are reserved with CU-IDOL

Warshall’s Algorithm 14 www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Floyd’s Algorithm: 15 All Pair Shortest Paths Floyd-Warshall algorithm is used to find all pair shortest path problem from a given weighted graph. As a result of this algorithm, it will generate a matrix, which will represent the minimum distance from any node to all other nodes in the graph. At first, the output matrix is the same as the given cost matrix of the graph. After that, the output matrix will be updated with all vertices k as the intermediate vertex. The time complexity of this algorithm is O(V^3), where V is the number of vertices in the graph. www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Floyd’s Algorithm: 16 All Pair Shortest Paths Algorithm floydWarshal(cost) Input: The cost matrix of given Graph. Output: Matrix to for shortest path between any vertex to any vertex. Begin for k := 0 to n, do for i := 0 to n, do for j := 0 to n, do if cost[i,k] + cost[k,j] < cost[i,j], then cost[i,j] := cost[i,k]+cost[k,j] done done done display the current cost matrix End www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Optimal Binary Search Tree 17  Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.  Let us first define the cost of a BST. The cost of a BST node is level of that node multiplied by its frequency. Level of root is 1. www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

0-1 Knapsack Problem 18 The goal is to maximize the value of a knapsack that can hold at most W units (i.e. lbs or kg) worth of goods from a list of items I0, I1, … In-1. Each item has 2 attributes: 1) Value – let this be vi for item Ii 2) Weight – let this be wi for item Ii www.cuidol.in Fig. 3.7: Knapsack Problem All right are reserved with CU-IDOL Unit-8-9(MCA 632)

0-1 Knapsack Problem 19 The difference between this problem and the fractional knapsack one is that you CANNOT take a fraction of an item.  You can either take it or not. Hence the name Knapsack 0-1 problem. ww1w3.c-0ui3d-o2l.i0n20 Unit-8-9(MCA 632) All right are reserved with CU-IDOL

0-1 Knapsack Problem 20  Brute Force  The naïve way to solve this problem is to cycle through all 2n subsets of the n items and pick the subset with a legal weight that maximizes the value of the knapsack.  We can come up with a dynamic programming algorithm that will USUALLY do better than this brute force technique. www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

0-1 Knapsack Problem 21  Let’s illustrate that point with an example: Value Item Weight 10 I0 3 4 I1 8 9 I2 9 11 I3 8  The maximum weight the knapsack can hold is 20. www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Contd… 22  The best set of items from {I0, I1, I2} is {I0, I1, I2}  BUT the best set of items from {I0, I1, I2, I3} is {I0, I2, I3}.  In this example, note that this optimal solution, {I0, I2, I3}, does NOT build upon the previous optimal solution, {I0, I1, I2}.  (Instead it build's upon the solution, {I0, I2}, which is really the optimal subset of {I0, I1, I2} with weight 12 or less.) www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

0-1 Knapsack Algorithm 23 for w = 0 to W { // Initialize 1st row to 0’s B[0,w] = 0 } for i = 1 to n { // Initialize 1st column to 0’s B[i,0] = 0 } for i = 1 to n { for w = 0 to W { if wi <= w { //item i can be in the solution www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

0-1 Knapsack Algorithm 24 if vi + B[i-1,w-wi] > B[i-1,w] B[i,w] = vi + B[i-1,w- wi] else B[i,w] = B[i-1,w] } else B[i,w] = B[i-1,w] // wi > w } } www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

Bellman Ford Algorithm 25 Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges. We have discussed Dijkstra’s algorithm for this problem. Dijkstra’s algorithm is a Greedy algorithm and time complexity is O(VLogV) (with the use of Fibonacci heap). Dijkstra doesn’t work for Graphs with negative weight edges, Bellman-Ford works for such graphs. Bellman-Ford is also simpler than Dijkstra and suites well for distributed systems. But time complexity of Bellman-Ford is O(VE), which is more than Dijkstra. www.cuidol.in Unit-8-9(MCA 632) 25 All right are reserved with CU-IDOL

Bellman Ford Algorithm 26 Like other Dynamic Programming Problems, the algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates shortest paths with at-most 2 edges, and so on. After the i-th iteration of outer loop, the shortest paths with at most i edges are calculated. There can be maximum |V| – 1 edges in any simple path, that is why the outer loop runs |v| – 1 times. The idea is, assuming that there is no negative weight cycle, if we have calculated shortest paths with at most i edges, then an iteration over all edges guarantees to give shortest path with at-most (i+1) edges www.cuidol.in Unit-8-9(MCA 632) 26 All right are reserved with CU-IDOL

Travelling Salesperson 27 Problem(TSP) Sometimes Dynamic Programming can be used to find relatively fast, but still exponential algorithms. Travelling Salesman Problem Given: A distance table between n cities. Problem: Find a shortest tour. A tour here is required to visit each city exactly once and return to the city of origin. The cost is the sum of the edge costs. www.cuidol.in Unit-8-9(MCA 632) 27 All right are reserved with CU-IDOL

TSP Algorithm 28 • Algorithm: 1. Construct the minimal spanning tree 2. Duplicate all its edges. This gives us an Euler cycle. 3. Traverse the cycle, but do not visit any node more than once, taking shortcuts when it passes a visited node www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 1. Which of the following algorithms solves the all-pair shortest path problem? 29 a) Dijkstra's algorithm b) Floyd's algorithm c) Prim's algorithm d) Warshall's algorithm 2.From the following algorithm design techniques which one is used to find all the pairs of shortest distances in a graph? a) Backtracking b) Greedy c) Dynamic programming d) Divide 3. Which of the following standard algorithms is not Dynamic Programming based. a) Bellman Ford Algorithm for single source shortest path b) Floyd Warshall Algorithm for all pairs shortest paths c) 0-1 Knapsack problem d) Prim’s Minimum Spanning Tree 4. Which of the following does not belongs to the same algorithm paradigm which the others belong to a) Minimum and Maximum Problem b) Knapsack Problem c) Selection Problem d) Merge Sort www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 30 5. Time complexity of Bellman Ford is b) O(V log V) a) O(n) d) O(log V) c) O(1) b) O(log V) 6. Time complexity of Floyed’s is d) O(log n) a) O(V^3) c) O(V^2) Answers:1)-b 2)-c 3)-d 4)-d 5)-b 6)-c www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

SUMMARY 31 This presentation includes unit 8 and 9. This unit is based on dynamic approach to design algorithms. First of all there is all pair shortest path algorithm. Floyd-Warshall algorithm is used to find all pair shortest path problem from a given weighted graph. And then in travelling salesperson problem is to find the shortest rout with covering of all vertices. Warshall algorithm is used to solve transitive closure of any graph. Optimal Binary search tree is used to find the binary tree with minimum cost. Multistage graph is one of the most famous graph problem which can be solved using dynamic approach. www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 32 Q1. Discuss Dynamic general method. Ans. This is an optimization technique at global level. For Further details please refer to the SLM Q2. Design an optimal binary search tree for any graph. Ans. Go through previous slides to calculate the code. For Further details please refer to the SLM Q3. Discuss about knapsack problem. Ans. In this problem we need to pick maximum profit with limited knapsack capacity. For Further details please refer to the SLM www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

REFRENCES 33 1) Data Structures and Algorithms made easy By Narasimha Karumanchi. 2) The Algorithm Design Manual, 2nd Edition by Steven S Skiena 3) Fundamentals of Computer Algorithms - Horowitz and Sahani 4) https://stackoverflow.com/questions/16690249/what-is-the-difference-between-dynamic-programming-and- greedy-approach 5) https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/ www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL

34 THANK YOU www.cuidol.in Unit-8-9(MCA 632) All right are reserved with CU-IDOL