Greedy Algorithms and Optimization Techniques
Learn about Greedy Algorithms, Subset Paradigm, Ordering Paradigm, and when to use Greedy Algorithm. Understand how Greedy Method and Control Abstraction work for the Subset Paradigm. Explore examples like the Knapsack Problem to grasp these algorithmic design concepts. Join the lecture to delve deeper into Data Structures and Algorithms using Python.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
ALGORITHMIC DESIGN: ALGORITHMIC DESIGN: GREEDY METHOD GREEDY METHOD
GREEDY ALGORITHM Most straightforward design technique. Used to solve optimization problems. Makes locally optimal choices at each step. Objective is to find a global optimum. LECTURE ON 11.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
SUBSET PARADIGM Selects a subset of elements that optimizes the given objective function. Examples: Knapsack Problem Minimum Spanning Tree LECTURE ON 11.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
Ordering paradigm Arranging elements in a specific order to optimize the given objective function. Examples: Optimal Storage on tapes. Optimal Merge Pattern. Huffman Coding. LECTURE ON 11.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
WHEN TO USE GREEDY ALGORITHM When the problem has "optimal substructure". When a locally optimal choice leads to a globally optimal solution. LECTURE ON 11.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
GREEDY METHOD CONTROL ABSTRACTION FOR SUBSET PARADIGM 1 Algorithm Greedy(a, n) 2 solution # a[1 : n] contains n inputs Selects an input from a[ ] and removes it. The selected input's value is assigned to x 3 fori 1 tondo A Boolean valued function that determines whether x can be included into the solution vector. 4 x Select(a) 5 if Feasible(solution, x) then 6 solution Union(solution, x) Combines x with the solution and updates the objective function. 7 returnsolution LECTURE ON 12. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
Knapsack Problem LECTURE ON 12. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
DESCRIPTION OF THE PROBLEM 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 pi xi is earned. A feasible solution (or filling) is any set (x1, x2 xn) satisfying 1 ? ????? ?, 0 xi 1 and 0 i n ? Goal of the problem: An optimal solution is a feasible solution for which ?=1 Since the knapsack capacity is m, the total weight of all chosen objects is required to be at most ???? is maximized. m. LECTURE ON 12. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
LEMMA: In case the sum of all the weights is m, then xi = 1, 0 i n is an optimal solution. LECTURE ON 12. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
LEMMA: All optimal solutions will fill the knapsack exactly. Assume that the sum of weights exceeds m. Now all the xi s cannot be 1. LECTURE ON 12. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
ALGORITHM FOR KNAPSACK PROBLEM LECTURE ON 12. 9. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
PROOF OF CORRECTNESS PROBLEM THEOREM: If ?? ??, then Algorithm ?1 ?1 ?2 ?2 GreedyKnapsack generates an optimal solution to the given instance of the knapsack problem. LECTURE ON 12. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
Minimum Cost Spanning Tree (MST) Problem LECTURE ON 13. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
KEY WORDS Weighted Graph. Spanning Tree. LECTURE ON 13. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
DESCRIPTION OF THE PROBLEM For a weighted undirected graph G, to determine a tree T that contains all the vertices in G and sum of weights of edges of T is minimum i.e., ? ? = ? ??(?). Minimum spanning tree (MST) problem is to find a spanning tree T with minimum weight. LECTURE ON |13. 09. 24 DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
APPLICATIONS Design of Networks. Electrical connections. Telecommunication. Transportation. LECTURE ON 13. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
GREEDY STRATEGY TO SOLVE MST PROBLEM USING PRIM S ALGORITHM At each step select the edge with the smallest weight that doesn't form a cycle. This strategy ensures that we always choose the optimal available edge, leading to a minimum spanning tree. LECTURE ON 13. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
ALGORITHM PRIM LECTURE ON 13. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
GREEDY STRATEGY TO SOLVE MST PROBLEM USING ALGORITHM KRUSKAL Selects the edge with the minimum weight from the remaining edges, as long as it doesn't create a cycle at each stage. LECTURE ON 13. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
ALGORITHM KRUSKAL LECTURE ON 13.09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
SINGLE-SOURCE SHORTEST PATHS If the vertices u and v are connected in G, the distance between u and v in G, denoted by dG(u, v), is the length of the shortest (u, v)-path in G. If there is no path connecting u and v, then dG(u, v) is defined to be infinite. Let G be a weighted graph. The length (or weight) of a path P denoted by ?(?) is the sum of the weights of the edges ?0,?1 ?? 1 of P i.e., ? ? = ?=0 ? 1?(??). For a weighted graph G, determining a shortest path between a vertex ? ?(?) and all other vertices of G if they exist is single-source shortest path problem. Greedy Approach: Makes the locally optimal choice at each step. LECTURE ON 13. 09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
DIJKSTRAS ALGORITHM Instance: A connected directed weighted graph G = (V, E) with n vertices, a source vertex v V(G). Assume that all the weights are positive. Output: To determine the shortest path from v to all the remaining vertices of G. LECTURE ON 13.09. 24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
Optimal Storage on Tapes Problem LECTURE ON 18.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
Description of the Problem This problem involves efficiently storing n programs on tapes to minimize access time. Associated with each program i is a length li , 1 i n. All programs can be stored on the tape if and only if the sum of the lengths of the programs is at most l. LECTURE ON 18.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
Mean Retrieval Time Let l1, l2 , . . . , ln be the length of n programs to be stored on tape. Suppose the programs are stored in the order of I = i1, i2 , . . . , in and tj be the time to retrieve program ij. Assuming that the tape is initially positioned at the beginning, then tj is proportional to the sum of all lengths of programs stored in front of the program ij. i.e., ?=1 ???. If all programs are retrieved equally, then the expected or mean retrieval time (MRT) is1 ? ?=1 Optimal Solution: To minimize MRT (Mean Retrieval Time), i.e. to minimize ? ? ??. 1 n = j jt n 1 LECTURE ON 18.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
STATEMENT Theorem: If l1 l2 ln, then the ordering ij = j, 1 j n, minimizes ?=1 ?=1 ??? over all possible permutations ij. ? ? LECTURE ON 18.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
Optimal Merge Pattern LECTURE ON 19.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
OPTIMAL MERGE PATTERN Given n sorted files, merge them into a single sorted file with minimum cost. The cost of merging two files is the sum of their lengths. Greedy Approach: At each stage, merge the two smallest files. Construction of binary merge tree. Weighted external path length of the tree is ?=1 the root to the external node for file xi and the length of xi is qi. Optimal binary merge tree: Is a binary merge tree where the sum of paths from root to external nodes is optimal . ? ???? where diis the distance from LECTURE ON 19.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
ALGORITHM TO GENERATE A TWO-WAY MERGE TREE LECTURE ON 19.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
PROOF OF CORRECTNESS If list initially contains n 1single node trees with weight values (q1, q2, ..., qn), then algorithm Tree generates an optimal two-way merge tree for n files with these lengths. LECTURE ON 19.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY DR. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
REFERENCES 1. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Fundamentals of Computer Algorithms, Galgotia Publications Second Edition, 2010. 2. Michael T. Goodrich, Irvine Roberto Tamassia, Michael H. Goldwasser, Data Structures and Algorithms in Python, Wiley India, 2016. 3. Michael T. Goodrich, Roberto Tamassia, Algorithm Design (Foundations, Analysis and Internet and Examples), Wiley India (P) Ltd., 2013. LECTURE ON 19.09.24 | DATA STRUCTURES AND ALGORITHMS USING PYTHON (PMT1MC04) | PREPARED AND POSTED BY D B R. CHRIS MONICA M., ASSISTANT PROFESSOR, DEPARTMENT OF MATHEMATICS, LOYOLA COLLEGE, CHENNAI 600 034.
