Title DAA-MODULE 3.pdf ✅

Geethalaxmi, Department of ISE, CEC Module 3 Greedy Method: General method, Coin Change Problem, Knapsack Problem, Job sequencing with deadlines (T2:4.1, 4.3, 4.5). Minimum cost spanning trees: Prims Algorithm, Kruskals Algorithm (T1:9.1, 9.2). Single source shortest paths: Dijkstra’s Algorithm (T1:9.3). Optimal Tree problem: Huffman Trees and Codes (T1:9.4). Transform and Conquer Approach: Heaps and Heap Sort (T1:6.4). RBT: L1, L2, L3 Table of Contents Module 3.......................................................................................................................................................1 GREEDY METHOD.....................................................................................................................................1 General Method: ........................................................................................................................1 Coin Change Problem:.................................................................................................................2 Knapsack Problem ......................................................................................................................3 Job Sequencing With Deadlines:..................................................................................................7 MINIMUM COST SPANNING TREES: ........................................................................................................9 Prim’s Algorithm.......................................................................................................................10 Kruskal’s Algorithm ..................................................................................................................13 SINGLE SOURCE SHORTEST PATHS: .......................................................................................................17 Dijkstra’s Algorithm..................................................................................................................17 Huffman Trees and Codes.........................................................................................................22 Heaps and Heapsort .................................................................................................................27 GREEDY METHOD General Method: Greedy Method: The greedy method is perhaps (maybe or possible) the most straight forward design technique, used to determine a feasible solution that may or may not be optimal. Feasible solution:- Most problems have n inputs and its solution contains a subset of inputs that satisfies a given constraint(condition). Any subset that satisfies the constraint is called feasible solution. Optimal solution: To find a feasible solution that either maximizes or minimizes a given objective function. A feasible solution that does this is called optimal solution.
Geethalaxmi, Department of ISE, CEC The greedy method suggests that an algorithm 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. Greedy algorithms neither postpone nor revise the decisions (ie., no back tracking). 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. The selection procedure itself is based on some optimization measure. Several optimization measures are plausible for a given problem. Most of them, however, will result in algorithms that generate sub-optimal solutions. This version of greedy technique is called subset paradigm. Some problems like Knapsack, Job sequencing with deadlines and minimum cost spanning trees are based on subset paradigm. For the problems that make decisions by considering the inputs in some order, each decision is made using an optimization criterion that can be computed using decisions already made. This version of greedy method is ordering paradigm. Some problems like optimal storage on tapes, optimal merge patterns and single source shortest path are based on ordering paradigm. Example: Kruskal’s minimal spanning tree. Select an edge from a sorted list, check, decide, and never visit it again. Application of Greedy Method: Job sequencing with deadline 0/1 knapsack problem Minimum cost spanning trees Single source shortest path problem. Coin Change Problem: Let us revisit the change-making problem faced, at least subconsciously, by millions of cashiers all over the world: give change for a specific amount n with the least number of coins of the denominations d1 > d2 > . . . > dm used in that locale. For example, the widely used coin denominations in the United States are d1 = 25 (quarter), d2 = 10 (dime), d3 = 5 (nickel), and d4 = 1 (penny). How would you give change with coins of these denominations of, say, 48 cents? If you came up with the answer 1 quarter, 2 dimes, and 3 pennies, you followed— consciously or not—a logical strategy of making a sequence of best choices among the currently available alternatives.  Indeed, in the first step, you could have given one coin of any of the four denominations. “Greedy” thinking leads to giving one quarter because it reduces the remaining amount the most, namely, to 23 cents.  In the second step, you had the same coins at your disposal, but you could not give a quarter, because it would have violated the problem’s constraints.  So your best selection in this step was one dime, reducing the remaining amount to 13 cents.
Geethalaxmi, Department of ISE, CEC  Giving one more dime left you with 3 cents to be given with three pennies. Is this solution to the instance of the change-making problem optimal? Yes, it is. In fact, one can prove that the greedy algorithm yields an optimal solution for every positive integer amount with these coin denominations. At the same time, it is easy to give an example of coin denominations that do not yield an optimal solution for some amounts—e.g., d1 = 25, d2 = 10, d3 = 1 and n = 30. Knapsack Problem Let us apply the greedy method to solve the knapsack problem. We are given ‘n’ objects and a knapsack. The 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 fill 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’. The problem is stated as: The profits and weights are positive numbers. A feasible solution is any set (x1, x2, ..., xn) satisfying (2) and (3). An optimal solution is a feasible solution that maximizes (1). Consider the following instance of the knapsack problem: n = 3, m = 20, (p1, p2, p3) = (25, 24, 15) and (w1, w2, w3) = (18, 15,10).
Geethalaxmi, Department of ISE, CEC Detailed explanation: 1. First, we try to fill the knapsack by selecting the objects in some order: x1 x2 x3 Σwi xi Σpi xi 1/2 1/3 1/4 18 x 1/2 + 15 x 1/3 + 10 x1/4 =16.5 25 x 1/2 + 24 x 1/3 + 15 x 1/4= 24.25 2. Select the object with the maximum profit first (p = 25). So, x1 = 1 and profit earned is 25. Now, only 2 units of space is left, select the object with next largest profit (p = 24). So, x2 =2/15 x1 x2 x3 Σwi xi Σpi xi 1 2/15 0 18 x 1 + 15 x 2/15 =20 25 x 1 + 24 x 2/15 =28.2 3. Considering the objects in the order of non-decreasing weightswi. x1 x2 x3 Σ wi xi Σ pi xi 0 2/3 1 15 x 2/3 + 10 x 1 =20 24 x 2/3 + 15 x 1 =31 4. Considered the objects in the order of the ratio pi / wi. p1/w1 p2/w2 p3/w3 25/18 24/15 15/10 1.4 1.6 1.5 Sort the objects in order of the non-increasing order of the ratio pi / xi. Select the object with the maximum pi / xi ratio, so, x2 = 1 and profit earned is 24. Now, only 5 units of space is left, select the object with next largest pi / xi ratio, so x3 = 1⁄2 and the profit earned is7.5. x1 x2 x3 Σwi xi Σpi xi 0 1 1/2 15 x 1 + 10 x 1/2 =20 24 x 1 + 15 x 1/2 =31.5 This solution is the optimal solution.