ANALYSIS AND DESIGN OF ALGORITHMS- Graphs

ANALYSIS AND DESIGN OF ALGORITHMS

1. MVJ19CS42 – ANALYSIS AND DESIGN OF ALGORITHMS Module 4 Semester – II Academic Year : 2020-2021(EVEN) By SUGUNADEVI C

2. PREREQUISITES: BASIC KNOWLEDGE ABOUT ANALYSIS AND DESIGN OF ALGORITHMS BRIDGE MATERIAL : Algorithm is a sequence of steps to solve a problem. Design and Analysis of Algorithm is very important for designing algorithm to solve different types of problems. As the speed of processor increases, performance is frequently said to be less central than other software quality characteristics (e.g. security, extensibility, reusability etc.).

3. COURSE OBJECTIVE IS TO: Identify the importance of different asymptotic notation. Determine the complexity of recursive and non-recursive algorithms. Compare the efficiency of various design techniques like greedy method, backtracking etc. Apply appropriate method to solve a given problem. COURSE OUTCOMES : Describe the need of algorithm and the notations used in design analysis. Compare the efficiency of brute force, divide and conquer techniques for problem solving. Ability to apply greedy algorithms, hashing and string matching algorithms Ability to design efficient algorithms using various design techniques

4. Module - 4 Dynamic Programming: General method with Examples, Multistage Graphs. Transitive Closure: Warshall's Algorithm, All Pairs Shortest Paths: Floyd's Algorithm, Optimal Binary Search Trees, Knapsack problem, Bellman-Ford Algorithm , Travelling Sales Person problem , Reliability design. Laboratory Sessions/ Experimental learning: Solving real time problems using Dynamic Programming. Applications: Computer Networks . Video link: https://nptel.ac.in/courses/106/106/106106131/

5. Dynamic programming is a technique for solving problems with overlapping subproblems . subproblems arise from a recurrence relating a given problem’s solution to solutions of its smaller subproblems . DP suggests solving each of the smaller subproblems only once and recording the results in a table from which a solution to the original problem can then be obtained. The Dynamic programming can be used when the solution to a problem can be viewed as the result of sequence of decisions .

6. Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems. Let’s take the example of the  Fibonacci numbers . As we all know, Fibonacci numbers are a series of numbers in which each number is the sum of the two preceding numbers. The first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, and 8, and they continue on from there. If we are asked to calculate the nth Fibonacci number, we can do that with the following equation,

7. As we can clearly see here, to solve the overall problem (i.e.  Fib(n) ), we broke it down into two smaller subproblems (which are  Fib(n-1)  and  Fib(n-2) ). This shows that we can use DP to solve this problem. Fib(n) = Fib(n-1) + Fib(n-2), for n > 1

8. Applications of dynamic programming 0/1 knapsack problem Mathematical optimization problem All pair Shortest path problem Reliability design problem Longest common subsequence (LCS) Flight control and robotics control Time-sharing: It schedules the job to maximize CPU usage

9. EXAMPLE 1 Coin- rowproblem There is a row of n coins whose values are some positive integers c 1 , c 2 , . . . , cn , not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up. Let F(n) be the maximum amount that can be picked up from the row of n coins. To derive a recurrence for F(n), we partition all the allowed coin selections into two groups: those that include the last coin and those without it. The largest amount we can get from the first group is equal to c n + F(n − 2 ) —the value of the n th coin plus the maximum amount we can pick up from the first n − 2 coins. The maximum amount we can get from the second group is equal to F(n − 1 ) by the definition of F(n). Thus, we have the following recurrence subject to the obvious initial conditions:

10. Coin Row Problem :  Coin- rowproblem There is a row of n coins whose values are some positive integers c1, c2, . . . , cn , not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up. Or in other words There is an integer array consisting positive numbers only. Find maximum possible sum of elements such that there are no 2 consecutive elements present in the sum. For ex: Coins[] = {5, 22, 26, 15, 4, 3,11} Max Sum = 22 + 15 + 11 = 48

