Algorithm_design&implementation_module3

EXECUTIVE M. TECH IN CLOUD COMPUTING FIRST SEMESTER ALGORITHM: DESIGN & IMPLEMENTATION

Prefix

CONTENT UNIT - 3: Dynamic Programming.............................................................................................4

UNIT-3: DYNAMIC PROGRAMMING IN ALGORITHMS DESIGN & IMPLEMENTATION STRUCTURE 3.0 Learning Objectives 3.1 Introduction 3.2 Principle of Dynamic Programming 3.2.1 Overlapping Subproblems 3.2.2 Optimal Substructure 3.2.3 Examples 3.3 Memorization and Tabulation 3.3.1 Memorization 3.3.2 Tabulation 3.4 Longest Increasing Subsequence 3.4.1 Example 3.5 Optimal Binary Search Trees 3.6 Shortest Paths in a Graph 3.6.1 Bellman-Ford Algorithm 3.6.2 Floyd-Warshall Algorithm 3.7 Conclusion 3.8 Keywords 3.9 Learning Activity 3.10 Unit End Questions 3.11 References 4. Additional Learning material

3.0 LEARNING OBJECTIVES After studying this unit, you will be able to: • Explain the principle of Dynamic Programming • Solve problems using dynamic programming technique • Describe how to find the longest increasing subsequence • Understand the concept of optimal binary search trees • Explain the application of dynamic programming in shortest paths in a graph • Discuss the identification of negative cycles in a graph 3.1 INTRODUCTION Dynamic Programming (DP) is a powerful problem-solving method that is widely used in mathematics, economics, and computer science. The core idea behind dynamic programming is simple: divide a complex problem into simpler subproblems, solve these subproblems, and then combine their solutions to find the solution for the original problem. This approach is particularly useful when the problem at hand has overlapping subproblems. The history of dynamic programming dates back to the 1950s when it was developed by Richard Bellman, an American applied mathematician. His work has revolutionized how we approach optimization and decision-making problems, and to this day, dynamic programming remains a key tool in these areas. The term \"dynamic programming\" itself has an interesting origin. Bellman deliberately chose a name that would be difficult to understand to protect his work from non-technical administrators who might question the value of his research. 3.2 PRINCIPLES OF DYNAMIC PROGRAMMING Dynamic programming is based on two fundamental principles:

3.2.1 Overlapping Subproblems The principle of overlapping subproblems is based on the observation that many problems share subproblems. In other words, the same subproblem will need to be solved multiple times during the computation of the solution to a larger problem. By saving the result of a subproblem the first time it is solved, dynamic programming avoids redundant work when the same subproblem arises again. For instance, consider the Fibonacci sequence, where each number is the sum of the two preceding ones. If we were to compute the Fibonacci sequence traditionally, we would end up recalculating some parts of the sequence multiple times. However, using dynamic programming, we can calculate each element of the sequence only once and store the results in an array for later use, saving computation time. 3.2.2 Optimal Substructure Optimal substructure is a condition that states that the optimal solution to a problem can be constructed from the optimal solutions of its subproblems. In other words, if a problem can be solved by combining optimal solutions to non-overlapping subproblems, then it has the property of optimal substructure. Take, for example, the problem of finding the shortest path between two nodes in a graph. This problem has an optimal substructure because the shortest path between two nodes can be found by finding the shortest path to each of the intermediate nodes and then choosing the shortest of those paths. Let's look at the Fibonacci sequence as a simple example of using dynamic programming. The Fibonacci sequence is defined as:

Fibonacci(0) = 0 Fibonacci(1) = 1 Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) for n > 1 Using a recursive solution, we could write the Fibonacci sequence as follows: def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2) The problem with this solution is that it does a lot of repeated work. For example, to compute fibonacci(5), it first computes fibonacci(4) and fibonacci(3). To compute fibonacci(4), it computes fibonacci(3) and fibonacci(2). Notice that fibonacci(3) is being computed twice. We can avoid this repeated work by using dynamic programming. We can store the result of each Fibonacci number as we compute it and then use the stored values to compute the next Fibonacci number. Here's how we can do it: def fibonacci(n): fib_values = [0, 1] + [0] * (n-1) for i in range(2, n+1): fib_values[i] = fib_values[i-1] + fib_values[i-2] return fib_values[n]

