Part 2 - Design Strategies PDF

CEF405 - Design & Analysis of Algorithms Department of Computer Engineering Faculty of Engineering & Technology Part II: Design Strategies 6- Divide and Conquer Applications: Max-Min Problem Merge...

CEF405 - Design & Analysis of Algorithms Department of Computer Engineering Faculty of Engineering & Technology Part II: Design Strategies 6- Divide and Conquer Applications: Max-Min Problem Merge Sort Binary Search Strassen’s Matrix Multiplication 7- Greedy Method Applications: Fractional Knapsack Job Sequencing with Deadline Optimal Merge Pattern 8- Dynamic Programming Applications: 0-1 Knapsack Longest Common Subsequence Course master: Dr TSAGUE A. 14  6. Divide & ConquerDesign & Analysis of Algorithms Many algorithms are recursive in nature to solve a given problem recursively dealing with sub-problems. In divide and conquer approach, a problem is divided into smaller problems, then the smaller problems are solved independently, and finally the solutions of smaller problems are combined into a solution for the large problem. Generally, divide-and-conquer algorithms have three parts:  Divide the problem into a number of sub-problems that are smaller instances of the same problem.  Conquer the sub-problems by solving them recursively. If they are small enough, solve the sub-problems as base cases.  Combine the solutions to the sub-problems into the solution for the original problem. Pros and cons of Divide and Conquer Approach Divide and conquer approach supports parallelism as sub-problems are independent. Hence, an algorithm, which is designed using this technique, can run on the multiprocessor system or in different machines simultaneously. In this approach, most of the algorithms are designed using recursion, hence memory management is very high. For recursive function stack is used, where function state needs to be stored. Application of Divide and Conquer Approach Following are some problems, which are solved using divide and conquer approach.  Finding the maximum and minimum of a sequence of numbers  Strassen’s matrix multiplication  Merge sort  Binary search 15  6.1 Max-Min Problem Design & Analysis of Algorithms Let us consider a simple problem that can be solved by divide and conquer technique. Problem Statement The Max-Min Problem in algorithm analysis is finding the maximum and minimum value in an array. Solution To find the maximum and minimum numbers in a given array 𝒏𝒖𝒎𝒃𝒆𝒓𝒔[] of size n, the following algorithm can be used. First we are representing the naive method and then we will present divide and conquer approach. Naïve Method Naïve method is a basic method to solve any problem. In this method, the maximum and minimum number can be found separately. To find the maximum and minimum numbers, the following straightforward algorithm can be used. Algorithm: Max-Min-Element (numbers[]) max := numbers min := numbers for i = 2 to n do if numbers[i] > max then max := numbers[i] if numbers[i] < min then min := numbers[i] return (max, min) Analysis The number of comparison in Naive method is 𝟐𝒏 − 𝟐. The number of comparisons can be reduced using the divide and conquer approach. Following is the technique. Divide and Conquer Approach In this approach, the array is divided into two halves. Then using recursive approach maximum and minimum numbers in each halves are found. Later, return the maximum of two maxima of each half and the minimum of two minima of each half. 16  Design & Analysis of Algorithms In this given problem, the number of elements in an array is 𝒚 − 𝒙 + 𝟏, where y is greater than or equal to x. 𝑴𝒂𝒙 − 𝑴𝒊𝒏(𝒙, 𝒚) will return the maximum and minimum values of an array 𝒏𝒖𝒎𝒃𝒆𝒓𝒔[𝒙 … 𝒚]. Algorithm: Max-Min(x, y) if x –y ≤ 1 then return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) else (max1, min1):= maxmin(x, ⌊((x+y)/2)⌋) (max2, min2):= maxmin(⌊((x+y)/2) + 1)⌋,y) return (max(max1, max2), min(min1, min2)) Analysis Let 𝑇(𝑛) be the number of comparisons made by 𝑴𝒂𝒙 − 𝑴𝒊𝒏(𝒙, 𝒚), where the number of elements 𝒏 = 𝒚 – 𝒙 + 𝟏. If 𝑻(𝒏) represents the numbers, then the recurrence relation can be represented as: 𝒏 𝒏 𝑻 (⌊ ⌋) + 𝑻 (⌈ ⌉) + 𝟐 𝐟𝐨𝐫 𝒏 > 𝟐 𝑻(𝒏) = { 𝟐 𝟐 𝟏 𝐟𝐨𝐫 𝒏 = 𝟐 𝟎 𝐟𝐨𝐫 𝒏 = 𝟏 Let us assume that n is in the form of power of 2. Hence, 𝒏 = 𝟐𝒌 where k is height of the recursion tree. So, 𝒏 𝒏 𝟑𝒏 𝑻(𝒏) = 𝟐. 𝑻 ( ) + 𝟐 = 𝟐. (𝟐. 𝑻 ( ) + 𝟐) + 𝟐 ….. = −𝟐 𝟐 𝟒 𝟐 Compared to Naïve method, in divide and conquer approach, the number of comparisons is less. However, using the asymptotic notation both of the approaches are represented by 𝑶(𝒏). 17  6.2 Merge Sort Design & Analysis of Algorithms In this section, we will discuss merge sort and analyze its complexity. Problem Statement The problem of sorting a list of numbers lends itself immediately to a divide-and-conquer strategy: split the list into two halves, recursively sort each half, and then merge the two sorted sub-lists. Solution In this algorithm, the numbers are stored in an array numbers[]. Here, p and q represents the start and end index of a sub-array. Algorithm: Merge-Sort (numbers[], p, r) if p < r then q = ⌊(p + q) / 2⌋ Merge-Sort (numbers[], p, q) Merge-Sort (numbers[], q + 1, r) Merge (numbers[], p, q, r) Function: Merge (numbers[], p, q, r) n1 = q – p + 1 n2 = r – q declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays for i = 1 to n1 leftnums[i] = numbers[p + i - 1] for j = 1 to n2 leftnums[j] = numbers[q+ j] leftnums[n1 + 1] = ∞ rightnums[n2 + 1] = ∞ i = 1 j = 1 for k = p to r if leftnums[i] ≤ rightnums[j] numbers[k] = leftnums[i] i = i + 1 else 18  Design & Analysis of Algorithms numbers[k] = rightnums[j] j = j + 1 Analysis Let us consider, the running time of Merge-Sort as 𝑻(𝒏). Hence, 𝒄 𝒊𝒇 𝒏 ≤ 𝟏 𝑻(𝒏) = { 𝒏 where 𝑐 and 𝑑 are constants 𝟐𝒙𝑻( ) +𝒅𝒙𝒏 𝐨𝐭𝐡𝐞𝐫𝐰𝐢𝐬𝐞 𝟐 Therefore, using this recurrence relation, 𝑻(𝒏) = 𝟐𝒊 𝑻(𝒏/𝟐𝒊 ) + 𝒊. 𝒅. 𝒏 As, 𝒊 = 𝒍𝒐𝒈 𝒏, 𝑻(𝒏) = 𝟐𝐥𝐨𝐠 𝒏 𝑻(𝒏/𝟐𝐥𝐨𝐠 𝒏 ) + 𝒍𝒐𝒈 𝒏. 𝒅. 𝒏 = 𝒄. 𝒏 + 𝒅. 𝒏. 𝒍𝒐𝒈 𝒏 Therefore, 𝑻(𝒏) = 𝑶(𝒏 𝒍𝒐𝒈 𝒏 ). Example In the following example, we have shown Merge-Sort algorithm step by step. First, every iteration array is divided into two sub-arrays, until the sub-array contains only one element. When these sub-arrays cannot be divided further, then merge operations are performed. Divide and Merge operations step by step: 32 14 15 27 31 7 23 26 32 14 15 27 31 7 23 26 32 14 15 27 31 7 23 26 32 14 15 27 31 7 23 26 14 32 15 27 7 31 23 26 14 15 27 32 7 23 26 31 7 14 15 23 26 27 31 32 19  6.3 Binary Search Design & Analysis of Algorithms In this section, we will discuss another algorithm based on divide and conquer method. Problem Statement Binary search can be performed on a sorted array. In this approach, the index of an element x is determined if the element belongs to the list of elements. If the array is unsorted, linear search is used to determine the position. Solution In this algorithm, we want to find whether element x belongs to a set of numbers stored in an array numbers[]. Where l and r represent the left and right index of a sub-array in which searching operation should be performed. Algorithm: Binary-Search(numbers[], x, l, r) if l = r then return l else m := ⌊(l + r) / 2⌋ if x ≤ numbers[m] then return Binary-Search(numbers[], x, l, m) else return Binary-Search(numbers[], x, m+1, r) Analysis Linear search runs in 𝑶(𝒏) time. Whereas binary search produces the result in 𝑶(𝒍𝒐𝒈 𝒏) time. Let T(n) be the number of comparisons in worst-case in an array of n elements. Hence, 𝟎 𝒊𝒇 𝒏 = 𝟏 𝑻(𝒏) = { 𝒏 𝑻( )+ 𝟏 𝒐𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆 𝟐 Using this recurrence relation 𝑻(𝒏) = 𝒍𝒐𝒈 𝒏. Therefore, binary search uses 𝑶(𝒍𝒐𝒈 𝒏) time. 20  Design & Analysis of Algorithms Example In this example, we are going to search element 63. 21  6.4 Strassen’s Matrix Multiplication Design & Analysis of Algorithms In this chapter, first we will discuss the general method of matrix multiplication and later we will discuss Strassen’s matrix multiplication algorithm. Problem Statement Let us consider two matrices X and Y. We want to calculate the resultant matrix Z by multiplying X and Y. Naïve Method First, we will discuss naïve method and its complexity. Here, we are calculating 𝒁 = 𝑿 𝒙 𝒀. Using Naïve method, two matrices (X and Y) can be multiplied if the order of these matrices are 𝒑𝒙𝒒 and 𝒒𝒙𝒓. Following is the algorithm. Algorithm: Matrix-Multiplication (X, Y, Z) for i = 1 to p do for j = 1 to r do Z[i,j] := 0 for k = 1 to q do Z[i,j] := Z[i,j] + X[i,k] x Y[k,j] Complexity Here, we assume that integer operations take 𝑶(𝟏) time. There are three for loops in this algorithm and one is nested in other. Hence, the algorithm takes 𝑶(𝒏𝟑 ) time to execute. Strassen’s Matrix Multiplication Algorithm In this context, using Strassen’s Matrix multiplication algorithm, the time consumption can be improved a little bit. Strassen’s Matrix multiplication can be performed only on square matrices where n is a power of 2. Order of both of the matrices are n x n. Divide X, Y and Z into four (𝐧/𝟐)𝐱(𝐧/𝟐) matrices as represented below: 𝑰 𝑱 𝑨 𝑩 𝑬 𝑭 𝒁=[ ] 𝑿=[ ] and 𝒀=[ ] 𝑲 𝑳 𝑪 𝑫 𝑮 𝑯 22  Design & Analysis of Algorithms Using Strassen’s Algorithm compute the following: 𝑴𝟏 ∶= (𝑨 + 𝑪) 𝒙 (𝑬 + 𝑭) 𝑴𝟐 ∶= (𝑩 + 𝑫) 𝒙 (𝑮 + 𝑯) 𝑴𝟑 ∶= (𝑨 − 𝑫) 𝒙 (𝑬 + 𝑯) 𝑴𝟒 ∶= 𝑨 𝒙 (𝑭 − 𝑯) 𝑴𝟓 ∶= (𝑪 + 𝑫) 𝒙 𝑬 𝑴𝟔 ∶= (𝑨 + 𝑩) 𝒙 𝑯 𝑴𝟕 ∶= 𝑫 𝒙 (𝑮 – 𝑬) Then, 𝑰 ∶= 𝑴𝟐 + 𝑴𝟑 – 𝑴𝟔 – 𝑴𝟕 𝑱 ∶= 𝑴𝟒 + 𝑴𝟔 𝑲 ∶= 𝑴𝟓 + 𝑴𝟕 𝑳 ∶= 𝑴𝟏 – 𝑴𝟑 – 𝑴𝟒 – 𝑴𝟓 Analysis 𝑐 𝑖𝑓 𝑛 = 1 𝑇(𝑛) = { 𝑛 where 𝑐 and 𝑑 are constants 7 𝑥 𝑇 ( ) + 𝑑 𝑥 𝑛2 otherwise 2 Using this recurrence relation, we get 𝑻(𝒏) = 𝑶 (𝒏𝐥𝐨𝐠 𝟕 ) Hence, the complexity of Strassen’s matrix multiplication algorithm is 𝑶 (𝒏𝐥𝐨𝐠 𝟕 ). 23  7. Greedy Method Design & Analysis of Algorithms Among all the algorithmic approaches, the simplest and straightforward approach is the Greedy method. In this approach, the decision is taken on the basis of current available information without worrying about the effect of the current decision in future. Greedy algorithms build a solution part by part, choosing the next part in such a way, that it gives an immediate benefit. This approach never reconsiders the choices taken previously. This approach is mainly used to solve optimization problems. Greedy method is easy to implement and quite efficient in most of the cases. Hence, we can say that Greedy algorithm is an algorithmic paradigm based on heuristic that follows local optimal choice at each step with the hope of finding global optimal solution. In many problems, it does not produce an optimal solution though it gives an approximate (near optimal) solution in a reasonable time. Components of Greedy Algorithm Greedy algorithms have the following five components:  A candidate set: A solution is created from this set.  A selection function: Used to choose the best candidate to be added to the solution.  A feasibility function: Used to determine whether a candidate can be used to contribute to the solution.  An objective function: Used to assign a value to a solution or a partial solution.  A solution function: Used to indicate whether a complete solution has been reached. Areas of Application Greedy approach is used to solve many problems, such as  Finding the shortest path between two vertices using Dijkstra’s algorithm.  Finding the minimal spanning tree in a graph using Prim’s /Kruskal’s algorithm, etc. Where Greedy Approach Fails In many problems, Greedy algorithm fails to find an optimal solution, moreover it may produce a worst solution. Problems like Travelling Salesman and Knapsack cannot be solved using this approach. 24  7.1 Fractional Knapsack Design & Analysis of Algorithms The Greedy algorithm could be understood very well with a well-known problem referred to as Knapsack problem. Although the same problem could be solved by employing other algorithmic approaches, Greedy approach solves Fractional Knapsack problem reasonably in a good time. Let us discuss the Knapsack problem in detail. Knapsack Problem Given a set of items, each with a weight and a value, determine a subset of items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. The knapsack problem is in combinatorial optimization problem. It appears as a sub- problem in many, more complex mathematical models of real-world problems. One general approach to difficult problems is to identify the most restrictive constraint, ignore the others, solve a knapsack problem, and somehow adjust the solution to satisfy the ignored constraints. set of items is considered the candidate set Applications In many cases of resource allocation along with some constraint, the problem can be derived in a similar way of Knapsack problem. Following is a set of example.  Finding the least wasteful way to cut raw materials  portfolio optimization  Cutting stock problems Problem Scenario A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are n items available in the store and weight of ith item is wi and its profit is pi. What items should the thief take? In this context, the items should be selected in such a way that the thief will carry those items for which he will gain maximum profit. Hence, the objective of the thief is to maximize the profit. Based on the nature of the items, Knapsack problems are categorized as  Fractional Knapsack  Knapsack 25  Design & Analysis of Algorithms Fractional Knapsack In this case, items can be broken into smaller pieces, hence the thief can select fractions of items. According to the problem statement,  There are n items in the store  Weight of ith item 𝒘𝒊 > 𝟎  Profit for ith item 𝒑𝒊 > 𝟎 and  Capacity of the Knapsack is W In this version of Knapsack problem, items can be broken into smaller pieces. So, the thief may take only a fraction xi of ith item. 𝟎 ≤ 𝒙𝒊 ≤ 𝟏 The ith item contributes the weight 𝒙𝒊. 𝒘𝒊 to the total weight in the knapsack and profit 𝒙𝒊. 𝒑𝒊 to the total profit. Hence, the objective of this algorithm is to 𝒏 𝒎𝒂𝒙𝒊𝒎𝒊𝒛𝒆 ∑(𝒙𝒊. 𝒑𝒊 ) 𝒏=𝟏 subject to constraint, 𝒏 ∑(𝒙𝒊. 𝒘𝒊 ) ≤ 𝑾 𝒏=𝟏 It is clear that an optimal solution must fill the knapsack exactly, otherwise we could add a fraction of one of the remaining items and increase the overall profit. Thus, an optimal solution can be obtained by 𝒏 ∑(𝒙𝒊. 𝒘𝒊 ) = 𝑾 𝒏=𝟏 In this context, first we need to sort those items according to the value of 𝒑𝒊 /𝒘𝒊 , so that 𝒑𝒊+𝟏 𝒑 ≤ 𝒊. Here, x is an array to store the fraction of items. 𝒘𝒊+𝟏 𝒘𝒊 Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) for i = 1 to n do x[i] = 0 weight = 0 for i = 1 to n if weight + w[i] ≤ W then x[i] = 1 26  Design & Analysis of Algorithms weight = weight + w[i] else x[i] = (W - weight) / w[i] weight = W break return x Analysis If the provided items are already sorted into a decreasing order of 𝒑𝒊 /𝒘𝒊 , then the while- loop takes a time in 𝑶(𝒏); Therefore, the total time including the sort is in 𝑶(𝒏 𝒍𝒐𝒈 𝒏). Example Let us consider that the capacity of the knapsack 𝑾 = 𝟔𝟎 and the list of provided items are shown in the following table: Item A B C D Profit 280 100 120 120 Weight 40 10 20 24 𝒑𝒊 Ratio ( ) 7 10 6 5 𝒘𝒊 As the provided items are not sorted based on pi / wi. After sorting, the items are as shown in the following table. Item B A C D Profit 100 280 120 120 Weight 10 40 20 24 𝒑 Ratio (𝒘𝒊 ) 10 7 6 5 𝒊 Solution After sorting all the items according to 𝒑𝒊 /𝒘𝒊. First all of B is chosen as weight of B is less than the capacity of the knapsack. Next, item A is chosen, as the available capacity of the knapsack is greater than the weight of A. Now, C is chosen as the next item. However, the whole item cannot be chosen as the remaining capacity of the knapsack is less than the weight of C. Hence, fraction of C (i.e. (60 − 50)/20) is chosen. 27  Design & Analysis of Algorithms Now, the capacity of the Knapsack is equal to the selected items. Hence, no more item can be selected. The total weight of the selected items is 𝟏𝟎 + 𝟒𝟎 + 𝟐𝟎 ∗ (𝟏𝟎/𝟐𝟎) = 𝟔𝟎 And the total profit is 𝟏𝟎𝟎 + 𝟐𝟖𝟎 + 𝟏𝟐𝟎 ∗ (𝟏𝟎/𝟐𝟎) = 𝟑𝟖𝟎 + 𝟔𝟎 = 𝟒𝟒𝟎 This is the optimal solution. We cannot gain more profit selecting any different combination of items. 28  7.2 Job Sequencing with Deadline Design & Analysis of Algorithms Problem Statement In job sequencing problem, the objective is to find a sequence of jobs, which is completed within their deadlines and gives maximum profit. Solution Let us consider, a set of n given jobs which are associated with deadlines and profit is earned, if a job is completed by its deadline. These jobs need to be ordered in such a way that there is maximum profit. It may happen that all of the given jobs may not be completed within their deadlines. Assume, deadline of ith job Ji is di and the profit received from this job is pi. Hence, the optimal solution of this algorithm is a feasible solution with maximum profit. Thus, 𝑫(𝒊) > 𝟎 for 𝟏 ≤ 𝒊 ≤ 𝒏. Initially, these jobs are ordered according to profit, i.e. 𝒑𝟏 ≥ 𝒑𝟐 ≥ 𝒑𝟑 ≥ … ≥ 𝒑𝒏. Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) D(0) := J(0) := 0 k := 1 J(1) := 1 // means first job is selected for i = 2 … n do r := k while D(J(r)) > D(i) and D(J(r)) ≠ r do r := r – 1 if D(J(r)) ≤ D(i) and D(i) > r then for l = k … r + 1 by -1 do J(l + 1) := J(l) J(r + 1) := i k := k + 1 Analysis In this algorithm, we are using two loops, one is within another. Hence, the complexity of this algorithm is 𝑶(𝒏𝟐 ). 29  Design & Analysis of Algorithms Example Let us consider a set of given jobs as shown in the following table. We have to find a sequence of jobs, which will be completed within their deadlines and will give maximum profit. Each job is associated with a deadline and profit. Job J1 J2 J3 J4 J5 Deadline 2 1 3 2 1 Profit 60 100 20 40 20 Solution To solve this problem, the given jobs are sorted according to their profit in a descending order. Hence, after sorting, the jobs are ordered as shown in the following table. Job J2 J1 J4 J3 J5 Deadline 1 2 2 3 1 Profit 100 60 40 20 20 From this set of jobs, first we select J2, as it can be completed within its deadline and contributes maximum profit.  Next, J1 is selected as it gives more profit compared to J4.  In the next clock, J4 cannot be selected as its deadline is over, hence J3 is selected as it executes within its deadline.  The job J5 is discarded as it cannot be executed within its deadline. Thus, the solution is the sequence of jobs (J2, J1, J4), which are being executed within their deadline and gives maximum profit. Total profit of this sequence is 𝟏𝟎𝟎 + 𝟔𝟎 + 𝟐𝟎 = 𝟏𝟖𝟎. 30  7.3 Optimal Merge Pattern Design & Analysis of Algorithms Merge a set of sorted files of different length into a single sorted file. We need to find an optimal solution, where the resultant file will be generated in minimum time. If the number of sorted files are given, there are many ways to merge them into a single sorted file. This merge can be performed pair wise. Hence, this type of merging is called as 2-way merge patterns. As, different pairings require different amounts of time, in this strategy we want to determine an optimal way of merging many files together. At each step, two shortest sequences are merged. To merge a p-record file and a q-record file requires possibly 𝐩 + 𝐪 record moves, the obvious choice being, merge the two smallest files together at each step. Two-way merge patterns can be represented by binary merge trees. Let us consider a set of n sorted files {f1, f2, f3, …, fn}. Initially, each element of this is considered as a single node binary tree. To find this optimal solution, the following algorithm is used. Algorithm: TREE (n) for i := 1 to n – 1 do declare new node node.leftchild := least (list) node.rightchild := least (list) node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight) insert (list, node); return least (list); At the end of this algorithm, the weight of the root node represents the optimal cost. Example Let us consider the given files, f1, f2, f3, f4 and f5 with 20, 30, 10, 5 and 30 number of elements respectively. If merge operations are performed according to the provided sequence, then M1 = merge f1 and f2 => 𝟐𝟎 + 𝟑𝟎 = 𝟓𝟎 M2 = merge M1 and f3 => 𝟓𝟎 + 𝟏𝟎 = 𝟔𝟎 M3 = merge M2 and f4 => 𝟔𝟎 + 𝟓 = 𝟔𝟓 M4 = merge M3 and f5 => 𝟔𝟓 + 𝟑𝟎 = 𝟗𝟓 Hence, the total number of operations is 𝟓𝟎 + 𝟔𝟎 + 𝟔𝟓 + 𝟗𝟓 = 𝟐𝟕𝟎 31  Design & Analysis of Algorithms Now, the question arises is there any better solution? Sorting the numbers according to their size in an ascending order, we get the following sequence: f4, f3, f1, f2, f5 Hence, merge operations can be performed on this sequence M1 = merge f4 and f3 => 𝟓 + 𝟏𝟎 = 𝟏𝟓 M2 = merge M1 and f1 => 𝟏𝟓 + 𝟐𝟎 = 𝟑𝟓 M3 = merge M2 and f2 => 𝟑𝟓 + 𝟑𝟎 = 𝟔𝟓 M4 = merge M3 and f5 => 𝟔𝟓 + 𝟑𝟎 = 𝟗𝟓 Therefore, the total number of operations is 𝟏𝟓 + 𝟑𝟓 + 𝟔𝟓 + 𝟗𝟓 = 𝟐𝟏𝟎 Obviously, this is better than the previous one. In this context, we are now going to solve the problem using this algorithm. Initial Set 5 10 20 30 30 Step-1 15 20 30 30 5 10 Step-2 35 30 30 15 20 5 10 32  Design & Analysis of Algorithms Step-3 35 60 15 20 30 30 5 10 Step-4 95 35 60 15 20 30 30 5 10 Hence, the solution takes 15 + 35 + 60 + 95 = 205 number of comparisons. 33  8. Dynamic Programming Design & Analysis of Algorithms Dynamic Programming is also used in optimization problems. Like divide-and-conquer method, Dynamic Programming solves problems by combining the solutions of sub- problems. Moreover, Dynamic Programming algorithm solves each sub-problem just once and then saves its answer in a table, thereby avoiding the work of re-computing the answer every time. Two main properties of a problem suggest that the given problem can be solved using Dynamic Programming. These properties are overlapping sub-problems and optimal substructure. Overlapping Sub-Problems Similar to Divide-and-Conquer approach, Dynamic Programming also combines solutions to sub-problems. It is mainly used where the solution of one sub-problem is needed repeatedly. The computed solutions are stored in a table, so that these don’t have to be re-computed. Hence, this technique is needed where overlapping sub-problem exists. For example, Binary Search does not have overlapping sub-problem. Whereas recursive program of Fibonacci numbers have many overlapping sub-problems. Optimal Sub-Structure A given problem has Optimal Substructure Property, if the optimal solution of the given problem can be obtained using optimal solutions of its sub-problems. For example, the Shortest Path problem has the following optimal substructure property: If a node x lies in the shortest path from a source node u to destination node v, then the shortest path from u to v is the combination of the shortest path from u to x, and the shortest path from x to v. The standard All Pair Shortest Path algorithms like Floyd-Warshall and Bellman-Ford are typical examples of Dynamic Programming. Steps of Dynamic Programming Approach Dynamic Programming algorithm is designed using the following four steps:  Characterize the structure of an optimal solution.  Recursively define the value of an optimal solution.  Compute the value of an optimal solution, typically in a bottom-up fashion.  Construct an optimal solution from the computed information. Applications of Dynamic Programming Approach  Matrix Chain Multiplication  Longest Common Subsequence  Travelling Salesman Problem 34  8.1 0-1 Knapsack Design & Analysis of Algorithms In this 2nd part , earlier we have discussed Fractional Knapsack problem using Greedy approach. We have shown that Greedy approach gives an optimal solution for Fractional Knapsack. However, this chapter will cover 0-1 Knapsack problem and its analysis. In 0-1 Knapsack, items cannot be broken which means the thief should take the item as a whole or should leave it. This is reason behind calling it as 0-1 Knapsack. Hence, in case of 0-1 Knapsack, the value of xi can be either 0 or 1, where other constraints remain the same. 0-1 Knapsack cannot be solved by Greedy approach. Greedy approach does not ensure an optimal solution. In many instances, Greedy approach may give an optimal solution. The following examples will establish our statement. Example-1 Let us consider that the capacity of the knapsack is W = 25 and the items are as shown in the following table. Item A B C D Profit 24 18 18 10 Weight 24 10 10 7 Without considering the profit per unit weight (𝒑𝒊 /𝒘𝒊 ), if we apply Greedy approach to solve this problem, first item A will be selected as it will contribute maximum profit among all the elements. After selecting item A, no more item will be selected. Hence, for this given set of items total profit is 24. Whereas, the optimal solution can be achieved by selecting items, B and C, where the total profit is 18 + 18 = 36. Example-2 Instead of selecting the items based on the overall benefit, in this example the items are selected based on ratio 𝒑𝒊 /𝒘𝒊. Let us consider that the capacity of the knapsack is 𝑊 = 30 and the items are as shown in the following table. Item A B C Price 100 280 120 Weight 10 40 20 Ratio 10 7 6 35  Design & Analysis of Algorithms Using the Greedy approach, first item A is selected. Then, the next item B is chosen. Hence, the total profit is 𝟏𝟎𝟎 + 𝟐𝟖𝟎 = 𝟑𝟖𝟎. However, the optimal solution of this instance can be achieved by selecting items, B and C, where the total profit is 𝟐𝟖𝟎 + 𝟏𝟐𝟎 = 𝟒𝟎𝟎. Hence, it can be concluded that Greedy approach may not give an optimal solution. To solve 0-1 Knapsack, Dynamic Programming approach is required. Problem Statement A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are n items and weight of ith item is wi and the profit of selecting this item is pi. What items should the thief take? Dynamic-Programming Approach Let i be the highest-numbered item in an optimal solution S for W dollars. Then 𝑺’ = 𝑺 − {𝒊} is an optimal solution for 𝑾 – 𝒘𝒊 dollars and the value to the solution S is Vi plus the value of the sub-problem. We can express this fact in the following formula: define c[i, w] to be the solution for items 1,2, … , i and the maximum weight w. The algorithm takes the following inputs  The maximum weight W  The number of items n  The two sequences v = and w = Dynamic-0-1-knapsack (v, w, n, W) for w = 0 to W do c[0, w] = 0 for i = 1 to n do c[i, 0] = 0 for w = 1 to W do if wi ≤ w then if vi + c[i-1, w-wi] then c[i, w] = vi + c[i-1, w-wi] else c[i, w] = c[i-1, w] else c[i, w] = c[i-1, w] 36  Design & Analysis of Algorithms The set of items to take can be deduced from the table, starting at c[n, w] and tracing backwards where the optimal values came from. If 𝒄[𝒊, 𝒘] = 𝒄[𝒊 − 𝟏, 𝒘], then item i is not part of the solution, and we continue tracing with c[i-1, w]. Otherwise, item i is part of the solution, and we continue tracing with c[i- 1, w-W]. Analysis This algorithm takes Ɵ(𝒏. 𝒘) times as table c has (𝒏 + 𝟏). (𝒘 + 𝟏) entries, where each entry requires Ɵ(𝟏) time to compute. 37  8.2 Longest Common Subsequence Design & Analysis of Algorithms The longest common subsequence problem is finding the longest sequence which exists in both the given strings. Subsequence Let us consider a sequence S =. A sequence Z = over S is called a subsequence of S, if and only if it can be derived from S deletion of some elements. Common Subsequence Suppose, X and Y are two sequences over a finite set of elements. We can say that Z is a common subsequence of X and Y, if Z is a subsequence of both X and Y. Longest Common Subsequence If a set of sequences are given, the longest common subsequence problem is to find a common subsequence of all the sequences that is of maximal length. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff-utility, and has applications in bioinformatics. It is also widely used by revision control systems, such as SVN and Git, for reconciling multiple changes made to a revision-controlled collection of files. Naïve Method Let X be a sequence of length m and Y a sequence of length n. Check for every subsequence of X whether it is a subsequence of Y, and return the longest common subsequence found. There are 2m subsequences of X. Testing sequences whether or not it is a subsequence of Y takes 𝑶(𝒏) time. Thus, the naïve algorithm would take 𝑶(𝒏𝟐𝒎 ) time. Dynamic Programming Let 𝑿 = < 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , … , 𝒙𝒎 > and 𝒀 = < 𝒚𝟏 , 𝒚𝟐 , 𝒚𝟑 , … , 𝒚𝒏 > be the sequences. To compute the length of an element the following algorithm is used. In this procedure, table C[m, n] is computed in row major order and another table B[m,n] is computed to construct optimal solution. Algorithm: LCS-Length-Table-Formulation (X, Y) m := length(X) n := length(Y) for i = 1 to m do C[i, 0] := 0 38  Design & Analysis of Algorithms for j = 1 to n do C[0, j] := 0 for i = 1 to m do for j = 1 to n do if xi = yj C[i, j] := C[i - 1, j - 1] + 1 B[i, j] := ‘D’ else if C[i -1, j] ≥ C[i, j -1] C[i, j] := C[i - 1, j] + 1 B[i, j] := ‘U’ else C[i, j] := C[i, j - 1] + 1 B[i, j] := ‘L’ return C and B Algorithm: Print-LCS (B, X, i, j) if i=0 and j=0 return if B[i, j] = ‘D’ Print-LCS(B, X, i-1, j-1) Print(xi) else if B[i, j] = ‘U’ Print-LCS(B, X, i-1, j) else Print-LCS(B, X, i, j-1) This algorithm will print the longest common subsequence of X and Y. Analysis To populate the table, the outer for loop iterates m times and the inner for loop iterates n times. Hence, the complexity of the algorithm is 𝑶(𝒎. 𝒏), where m and n are the length of two strings. 39  Design & Analysis of Algorithms Example In this example, we have two strings 𝑿 = 𝑩𝑨𝑪𝑫𝑩 and 𝒀 = 𝑩𝑫𝑪𝑩 to find the longest common subsequence. Following the algorithm LCS-Length-Table-Formulation (as stated above), we have calculated table C (shown on the left hand side) and table B (shown on the right hand side). In table B, instead of ‘D’, ‘L’ and ‘U’, we are using the diagonal arrow, left arrow and up arrow, respectively. After generating table B, the LCS is determined by function LCS-Print. The result is BCB. 40