11. To solve this problem using Dynamic Programming first we will have to define recurrence relation. Let F[n] is the array which will contain the maximum sum at n for any given n. The recurrence relation will be. F(n) = max{Coins[n] + F[n − 2], F[n − 1]} for n > 1, F(0) = 0, F(1) = Coins[1]. This is very easy to understand. While calculating F[n] we are taking maximum of coins[n]+the previous of preceding element and the previous element. For example F[2] = max{coins[0]+ F[2-2], F[2-1]} // No consecutive

12. Coins: C2, C4, C6; Value = 23

13. Coins: C1, C3, C5; Value = 24

14. Example 3:

15. To find the coins with the maximum total value found, we need to backtrace the computations to see which of the two possibilities— c n + F(n − 2 ) or F(n − 1 ) —produced the maxima in formula Thus, the optimal solution is { c 1 , c 4 , c 6 }. .

16. Change-making problem

17. Coin change problem: In the coin change problem, we are basically provided with coins with different denominations like Rs.1, Rs.5 and Rs.10. Now, we have to make an amount by using these coins such that a minimum number of coins are used. Let's take a case of making Rs.10 using these coins, we can do it in the following ways: Using 1 coin of Rs.10 Using two coins of Rs.5 Using one coin of Rs.5 and 5 coins of Rs.1 Using 10 coins of Rs.1

18. Change-making problem Consider the general instance of the following well-known problem. Give change for amount n using the minimum number of coins of denominations d 1 <d 2 < . . .<dm. we consider a dynamic programming algorithm for the general case, assuming availability of unlimited quantities of coins for each of the m denominations d 1 < d 2 < . . . < dm where d 1 = 1.

19. Out of these 4 ways of making Rs.10, we can see that the first way of using only one coin of Rs.10 requires the least number of coins and thus it is our solution. So in a coin change problem, we are provided with different denominations of coins: Now, we have to make change for the value n using these coins and we need to find out the minimum number of coins required to make this change

20. Suppose, we have picked a coin with value x and we know that this coin is going to be in the solution. So, our next task is to find the minimum number of coins needed to make the change of value n-x i.e., Also, by choosing the coin with value x, we have already increased the total number of coins needed by 1. So, we can write:

21. Let F(n) be the minimum number of coins whose values add up to n ; it is convenient to define F( ) = 0 . The amount n can only be obtained by adding one coin of denomination d j to the amount n − d j for j = 1 , 2 , . . . , m such that n ≥ d j . Therefore, we can consider all such denominations and select the one minimizing F(n − d j ) + 1 . Since 1 is a constant, we can, of course, find the smallest F(n − d j ) first and then add 1 to it. Hence, we have the following recurrence for F(n) :

22. Thus, the minimum-coin set for n = 6 is two 3’s . Example:

23. The time and space efficiencies of the algorithm are obviously O(nm) and (n).

24. Coin-collecting problem: Several coins are placed in cells of an n × m board, no more than one coin per cell. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location. When the robot visits a cell with a coin, it always picks up that coin. Design an algorithm to find the maximum number of coins the robot can collect and a path it needs to follow to do this.

25. Let F( i , j) be the largest number of coins the robot can collect and bring to the cell ( i , j ) in the i th row and j th column of the board. It can reach this cell either from the adjacent cell ( i − 1 , j) above it or from the adjacent cell ( i , j − 1 ) to the left of it. The largest numbers of coins that can be brought to these cells are F( i − 1 , j) and F( i , j − 1 ) , respectively. Of course, there are no adjacent cells above the cells in the first row, and there are no adjacent cells to the left of the cells in the first column. For those cells, we assume that F( i − 1, j) and F( i , j − 1) are equal to 0 for their nonexistent neighbors. Therefore, the largest number of coins the robot can bring to cell ( i , j ) is the maximum of these two numbers plus one possible coin at cell ( i , j ) itself.

26. In other words, we have the following formula for F( i , j) : where c ij = 1 if there is a coin in cell ( i , j ), and c ij = 0 otherwise. Using these formulas, we can fill in the n × m table of F( i , j) values either row by row or column by column, as is typical for dynamic programming algorithms involving two-dimensional tables.