3.3 MEMORIZATION & TABULATION Memorization and tabulation are two fundamental techniques used in dynamic programming: 3.3.1 Memorization Memorization is a top-down approach where we break down a problem into subproblems, solve the subproblems, and store their solutions in a data structure such as an array or a hash map. This data structure acts as a \"memory\" that remembers the solutions to the subproblems. When a subproblem is encountered again, its solution is simply looked up in the memory instead of being computed again. This avoids redundant work and helps speed up the algorithm. For instance, consider again the Fibonacci sequence. A simple recursive function for calculating Fibonacci numbers will end up doing a lot of redundant work because it will calculate the same Fibonacci numbers multiple times. However, we can avoid this redundancy by using a memoization table. 3.3.2 Tabulation Tabulation, on the other hand, is a bottom-up approach. Here, we start with the simplest subproblem and gradually build up to the original, larger problem. Just like in memoization, we store the results of the subproblems in a table. However, in tabulation, the table is filled up systematically, ensuring that the solution to a subproblem is computed before it is needed for solving larger subproblems. 3.4 LONGEST INCREASING SUBSEQUENCE One classical problem that can be solved with dynamic programming is finding the Longest Increasing Subsequence (LIS) in a given sequence of numbers. A subsequence is a sequence

that appears in the same order but not necessarily contiguous in the original sequence. An increasing subsequence is one where each element is larger than the previous one. The problem of finding the LIS can be defined as follows: Given a sequence of n numbers, find the length of the longest increasing subsequence. For instance, consider the sequence [5, 8, 3, 7, 9, 1]. In this case, the LIS would be [5, 8, 7, 9] and its length would be 4. This problem can be solved using dynamic programming by realizing that the LIS ending at each position in the sequence can be calculated from the LIS of the positions before it. Specifically, if we let LIS[i] denote the length of the LIS ending at position i, then we have the following recursive formula for calculating LIS[i]: LIS[i] = 1 + max(LIS[j]) for all j < i such that sequence[j] < sequence[i]. That is, the length of the LIS ending at position i is one more than the maximum length of the LIS ending at any position before i where the corresponding element in the sequence is smaller than the element at position i. This problem exhibits the properties of overlapping subproblems and optimal substructure, and therefore can be solved efficiently with dynamic programming. 3.4.1 Example The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. Let's say we have the following sequence: A = [5, 7, 3, 8, 4, 2, 9, 6] The longest increasing subsequence in this case is [5, 7, 8, 9] and its length is 4. Here's a simple dynamic programming solution to this problem: def longest_increasing_subsequence(A):

n = len(A) # Initialize LIS values for all indexes lis = [1] * n # Compute optimized LIS values in bottom up manner for i in range (1, n): for j in range(0, i): if A[i] > A[j] and lis[i]< lis[j] + 1 : lis[i] = lis[j]+1 # Initialize maximum to 0 to get the maximum of all LIS maximum = 0 # Pick maximum of all LIS values for i in range(len(lis)): maximum = max(maximum, lis[i]) return maximum Gere's a Python program that uses dynamic programming to solve the Longest Common Subsequence problem for the two strings \"ABCBDAB\" and \"BDCAB\": def longest_common_subsequence(X , Y): m = len(X) n = len(Y)

# Declare a table to store lengths of LCS for subproblems dp = [[None]*(n+1) for i in range(m+1)] # Build the dp table from bottom up for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: dp[i][j] = 0 elif X[i-1] == Y[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[m][n] # Driver program to test the above function X = \"ABCBDAB\" Y = \"BDCAB\" print(\"Length of LCS is \", longest_common_subsequence(X, Y)) - A B C BD A B - 0 0 0 0 00 0 0 B 0 0 1 1 11 1 1 D 0 0 1 1 12 2 2 C 0 0 1 2 22 2 2 A 0 1 1 2 22 3 3 B 0 1 2 2 33 3 4 Table 1: Dynamic Programming Table for Longest Common Subsequence (LCS) Problem

