E Lesson 5

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

MCA 2 All right are reserved with CU-IDOL DESIGN AND ANALYSIS OF ALGORITHMS Course Code: MCA 632 Semester: Third e-Lesson: 5  SLM Unit: 6 www.cuidol.in Unit-6(MCA 632)

Design and Analysis of Algorithms 33 OBJECTIVES INTRODUCTION  Student will be able to learn about greedy  In this unit we are going to learn about approach to design algorithm. algorithm analysis through greedy method.  Student will be able to solve coin based and Under this you will learn and understand the concept of coin change problem and knapsack problems.  knapsack problem.  Student will be able to design minimum spanning trees. Different types minimum spanning trees. Student will be able to learn differentiate between   Prim’s and Kruskal’s algorithm. www.cuidol.in Unit-6(MCAQ-613021) INSTITUTE OF DAIlSlTAriNgChEt aArNeDreOsNeLrvINeEd LwEiAthRNCIUN-GIDOL

TOPICS TO BE COVERED 4 Greedy Method 1: General method Coin change Problem Knapsack Problem Job sequencing with deadlines Minimum cost spanning trees: Prim’s Algorithm Kruskal’s Algorithm www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Greedy Method 5  A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.  How do you decide which choice is optimal? Assume that you have an objective function that needs to be optimized (either maximized or minimized) at a given point. A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision. www.cuidol.in Unit-6(MCA 632) 5All right are reserved with CU-IDOL

Greedy Method 6 Greedy algorithms have some advantages and disadvantages:  It is quite easy to come up with a greedy algorithm (or even multiple greedy algorithms) for a problem.  Analyzing the run time for greedy algorithms will generally be much easier than for other techniques (like Divide and conquer). For the Divide and conquer technique, it is not clear whether the technique is fast or slow. This is because at each level of recursion the size of gets smaller and the number of sub-problems increases.  The difficult part is that for greedy algorithms you have to work much harder to understand correctness issues. Even with the correct algorithm, it is hard to prove why it is correct. Proving that a greedy algorithm is correct is more of an art than a science. It involves a lot of creativity. www.cuidol.in Unit-6(MCA 632) 6All right are reserved with CU-IDOL

Greedy Method 7  Problem: Pick k numbers out of n numbers such that the sum of these k numbers is the largest.  Algorithm: FOR i = 1 to k pick out the largest number and delete this number from the input. ENDFOR www.cuidol.in Unit-6(MCA 632) 7All right are reserved with CU-IDOL