27. Dynamic Programming is an algorithm design method that can be used when the solution to a problem may be viewed as the result of a sequence of decisions.(or) Dynamic programming is an optimization approach that divides the complex problems into the simple sequences of problems in which they are interrelated leading to decisions. A  Multistage graph  is a directed graph in which the nodes can be divided into a set of stages such that all edges are from a stage to next stage only (In other words there is no edge between vertices of same stage and from a vertex of current stage to previous stage). We are give a multistage graph, a source and a destination, we need to find shortest path from source to destination. By convention, we consider source at stage 1 and destination as last stage. Multistage graph using Dynamic Programming Approach  

28. Let G=(V,E) be a directed graph. In this we divide the problem into no. of stages or multiple stages then we try to solve whole problem. Multistage graph problem is to determine shortest path from source to destination. This can be solved by using either forward or backward approach. In forward approach we will find the path from destination to source, in backward approach we will find the path from source to destination.

29. Multistage graph problem: The multistage graph problem is to find a minimum cost from a source to a sink. A multistage graph is a directed graph having a number of multiple stages, where stages element should be connected consecutively. In this multiple stage graph, there is a vertex whose in degree is   that is known as the source. And the vertex with only one out degree is   is known as the destination vertex. The one end of the multiple stage graphs is at  i  thus the other reaching end is on  i+1  stage. If we denote a graph  G = (V, E)  in which the vertices are partitioned into  K >= 2  disjoints sets,  Vi ,  1 <= I <=K . So that, if there is an edge  < u, v >  from  u  to  v  in E, the  u £Vi  and  v € v (i+1) , for some  I ,  1 <= i <= K . And sets  V1  and  Vk  are such that  |V1| = | Vk | = 1 .

30. A multistage graph G=(V,E) is a directed graph in which the vertices are partitioned into k>=2 disjoint sets Vi, i <= i <=k. The vertex s is source and t is the sink. Let c( i,j ) be the cost of edge . The cost of a path from s to t is the sum of costs of the edges on the path. The multistage graph problem is to find a minimum-cost path from s to t.

31. Cost of node j at stage i to reach terminal node t DP Solution using forward approach Stage number Node

32. V 1 2 3 4 5 6 7 8 9 10 11 12 Cost d

33. V 1 2 3 4 5 6 7 8 9 10 11 12 Cost d

34. V 1 2 3 4 5 6 7 8 9 10 11 12 Cost d

35. V 1 2 3 4 5 6 7 8 9 10 11 12 Cost d

36. V 1 2 3 4 5 6 7 8 9 10 11 12 Cost d

37. V 1 2 3 4 5 6 7 8 9 10 11 12 Cost d

38. V 1 2 3 4 5 6 7 8 9 10 11 12 Cost d

39. V 1 2 3 4 5 6 7 8 9 10 11 12 Cost d

40. An a l y sis Θ( |V| + |E|)

41. Assignment : 3 Question 1: F ind shortest path from source to destination using forward approach

42. Assignment : 3 Question 2: F ind shortest path from source to destination using forward approach

43. Multistage graph  problem is to determine shortest path from source to destination. This can be solved by  using  either forward or  backward approach . In forward  approach  we will find the path from destination to source, in  backward approach  we will find the path from source to destination. B ackward approach

44. Example 1:

45. V S A B C D E F T d Cost

46. V S A B C D E F T d Cost

47. V S A B C D E F T d Cost

48. V S A B C D E F T d Cost

49. V S A B C D E F T d Cost

50. V S A B C D E F T d Cost

51. Warshall's  algorithm uses the adjacency matrix to find the transitive closure of a directed graph.   Transitive closure The  transitive   closure  of a directed graph with  n  vertices can be defined as the  n -by- n   boolean  matrix  T , in which the element in the  i th  row and  j th  column is 1 if there exist a directed path from the  i th  vertex to the  j th  vertex, otherwise it is zero. Warshall's  Algorithm

52. Digraph Adjacency Matrix Transitive Closure

53. Rule for changing zeros in Warshall’s algorithm

54. An a l y sis

55. An a l y sis Its time efficiency is Θ(n 3 ). We can make the algorithm to run faster by treating matrix rows as bit strings and employ the bitwise or operation available in most modern computer languages. Space efficiency – Although separate matrices for recording intermediate results of the algorithm are used, that can be avoided.