This table illustrates the process of solving the Longest Common Subsequence (LCS) problem for the strings \"ABCBDAB\" and \"BDCAB\" using dynamic programming. Each cell in the table represents the length of the LCS for the substrings up to that point. The first row and the first column are initialized to 0 as they represent the case when one of the strings has no characters (i.e., the LCS of a string and an empty string is an empty string, so its length is 0). For the remaining cells, if the corresponding characters in the two strings are the same, the cell value is the diagonal top-left cell value plus one. If the characters are different, the cell value is the maximum of the left cell value or the above cell value. The process fills the table from top to bottom, left to right. The bottom-right cell of the table shows the length of the LCS for the entire strings. In this case, it's 4, which means that the longest common subsequence of \"ABCBDAB\" and \"BDCAB\" has length 4. 3.5 OPTIMAL BINARY SEARCH TREES Another classic problem solved using dynamic programming is creating an optimal binary search tree. A binary search tree (BST) is a tree data structure in which each node has at most two children, referred to as the left child and the right child. For each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater. The cost of searching for an element in a BST depends on the depth of the element. The closer the element is to the root, the less comparisons are needed to find it, and thus, the lower the cost. Therefore, to optimize search operations, we want to build a BST such that elements that are searched for more frequently are closer to the root. The problem can be stated as follows: given a set of n keys with associated probabilities of search (i.e., the probability that a search operation is for that key), build a binary search tree that minimizes the total search cost.

We can define the cost of a BST as the sum of the search costs for each key. The search cost for a key is the depth of the key in the tree, plus one (as the depth of the root is considered 0), multiplied by the probability of search for that key. Dynamic programming offers a systematic way to find the optimal binary search tree. The key idea is to solve the problem for smaller subsets of the keys and use these solutions to find the solution for larger subsets. This approach exploits the fact that the optimal binary search tree of a set of keys contains within it optimal binary search trees for subsets of the keys. Please see the additional learning material at the end of this chapter to learn more about the OBST problem. 3.6 SHORTEST PATHS IN GRAPH Finding the shortest path between two nodes in a graph is another classic problem that can be solved with dynamic programming. In its simplest form, the problem can be stated as follows: Given a graph with weighted edges and two nodes, find the shortest path from one node to the other. One popular algorithm for this problem is Dijkstra's algorithm, which calculates the shortest paths from a single source node to all other nodes in the graph. However, Dijkstra's algorithm has a limitation in that it does not work with graphs that have negative edge weights. For graphs with negative edge weights, the Bellman-Ford algorithm or the Floyd-Warshall algorithm, both of which are dynamic programming algorithms, can be used instead. 3.6.1 Bellman-Ford Algorithm The Bellman-Ford algorithm works by repeatedly relaxing the edges of the graph, which means updating the shortest path estimates of the graph's vertices. The algorithm does this for as many

times as there are vertices in the graph minus one. Each relaxation step ensures that the shortest path estimates for all vertices are at least as accurate as if we only allowed paths of a certain maximum length. The Bellman-Ford algorithm is useful because it can handle graphs with negative edge weights, and it can also detect negative cycles – cycles in the graph whose total edge weight is negative. If such a cycle exists, there is no shortest path, because we can keep going around the negative cycle to decrease the path length. 3.6.2 Floyd-Warshall Algorithm The Floyd-Warshall algorithm is another dynamic programming algorithm for finding shortest paths in a graph. Unlike Dijkstra's algorithm and the Bellman-Ford algorithm, which calculate shortest paths from a single source node, the Floyd-Warshall algorithm computes the shortest paths between all pairs of nodes. The Floyd-Warshall algorithm is based on a simple principle: for any vertices i, j, and k, if the shortest path from i to j goes through k, then the shortest paths from i to k and from k to j are part of the shortest path from i to j. This property is known as the principle of optimality. The algorithm works by systematically examining all paths between all pairs of vertices and updating the shortest path estimates as shorter paths are discovered. Despite its simplicity, the Floyd-Warshall algorithm can handle negative edge weights and is efficient for dense graphs, where the number of edges is close to the maximum possible number of edges. 3.6.3 Example The shortest path problem involves finding the shortest path or paths in a weighted graph (a graph in which each edge has a weight or length).

Let's take a simple graph and apply Dijkstra's algorithm which is a common dynamic programming algorithm for this problem. Suppose we have the following graph: A /\\ 1/ \\6 B----C \\/ 4\\/2 D In this graph, A, B, C, and D are nodes, and the numbers are the costs of the edges. We want to find the shortest path from A to D. Here's how we can do it: 1. We start at node A and mark it as visited. The current shortest path to A is 0 (since we start from A itself). 2. We visit all of A's neighbors (in this case, B and C). The path to B through A is 1, and the path to C through A is 6. We mark these costs as the current shortest paths to B and C, respectively. 3. We visit all of B's unvisited neighbors (C and D). Through B, the path to C is 1 (from A to B) + 2 (from B to C) = 3 which is less than the current cost to C, so we update the shortest path to C. The path to D is 1 (from A to B) + 4 (from B to D) = 5. 4. Since there are no more unvisited neighbors of B, we proceed to the next node with the smallest cost, which is C. Visiting all of C's unvisited neighbors (D), the path to D is 3 (from A to C) + 2 (from C to D) = 5. Since this is not less than the current cost to D, we do not update the cost. 5. Finally, we visit D. Since D has no unvisited neighbors, we've now found the shortest paths to all nodes. 3.7 CONCLUSION