Applications of Greedy Method 8 • Optimal solutions: – change making for “normal” coin denominations – minimum spanning tree (MST) – single-source shortest paths – simple scheduling problems – Huffman codes • Approximations: – traveling salesman problem (TSP) – knapsack problem – other combinatorial optimization problems www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Coin-Change Problem 9 Given unlimited amounts of coins of denominations d1 > … > dm , give change for amount n with the least number of coins Example: d1 = 25c, d2 =10c, d3 = 5c, d4 = 1c and n = 48c Greedy solution: d1+ 2 d2+ 3 d1 Greedy solution is • optimal for any amount and “normal’’ set of denominations • may not be optimal for arbitrary coin denominations www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Coin-Change Problem 10 • Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. • For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5. For the currency system , where we have coins of 1, 7, 10 value, counting coins for value 18 will be absolutely optimum but for count like 15, it may use more coins than necessary . For example , the greedy approach will use 10+1+1+1+1+1 , total 6 coins. Whereas the same problem could be solved by using 3 coins(7+7+1). www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Coin-Change Problem 11 Algorithm for Coin change Problem with greedy method V is total sum that is required with use of n coins(denominations) 1) Initialize result as empty. 2) find the largest denomination that is smaller than V. 3) Add found denomination to result. Subtract value of found denomination from V. 4) If V becomes 0, then print result. Else repeat steps 2 and 3 for new value of V www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Knapsack Problem 12 The problem states- Given a knapsack (a kind of shoulder bag) with a limited weight capacity and few items each having some weight and value, which items should we place in the knapsack so that the value or profit that we obtain by putting the items in the knapsack is maximum and the weight limit of the knapsack also does not exceed? Knapsack problem has the following two variants- 1. Fractional Knapsack Problem 2. 0/1 Knapsack Problem www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Knapsack 13 Problem Fractional Knapsack Problem- As the name suggests, In Fractional Knapsack Problem we can even put the fraction of any item in the knapsack if taking the complete item is not possible i.e. here items are divisible.Fractional Knapsack Problem is solved using Greedy Approach. Steps for solving Fractional Knapsack Problem using Greedy Approach Step-01:For each item, compute its value / weight ratio. Step-02: Arrange all the items in the decreasing order of their value / weight ratios. Step-03:Start putting the items in the Knapsack beginning from the item with the highest ratio. Put as many items as you can in the Knapsack. www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Knapsack Problem 14 Time Complexity of Fractional Knapsack Problem using Greedy Approach- • While solving the problem, the main time taking step is the sorting of all items in the decreasing order of their value / weight ratios. • But If the items are already arranged in the required order, the while loop takes O(n) time. • Now, because quick sort’s average time complexity is O(nlogn), therefore total time taken including the sort is O (nlogn). www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Knapsack Problem 15 • Find the optimal solution for the fractional knapsack problem making use of greedy approach. Consider- n = 5 (I1,I2,I3,I4,I5) and w = 60 kg • (w1, w2, w3, w4, w5) = (5, 10, 15, 22, 25) • (b1, b2, b3, b4, b5) = (30, 40, 45, 77, 90) Solution Had the problem been a 0/1 knapsack problem, we would have stopped and reported that the knapsack has items < I1 , I2 , I5 > and the knapsack’s total cost is 160. www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Knapsack Problem 16 • But because in fractional knapsack problem we can even take the fraction of any item, so our knapsack will contain the items- < I1 , I2 , I5 , (20/22) I4 > Now, Total cost of the knapsack = 160 + (20/27) x 77 = 160 + 70 = 230 units www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Knapsack Problem 17 Algorithm 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 weight = weight + w[i] else x[i] = (W - weight) / w[i] weight = W break return x www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Job Sequencing 18 Problem with Deadlines This problem consists of n jobs each associated with a deadline and profit and our objective is to earn maximum profit. We will earn profit only when job is completed on or before deadline. We assume that each job will take unit time to complete. Points to remember • In this problem we have n jobs j1, j2, … jn each has an associated deadline d1, d2, … dn and profit p1, p2, ... pn. • Profit will only be awarded or earned if the job is completed on or before the deadline. • We assume that each job takes unit time to complete. • The objective is to earn maximum profit when only one job can be scheduled or processed at any given time. www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Job Sequencing 19 Problem with Deadlines Input: Four Jobs with following deadlines and profits Job ID Deadline Profit a 4 20 b 1 10 c 1 40 d 1 30 Output: Following is maximum profit sequence of jobs c, a www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Job Sequencing 20 Problem with Deadlines This is a standard Greedy Algorithm problem. Following is algorithm. 1) Sort all jobs in decreasing order of profit. 2) Initialize the result sequence as first job in sorted jobs. 3) Do following for remaining n-1 jobs ....... a) If the current job can fit in the current result sequence without missing the deadline, add current job to the result. Else ignore the current job. Analysis In this algorithm, we are using two loops, one is within another. Hence, the complexity of this algorithm is O(n2). www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Job Sequencing 21 Problem with 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, D(i)>0D(i)>0 for 1⩽i⩽n1⩽i⩽n. Initially, these jobs are ordered according to profit, i.e. p1⩾p2⩾p3⩾...⩾pnp1⩾p2⩾p3⩾...⩾pn. 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 www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Minimum Spanning 22 Tree(MST)  It may be defined on Euclidean space points or on a graph.  G = (V, E): weighted connected undirected graph  Spanning tree : S = (V, T), T  E, undirected tree  Minimum spanning tree(MST) : a spanning tree with the smallest total weight. Alternate Definition  Let G = (V, E) be a connected graph in which each edge (u, v) E has an associated cost C(u, v).A Spanning Tree for G is a subgraph of G that it is a free tree connecting all vertices in V. The cost of a spanning tree is the sum of costs on its edges.  An MST of G is a spanning tree of G having a minimum cost. www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

MST (Cont…) 23  A graph and one of its minimum costs spanning tree www.cuidol.in Fig. 2.5: Minimum spanning Tree All right are reserved with CU-IDOL Unit-6(MCA 632)

MST Kruskal’s Algorithm 24 Step 1: Sort all edges into non-decreasing order. Step 2: Add the next smallest weight edge to the forest if it will not cause a cycle. Step 3: Stop if n-1 edges. Otherwise, go to Step2. www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