56. Floyd Warshall Algorithm-   Floyd Warshall Algorithm is a famous algorithm. It is used to solve All Pairs Shortest Path Problem. It computes the shortest path between every pair of vertices of the given graph. Floyd Warshall Algorithm is an example of dynamic programming approach. Floyd Warshall Algorithm-

57. Floyd Warshall Algorithm-

58. Solution-   Step-01:   Remove all the self loops and parallel edges (keeping the lowest weight edge) from the graph. In the given graph, there are neither self edges nor parallel edges.   Step-02:   Write the initial distance matrix. It represents the distance between every pair of vertices in the form of given weights. For diagonal elements (representing self-loops), distance value = 0. For vertices having a direct edge between them, distance value = weight of that edge. For vertices having no direct edge between them, distance value = ∞.

59. Example : 1 Solve the all-pairs shortest path problem for the given digraph The Cost Matrix: a b c d a b c d

60. The Cost Matrix: a b c d a b c d a b c d a b c d

61. Example : 1 The Cost Matrix: a b c d a b c d a b c d a b c d

62. Example : 1 The Cost Matrix: a b c d a b c d a b c d a b c d

63. Example : 1 The Cost Matrix: a b c d a b c d a b c d a b c d

64. Example : 1 The Cost Matrix: a b c d a b c d a b c d a b c d

65. Example : 1 The Cost Matrix: a b c d a b c d a b c d a b c d

66. Example : 1 The Cost Matrix: a b c d a b c d a b c d a b c d

67. Example : 1 The Cost Matrix: a b c d a b c d a b c d a b c d

68. Analysis:

69. Backward Approach Cost of node j at stage i to from source node s Sample problems

70. cost(4,I) = c(I,L) = 7 cost(4,J) = c(J,L) = 8 cost(4,K) = c(K,L) = 11 cost(3,F) = min { c(F,I) + cost(4,I) | c(F,J) + cost(4,J) } cost(3,F) = min { 12 + 7 | 9 + 8 } = 17 cost(3,G) = min { c(G,I) + cost(4,I) | c(G,J) + cost(4,J) } cost(3,G) = min { 5 + 7 | 7 + 8 } = 12 cost(3,H) = min { c(H,J) + cost(4,J) | c(H,K) + cost(4,K) } cost(3,H) = min { 10 + 8 | 8 + 11 } = 18 cost(2,B) = min { c(B,F) + cost(3,F) | c(B,G) + cost(3,G) | c(B,H) + cost(3,H) } cost(2,B) = min { 4 + 17 | 8 + 12 | 11 + 18 } = 20 cost(2,C) = min { c(C,F) + cost(3,F) | c(C,G) + cost(3,G) } cost(2,C) = min { 10 + 17 | 3 + 12 } = 15 cost(2,D) = min { c(D,H) + cost(3,H) } cost(2,D) = min { 9 + 18 } = 27 cost(2,E) = min { c(E,G) + cost(3,G) | c(E,H) + cost(3,H) } cost(2,E) = min { 6 + 12 | 12 + 18 } = 18 cost(1,A) = min { c(A,B) + cost(2,B) | c(A,C) + cost(2,C) | c(A,D) + cost(2,D) | c(A,E) + cost(2,E) } cost(1,A) = min { 7 + 20 | 6 + 15 | 5 + 27 | 9 + 18 } = 21 Optimal Path: A-C-G-I-L Reused costs are colored!

71. cost(3,D) = c(D,T) = 18 cost(3,E) = c(E,T) = 13 cost(3,F) = c(F,T) = 2 cost(2,A) = min { c(A,D) + cost(3,D) | c(A,E) + cost(3,E) } cost(2,A) = min { 4 + 18 | 11 + 13 } = 22 cost(2,B) = min { c(B,D) + cost(3,D) | c(B,E) + cost(3,E) | c(B,F) + cost(3,F) } cost(2,B) = min { 9 + 18 | 5 + 13 | 16+2 } = 18 cost(2,C) = min { c(C,F) + cost(3,F) } cost(2,C) = min { 2 + 2 } = 4 cost(1,S) = min { c(S,A) + cost(2,A) | c(S,B) + cost(2,B) | c(S,C) + cost(2,C) } cost(1,S) = min { 1 + 22 | 2 + 18 | 5 + 4 } = 9 Optimal Path: S-C-F-L