Dynamic programming is a powerful technique that can solve a wide range of problems in computer science and other fields. It is particularly well-suited to optimization problems that exhibit the properties of overlapping subproblems and optimal substructure. While dynamic programming can seem complex and intimidating at first, with practice, you can master it and use it to solve complex problems more efficiently. Remember that the key to dynamic programming is to break down a problem into simpler subproblems, solve these subproblems, and use their solutions to find the solution to the original problem. In this chapter, we have examined the principles of dynamic programming and explored several classical problems that can be solved using this technique. The examples discussed in this chapter should give you a good starting point for understanding how dynamic programming works and how it can be applied to solve various types of problems. Remember, however, that dynamic programming is not a silver bullet. Not all problems can be solved efficiently using dynamic programming, and even for those that can, there may be other approaches that are more appropriate depending on the specific circumstances. Therefore, it is important to understand not only how to use dynamic programming, but also when to use it, and when not to use it. 3.8 KEYWORDS 1. Dynamic Programming: A method for solving a complex problem by breaking it down into simpler subproblems, solving the subproblems just once, and storing their solutions. 2. Subproblems: Smaller parts of the original problem, the solutions to which are used to solve the larger problem. 3. Memorization: A method in dynamic programming for storing the results of expensive function calls and reusing them when the same inputs occur again.

4. Iteration: A procedural method in dynamic programming where a bigger problem's solution is built incrementally from solutions to smaller subproblems. 5. Longest Increasing Subsequence: A subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and where the subsequence is as long as possible. 6. Optimal Binary Search Trees: A binary search tree where the total cost of searching all elements is the lowest. 7. Shortest Paths in a Graph: Finding a path between two vertices or nodes in a graph such that the sum of the weights of its constituent edges is minimized. 8. Negative Cycles in a Graph: A cycle in a weighted graph where the sum of the weights of its edges is negative. 3.9 LEARNING ACTIVITY 1. Try implementing the algorithms discussed in this unit using a programming language of your choice. 2. Given a sequence of numbers, find the longest increasing subsequence using dynamic programming. 3. Given a set of keys with their frequencies, design an optimal binary search tree. 4. Consider a weighted graph. Try implementing the shortest path algorithm using dynamic programming. 5. Explore real-life applications of dynamic programming and discuss how it improves efficiency in those scenarios. 3.10 UNIT END QUESTIONS 1. What is dynamic programming and how does it differ from other problem-solving techniques? 2. Explain the concept of \"subproblems\" and their role in dynamic programming. 3. Discuss the steps involved in designing a dynamic programming algorithm. 4. Explain with an example how to find the longest increasing subsequence in a given sequence of numbers. 5. How does dynamic programming help in designing an optimal binary search tree?

6. Discuss the role of dynamic programming in finding shortest paths in a graph. 7. What are negative cycles in a graph and how can they be detected using dynamic programming? 3.11 REFERENCES 1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT press. 2. Bellman, R. (1957). Dynamic Programming. Princeton University Press. 3. Knuth, D. E. (1971). Optimum binary search trees. Acta Informatica, 1(1), 14-25. 4. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. 5. Floyd, R. W. (1962). Algorithm 97: shortest path. Communications of the ACM, 5(6), 345. 4. ADDITIONAL LEARNING MATERIAL Sure, here are some useful resources to learn dynamic programming and related concepts: 1. GeeksforGeeks: • Dynamic Programming: https://www.geeksforgeeks.org/dynamic-programming/ • Longest Increasing Subsequence: https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

• Optimal Binary Search Trees: https://www.geeksforgeeks.org/optimal-binary- search-tree-dp-24/ • Shortest Paths in a Graph (Dijkstra’s Algorithm): https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo- 7/ • Negative Cycles in a Graph (Bellman–Ford Algorithm): 2. Codecademy: • Introduction to Algorithms: https://www.codecademy.com/learn/introduction-to-algorithms 3. MIT OpenCourseWare: • Design and Analysis of Algorithms: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6- 046j-design-and-analysis-of-algorithms-spring-2015/ These resources provide comprehensive coverage on dynamic programming and related topics, and include practice problems that help reinforce understanding of these topics.