MST Kruskal ‘s Algorithm 25 KRUSKAL(G): 1A=∅ 2 for each v ∈ G.V: 3 MAKE-SET(v) 4 for each (u, v) in G.E ordered by weight(u, v), increasing: 5 if FIND-SET(u) ≠ FIND-SET(v): 6 A = A ∪ {(u, v)} 7 UNION(u, v) 8 return A Kruskal's algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time, where E is the number of edges in the graph and V is the number of vertices, all with simple data structures. These running times are equivalent because: •E is at most and is . •Each isolated vertex is a separate component of the minimum spanning forest. If we ignore isolated vertices we obtain V ≤ 2E, so log V is O(log E) www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

MST Kruskal ‘s Algorithm 26 Fig. 2.6: Kruskal’s algorithm Implementation Unit-6(MCA 632) All right are reserved with CU-IDOL www.cuidol.in

Prim’s Algorithm 27 Step 1: x  V, Let A = {x}, B = V - {x}. Step 2: Select (u, v)  E, u  A, v  B such that (u, v) has the smallest weight between A and B. Step 3: Put (u, v) in the tree. A = A  {v}, B = B - {v} Step 4: If B = , stop; otherwise, go to Step 2. • Time complexity : O(n2), n = |V|. (see the example on the next page) www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Prim’s Algorithm 28 Algorithm 1) Create a set mstSet that keeps track of vertices already included in MST. 2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first. 3) While mstSet doesn’t include all vertices ….a) Pick a vertex u which is not there in mstSet and has minimum key value. ….b) Include u to mstSet. ….c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

Prim’s Algorithm 29 Prim’s Algorithm Prim’s algorithm is a greedy approach to find the minimum spanning tree. In this algorithm, to form a MST we can start from an arbitrary vertex. Algorithm: MST-Prim’s (G, w, r) for each u є G.V u.key = ∞ u.∏ = NIL r.key = 0 Q = G.V while Q ≠ Ф u = Extract-Min (Q) for each v є G.adj[u] if each v є Q and w(u, v) < v.key v.∏ = u v.key = w(u, v) The function Extract-Min returns the vertex with minimum edge cost. This function works on min- heap. www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

An Example of Prim’s 30 Algorithm Fig. 2.7: Prim’s algorithm Implementation Unit-6(MCA 632) All right are reserved with CU-IDOL www.cuidol.in

MULTIPLE CHOICE QUESTIONES 31 1.)Which of the following is not greedy approach method? b) Knapsack problem a) Coin change problem d) Spanning tree c) Binary search 2) Which of the following is a minimum spanning tree problem? a) Prim’s Algorithm b) Kruskal’s algorithm c) Both of the above d) none 3) In Knapsack problem, the best strategy to get the optimal solution, where Pi, Wi is the Profit, Weight associated with each of the Xith object respectively is to a) Arrange the values Pi/Wi in ascending order b) Arrange the values Pi/Xi in ascending order c) Arrange the values Pi/Wi in descending order d) Arrange the values Pi/Xi in descending order www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 32 4) Time complexity of knapsack 0/1 where n is the number of items and W is the capacity of knapsack. Select one: a) O(W) b) O(n) c) O(nW) d)O(n2) 5) Time complexity of Prim’s algorithm is B) O(n2) A) O(n) D) O(log n) C) O(1) 6) Time complexity of Job Sequencing algorithm is b) O(n2) a) O(n) d) O(log n) c) O(1) Answer:1)-c 2)-c 3)-a 4)-c 5)-b 6)-b www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

SUMMARY 33 This presentation includes unit 6. Greedy method is one of the important method in designing of algorithms. This is an optimization technique which is based on local profit. Job sequencing, coin change problem and knapsack problem are some examples under greedy approach. Minimum spanning tree is a tree which represents minimum cost of a path with two algorithm named Prim’s and Kruskal’s Kruskal's algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time, where E is the number of edges in the graph and V is the number of vertices, all with simple data structures where Prim’s have O(n2) www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 34 Q1. What do you mean by greedy approach. Ans. This is an optimisation technique at local level. For Further details please refer to the SLM Q2. Give any example of greedy method. Ans. Coin change problem, knapsack problem. For Further details please refer to the SLM Q3. Discuss job sequencing problem. Ans. We need to arrange some jobs with given deadlines so that cost is minimum. For Further details please refer to the SLM www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

REFRENCES 35 1) Data Structures and Algorithms made easy By Narasimha Karumanchi. 2) The Algorithm Design Manual, 2nd Edition by Steven S Skiena 3) Fundamentals of Computer Algorithms - Horowitz and Sahani 4) https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_greedy_ method.htm www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL

36 THANK YOU www.cuidol.in Unit-6(MCA 632) All right are reserved with CU-IDOL