Download to read offline
![ Let us consider that you have an array F with size n. F[i] contains the size of ith file We want merge that file into one single file. What could be the best possible solution for that….? 1) A and B are two files with sizes and then time complexity of merging it is 0(m+n) Eg: F={10,5,100,50,20,15} N=6](https://image.slidesharecdn.com/greedyalgorithm-200319171637/75/computer-operating-system-Greedy-algorithm-2-2048.jpg)
![ m=k+1 While m≤n and s[m]<f[k] M=m+1 If m≤n return{am}URECURSIVE-ACTIVITY-SELECTOR( s, f, k, n) Else return ∅](https://image.slidesharecdn.com/greedyalgorithm-200319171637/75/computer-operating-system-Greedy-algorithm-11-2048.jpg)
![ n=s.length A={a1} K=1 For m=2 to n If s[m]≥f[k] A=AU{am} K=m Return A](https://image.slidesharecdn.com/greedyalgorithm-200319171637/75/computer-operating-system-Greedy-algorithm-14-2048.jpg)
computer operating system:Greedy algorithm
- 1.
- 2. Let usconsider that you have an array F with size n. F[i] contains the size of ith file We want merge that file into one single file. What could be the best possible solution for that….? 1) A and B are two files with sizes and then time complexity of merging it is 0(m+n) Eg: F={10,5,100,50,20,15} N=6
- 3. Select first2 files and merge them then merge the previous output file with the third file and so on…. Merge1:F={15,100,50,20,15} cost=15 Merge2:F={115,50,20,15} cost=115 Merge3:F={165,20,15} cost=165 Merge4:F={185,15} cost=185 Merge5:F={200} cost=200 Total cost of merging=15+115+165+185+200 =680 Strategy 2 Step1:merge the file in group of 2 Step2:That means after the first step we ll have n/2 intermidiate files. Step3:Then merge these intermediate files. Step4:Keep merging in that way till all files are merged. Step5:This approach is called 2 way merging Step6:If we do it in group of elements then it is called k way merging
- 4. We haveF={10,5,100,50,20,15} Step 1:F{15,150,35} Cost=15+150+35 Step 2:F{165,35} Cost=165 Step 3:F{200} Cost=200 Total cost=15+150+35+165+200=565
- 5. 1)sort filein ascending order as F={5,10,15,20,50,100} Repeat the process until we have single file Take 1st two smallest file then merge them Insert the merged file in the sorted list at its correct position F={15,15,20,50,100} cost=15 f-={20,30,50,100} c0st= 30 F={50,50,100} cost=50 F={100,100} cost=100 F={200} c0st=200 15+30+50+100+200=395 Total cost of merging is 395 This is optimal solution Time complexity:0(nlogn)
- 6. An activityselection problem Elements of greedy strategy Huffman codes
- 7. Greedy algorithmis the concept which observes subproblems and we need to consider only one choice.i.e called as greedy choice Based on observation greedy choice makes optimal solution. A greedy algorithm always makes the choice that looks, best at the moment. But greedy algorithm do not always read optimal solution but from many problem they do. Greedy algorithm following dynamic programming approach where recursive calls , how been made optimal solution.
- 8. S={a1,a2 ,…………………..an} Start time si and finish time fi, Where 0 ≤si < fi<∞ If selected activity ai takes place during the half open time interval[si,fi), Activities a1 and aj are compatible if the intervals [si,fi) and [si,fj) do not overlap. i.e ai and aj are compatible if si≤fj or sj≥fj. i 1 2 3 4 5 6 7 8 9 10 11 si 1 3 0 5 3 5 6 8 8 2 12 fi 4 5 9 7 9 9 10 11 12 14 16
- 9. From the aboveset of activities we wish to find maximum set of mutual compatible activities that start after ak activity finishes and that finished before aj starts.
- 10.
- 11. m=k+1 Whilem≤n and s[m]<f[k] M=m+1 If m≤n return{am}URECURSIVE-ACTIVITY-SELECTOR( s, f, k, n) Else return ∅
- 12.
- 13. K sk fk 0- 0 a0 1 1 4 ao 2 3 5 2 0 6 3 5 7 5 3 9 6 5 9 7 6 10 8 8 11 9 8 12 10 2 14 11 12 16 a1 M=1 Recursive-activity selector(s,f,0,11) a2 a1 Recursive-activity selector(s,f,1,11) a3 a1 a1 a4 M=4 a1 a4 a5 a1 a1 a1 a4 a4 a4 a6 a7 a8 M=8 Recursive-activity selector(s,f,4,11) a1 a1 a1 a4 a4 a4 a8 a8 a8 a10 a11 M=11 Recursive-activity selector(s,f,11
- 14. n=s.length A={a1} K=1 For m=2 to n If s[m]≥f[k] A=AU{am} K=m Return A
- 15. Determine theoptimal substructure Develop the recursive solution Prove one of the optimal choice is greedy choce Show that all but one of subproblems are empty after greedy choice Develop a recursive algorithm that implements the greedy strategy Convert the recursive algorithm to an iterative one.
- 16. Data compressionalgorithm using greedy choice. Without loss of information. Based n assigned codes based on frequencies. Variable length codes are known as prefix codes.
- 17. characte r code frequenc y A 00010 E 001 15 I 010 12 S 011 3 T 100 4 P 101 13 Newline 110 1 Total bits 30 45 36 12 12 39 3 A E I S T P n Code tree 0 1 0 1 0 1 0 1 0 1 0 1 0 A 000 E 001 Total :174
- 18. Goal: reducesthe code tree. cha r freq A 10 E 15 I 12 S 3 F 4 P 13 n 1 n S 4 F 8 A 18 I P 2 5 1 3410 12 13 58 33 E 15
- 19. n S 4 T 8 A 1 8 I P 2 5 1 3410 1213 58 3 3 E 15 0 1 0 1 0 1 0 1 0 1 0 1 Char Code Freq Total bits A 110 10 30 E 10 15 30 I 00 12 24 S 11111 3 15 T 110 4 16 P 01 13 20 n 11110 1 5 Total :146
- 20. n=|C| Q=C For i=1 to n-1 Allocate a new node z Z.left=x=EXTRACT-MIN(Q) Z.left=y=EXTRACT-MIN(Q) INSERT(Q,z) Return EXTRACT-MIN(Q) //return to the root of tree
- 21. 0-1 knapsackproblem:
- 22. 1 0 item3 $60 2 0 30 item1 item2 $120$100 3 0 2 0 50 $120+ $60 $10 0 =$220 $100 + + + + 1 0 20 30 10 $120 $60 =$180=$160 (b)(a) 20 30 20 10 (c) $100 $60 $80 =$240 An exampleshows that the greedy strategy does not work for the 0-1 knapsack problem
- 23. a)the thief mustselect a subset Of three items shown whose weight must not exceed 50 pond. (b)the optimal subset includes items 2 and 3 .any solution with 1 item is suboptimal even though item 1 has the greatest value per pound (c) fractional knapsack problem ,taking the Item in order of greatest value per pound yields an optimal solution
- 24. Introduction toalgorithms by THOMAS H.COREMEN , CHARLES E.LEISERSON, RONALD L.RIVEST, CLIFFORD STEIN WWW.google.com