Download to read offline
![Divide and Conquer Approach Let P = (n,a[i],...,a[j]) denote an arbitrary instance of the problem. Here n is the number of elements in the list a[i],...a[j]and we are interested in finding the maximum and minimum of this list. Let Small(P) be true when n <2. In this case, the maximum and minimum are a[i] if n = 1. If n = 2, the problem can be solved by making one comparison. If the list has more than two elements, P has to be divided into smaller instances. After having divided P into two smaller subproblems we can solve them by recursively invoking the same divide-and-conquer algorithm. When the maxima and minima of these subproblems are determined, the two maxima are compared and the two minima are compared to achieve the solution for the entire set.](https://image.slidesharecdn.com/algorithmdesigntechiquesi-240611063143-1148155f/75/Algorithm-Design-Techiques-divide-and-conquer-8-2048.jpg)
![Algorithm Algorithm optimalMerge(files, n) { for i:=1 to n do{ for j:=i+1 to n do{ if (files[i] > files[j]) { temp = files[i]; files[i] = files[j]; files[j] = temp; } } } cost := 0; while (n > 1) { // Merge the smallest two files mergedFileSize = files[1] + files[2]; cost:= cost + mergedFileSize; // Replace the first file with the merged file size files[1]: = mergedFileSize; // Shift the remaining files to the left for i := 1 to n-1 do { files[i]:= files[i + 1]; } n--; // Reduce the number of files // Sort the files again for i:=1 to n do { for j:=i+1 to n do { if (files[i] > files[j]) { temp := files[i]; files[i] := files[j]; files[j] := temp; } } } } return cost; }](https://image.slidesharecdn.com/algorithmdesigntechiquesi-240611063143-1148155f/75/Algorithm-Design-Techiques-divide-and-conquer-27-2048.jpg)
Algorithm Design Techiques, divide and conquer
- 1. Unit 3 Algorithm DesignTechniques - I
- 2. Agenda • Divide andConquer- General Method • Finding maximum and minimum number • Greedy Method- General Method • Knapsack Problem • Job sequencing with deadlines • Optimal storage on tapes • Optimal merge pattern • Minimum cost spanning tree- Prims and Kruskals algorithm • Single pair shortest path
- 3. Divide and Conquer Themost-well known algorithm design strategy: Divide instance of problem into two or more smaller instances . Solve smaller instances recursively. Obtain solution to original (larger) instance by combining these solutions
- 4. Problem of sizen subproblem 2 of size n/2 a solution to subproblem 2 subproblem 1 of size n/2 a solution to subproblem 1 a solution to the original problem
- 5. Control abstraction ofDivide and Conquer
- 6. General divide andconquer recurrence relation For DAndC algorithms that produce the sub-problems of the same type In general, a problem instance of size n can be divided into b instances of size n/b, with a of them needing to be solved. Here, a and b are constants; a≥ 1 and b > 1. We get the following recurrence for the running time T(n) = T(1) for n = 1 T(n) = a T( n/b ) + f(n) for n > 1 where n is power of b f(n) accounts for the time spent on dividing the problem into smaller ones and on combining their solutions.
- 7. Finding Maximum andMinimum Problem is to find maximum and minimum items in a set of n elements. Iterative Algorithm requires 2(n-1) comparisons
- 8. Divide and ConquerApproach Let P = (n,a[i],...,a[j]) denote an arbitrary instance of the problem. Here n is the number of elements in the list a[i],...a[j]and we are interested in finding the maximum and minimum of this list. Let Small(P) be true when n <2. In this case, the maximum and minimum are a[i] if n = 1. If n = 2, the problem can be solved by making one comparison. If the list has more than two elements, P has to be divided into smaller instances. After having divided P into two smaller subproblems we can solve them by recursively invoking the same divide-and-conquer algorithm. When the maxima and minima of these subproblems are determined, the two maxima are compared and the two minima are compared to achieve the solution for the entire set.
- 9.
- 10. Example Tree of callsfor MaxMin
- 11. Example a: 22, 14,8, 17, 35, 3, 10, 55
- 12. Recursive algorithm requires3n/2 – 2 best, average, worst case comparisons when n is power of 2
- 13. Greedy Method Itis most straightforward design technique. it can be applied to a wide variety of problem. The problems that have n inputs and require to obtain a subset that satisfies some constraints. Any subset that satisfies those constraints is called a feasible solution. We need to find a feasible solution that either maximizes or minimizes a given objective function. A feasible solution that does this is called an optimal solution.
- 14. General Method Greedymethod suggests that one can devise an algorithm that works in stages, Considering one input at a time. At each stage, a decision is made regarding whether a particular input is in an optimal solution. This is done by considering the inputs in an order determined by some selection procedure. If the inclusion of the next input into the partially constructed optimal solution will result in an infeasible solution, then this input is not added to the partial solution Otherwise, It is added. The selection procedure itself is based on some optimization measure. This measure may be the objective function.
- 15. Fractional Knapsack Problem We are given n objects and a knapsack or bag. Object i has a weight wi and the knapsack has a capacity m. If a fraction xi, 0 <= xi <= 1,of object i is placed into the knapsack, then a profit of pixi is earned. The objective is to obtain a filling of the knapsack that maximizes the total profit earned. Since the knapsack capacity is m, we require the total weight of all chosen objects to be at most m.
- 16.
- 17. Example Consider thefollowing instance of the knapsack problem: n = 3, m= 20, (p1,p2,p3) = (25,24,15) and, (w1, w2,w3)= (18,15,10) Consider the following instance of the knapsack problem: n = 7, m = 15 Objects: 1 2 3 4 5 6 7 Profit (P): 5 10 15 7 8 9 4 Weight(w): 1 3 5 4 1 3 2
- 18. Job Sequencing withdeadlines We are given a set of n jobs. Associated with job i is an integer deadline di >= 0 and a profit pi >0. For any job i the profit pi is earned if the job is completed by its deadline. To complete a job one has to process the job on a machine for one unit of time. Only one machine is available for processing jobs. A feasible solution for this problem is a subset J of jobs such that each job in this subset can be completed by its deadline. The value of a feasible solution J is the sum of the profits of the jobs in J. Optimal solution is a feasible solution with maximum value.
- 19. Example 1. n =4, (p1,p2,P3,p4) = (100,10,15,27), (d1, d2,d3, d4) = (2,1, 2,1) 2. n = 5, (p1,p2,p3,p4,p5) = (60, 100, 20, 40, 20), (d1, d2, d3, d4, d5) = (2, 1, 3, 2, 1)
- 20.
- 21. OPTIMAL STORAGE ONTAPES There are n programs that are to be stored on a computer tape of length I. Associated with each program i is a length li,1<= i <= n. Clearly, all programs can be stored on the tape if and only if the sum of the lengths of the programs is at most I. We assume that whenever a program is to be retrieved from this tape, the tape is initially positioned at the front. Hence, if the programs are stored in the order the time needed to retrieve program is proportional to
- 22. OPTIMAL STORAGE ONTAPES mean retrieval time (MRT) = In optimal storage on tapes it is required to select order which minimizes MRT Minimizing the MRT is equivalent to minimizing d(I) = n 1 j j 1 k ik L
- 23. Example n =3 and (l1, l2, l3)= (5,10,3) Find an optimal placement for 13 programs on three tapesT0,T1,and T2,where the programs are of lengths 12, 5, 8, 32, 7, 5, 18, 26, 4, 3, 11, 10 and 6.
- 24.
- 25. Analysis To sortn programs in increasing order according to their length requires O(n log n) time if we use efficient algorithm. To store n programs on tapes it requires O(n) time
- 26. Optimal Merge Pattern Given n number of sorted files, the task is to merge a set of sorted files of different length into a single sorted file in minimum computation time. Two sorted files containing n and m records respectively could be merged together to obtain one sorted file in time n + m. files x1,x2,x3,and x4 are to be merged, we could first merge x1 and x2 to get a file y1. Then we could merge y1 and x3 to get y2 Finally, we could merge y2 and x4 to get the desired sorted file. Alternatively, we could first merge x1 and x2 getting y1, then merge x3 and x4 and get y2, and finally merge y1 and y2 and get the desired sorted file. Given n sorted files, there are many ways in which to pairwise merge them into a single sorted file. Different pairings require differing amounts of computing time. The problem is to determining an optimal way (one requiring the fewest comparisons) to pairwise merge n sorted files
- 27. Algorithm Algorithm optimalMerge(files, n) { fori:=1 to n do{ for j:=i+1 to n do{ if (files[i] > files[j]) { temp = files[i]; files[i] = files[j]; files[j] = temp; } } } cost := 0; while (n > 1) { // Merge the smallest two files mergedFileSize = files[1] + files[2]; cost:= cost + mergedFileSize; // Replace the first file with the merged file size files[1]: = mergedFileSize; // Shift the remaining files to the left for i := 1 to n-1 do { files[i]:= files[i + 1]; } n--; // Reduce the number of files // Sort the files again for i:=1 to n do { for j:=i+1 to n do { if (files[i] > files[j]) { temp := files[i]; files[i] := files[j]; files[j] := temp; } } } } return cost; }
- 28. Example The filesx1,x2, and x3 are three sorted files of length30, 20,and 10 records each, find optimal merge tree. Find an optimal binary merge pattern for five files whose lengths are 20, 30, 10, 5 and 30. Find an optimal binary merge pattern for ten files whose lengths are 28, 32, 12, 5, 84, 53, 91, 35, 3 and 11
- 29. Analysis The mainfor loop in Algorithm is executed n -1 times. If list is kept in increasing order according to the weight value in the roots, then Least(list) requires only O(1)time and insert(list, pt), can be done in O(n)time. Hence the total time taken is O(n2).In case list is represented as a minheap ,then Least(list) and insert(lisi, pt), can be done in O(logn) time. In this case the computing time for Tree is O(n logn)
- 30. Single-source Shortest Paths Overview Graphs can be used to represent the highway structure of a state or country with vertices representing cities and edges representing sections of highway. The edges can then be assigned weights which may be either the distance between the two cities connected by the edge or the average time to drive along that section of highway. A motorist wishing to drive from city A to B would be interested in answers to the following questions 1. Is there a path from A to B? 2. If there is more than one path from A to B, which is the shortest path? The length of a path is defined as the sum of the weights of the edges on that path. The starting vertex of the path is referred to as the source, and the last vertex the destination
- 31. Single-source Shortest PathsProblem In the problem we consider, we are given a directed graph G = (V, E), a weighting function cost for the edges of G, and a source vertex . The problem is to determine the shortest paths from to all the remaining vertices of G. It is assumed that all the weights are positive. The shortest path between and some Other node is an ordering among a subset of the edges
- 32. Example 1 2 34 5 6 1 0 50 45 10 ∞ ∞ 2 ∞ 0 10 15 ∞ ∞ 3 ∞ ∞ 0 ∞ 30 ∞ 4 20 ∞ ∞ 0 15 ∞ 5 ∞ 20 35 ∞ 0 ∞ 6 ∞ ∞ ∞ ∞ 3 0 Source is 1
- 33.
- 34. Analysis First forloop executes for n vertices times Second for loop is adding vertices into S in time log n. Third for loop updating distance it takes O(|E|) time Overall time complexity is O((n+ |E|) log n)
- 35.