Module 11 Greedy Technique PDF

‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Design and Analysis of Algorithms Design and Analysis of Algorithms Module 11 Greedy Technique Week Learning Outcomes Describe Greedy Technique as...

‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Design and Analysis of Algorithms Design and Analysis of Algorithms Module 11 Greedy Technique Week Learning Outcomes Describe Greedy Technique as a concept Apply Prim’s Algorithm, Kruskal’s Algorithm and Dijkstra’s Algorithm in various context Explain Huffman Trees and Codes Apply Huffman Tree in problem domain 4 Topic Outline  Greedy Technique Overview  Prim’s Algorithm  Kruskal’s Algorithm  Dijkstra’s Algorithm  Huffman Trees and Codes 5 Greedy Technique Greedy Technique Constructs a solution to an optimization problem piece by piece through a sequence of choices that are:  feasible  locally optimal  irrevocable For some problems, yields an optimal solution for every instance. For most, does not but can be useful for fast approximations. 7 Applications of the Greedy Strategy Optimal solutions: o change making for “normal” coin denominations o minimum spanning tree (MST) o single-source shortest paths o simple scheduling problems o Huffman codes Approximations: o traveling salesman problem (TSP) o knapsack problem o other combinatorial optimization problems 8 Change-Making Problem , 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 optimal for any amount and “typical’’ set of denominations not optimal for all coin denominations … 9 Change-Making Problem Greedy not optimal for all sets of denominations: Consider 1, 3, 4 ?For what value does greedy algorithm fail 1 0 Minimum Spanning Tree (MST) Spanning tree of a connected graph G: a connected acyclic subgraph of G that includes all of G’s vertices i.e. an undirected connected graph is its connected acyclic subgraph (i.e., a tree) that contains all the vertices of the graph Minimum spanning tree of a weighted, connected graph G: a spanning tree of G of minimum total weight a 6 : Example of Spanning Tree c 2 4 1 b 3 d 1 1 Minimum Spanning Tree (MST) Minimum spanning tree problem: is the problem of finding a minimum spanning tree for a given weighted connected graph ?… How can be found Why constructing a minimum spanning tree with exhaustive search is not efficient ? ( see your textbook ) a 6 c 2 4 1 b 3 d 1 2 Prim’s MST algorithm One of the algorithms for finding MST, which goes back to at least 1957 Prim’s Algorithm Steps: - Start with tree T1 consisting of one (any) vertex and “grow” tree one vertex at a time to produce MST through a series of expanding subtrees T1, T2, …, Tn - On each iteration, construct Ti+1 from Ti by adding vertex not in Ti that is closest to those already in Ti (this is a “greedy” step!) - Stop when all vertices are included 1 3 Pseudocode of Prim’s algorithm 1 4 Prim’s MST algorithm One of the algorithms for finding MST, which goes back to at least 1957 Prim’s Algorithm Steps: - Start with tree T1 consisting of one (any) vertex and “grow” tree one vertex at a time to produce MST through a series of expanding subtrees T1, T2, …, Tn - On each iteration, construct Ti+1 from Ti by adding vertex not in Ti that is closest to those already in Ti (this is a “greedy” step!) - Stop when all vertices are included 1 5 Notes about Prim’s algorithm Proof by induction that this construction actually yields MST – ( see ch. 9 Sec. 9.1 from textbook ) Needs priority queue for locating closest fringe vertex ( min-heap) Efficiency O(n2) for weight matrix representation of graph and array implementation of priority queue O(m log n) for adjacency list representation of graph with n vertices and m edges and min-heap implementation of priority queue 1 6 Activity !!! In groups, in detailed steps apply prim algorithm for constructing MST for this graph ? Kruskal’s algorithm for MST Kruskal’s algorithm looks at a minimum spanning tree of a weighted connected graph G = (V, E) as an acyclic subgraph with |V |− 1 edges for which the sum of the edge weights is the smallest. The algorithm constructs a minimum spanning tree as an expanding sequence of subgraphs that are always acyclic but are not necessarily connected on the inter- mediate stages of the algorithm. 1 8 Kruskal’s algorithm for MST Kruskal’s algorithm Steps: Sort the edges in nondecreasing order of lengths “Grow” tree one edge at a time to produce MST through a series of expanding forests F1, F2, …, Fn-1 On each iteration, add the next edge on the sorted list unless this would create a cycle. (If it would, skip the edge.) 1 9 Pseudocode Kruskal’s algorithm 2 0 Notes about Kruskal’s algorithm Algorithm looks easier than Prim’s but is harder to implement (checking for cycles!) Cycle checking: a cycle is created iff added edge connects vertices in the same connected component Union-find algorithms – (for more details see sec. 9.2 in the textbook) 2 1 Shortest paths – Dijkstra’s algorithm Single Source Shortest Paths Problem: Given a weighted connected graph G, find shortest paths from source vertex s to each of the other vertices Dijkstra’s algorithm: Similar to Prim’s MST algorithm, with a different way of computing numerical labels: Among vertices not already in the tree, it finds vertex u with the smallest sum dv + w(v,u) where v is a vertex for which shortest path has been already found on preceding iterations (such vertices form a tree) dv is the length of the shortest path form source to v w(v,u) is the length (weight) of edge from v to u 2 2 Pseudocode Dijkstra’s algorithm 2 3 Dijkstra’s algorithm- An example Apply the algorithm to find the shortest path from the following graph 2 4 Dijkstra’s algorithm- An example 2 5 Notes on Dijkstra’s algorithm Doesn’t work for graphs with negative weights Applicable to both undirected and directed graphs Efficiency O(|V|2) for graphs represented by weight matrix and array implementation of priority queue O(|E|log|V|) for graphs represented by adj. lists and min-heap implementation of priority queue Don’t mix up Dijkstra’s algorithm with Prim’s algorithm! 2 6 Coding Problem Coding: assignment of bit strings to alphabet characters Codewords: bit strings assigned for characters of alphabet Two types of codes: fixed-length encoding (e.g., ASCII) variable-length encoding (e,g., Morse code) Prefix-free codes: no codeword is a prefix of another codeword Problem: If frequencies of the character occurrences are known, what is the best binary prefix-free code?2 7 Huffman codes Any binary tree with edges labeled with 0’s and 1’s yields a prefix-free code of characters assigned to its leaves Optimal binary tree minimizing the expected (weighted average) length of a codeword can be constructed as follows 2 8 Huffman’s algorithm Huffman’s encoding is one of the most important file-compression methods Huffman’s algorithm steps: Step 1: Initialize n one-node trees with alphabet characters and the tree weights with their frequencies. Step 2: Repeat the following step n-1 times: join two binary trees with smallest weights into one (as left and right subtrees) and make its weight equal the sum of the weights of the two trees. Mark edges leading to left and right subtrees with 0’s and 1’s, respectively. A tree constructed by the above algorithm is called a Huffman tree. 2 9 Huffman’s algorithm Example Consider the five-symbol alphabet {A, B, C, D, _} with the following occurrence frequencies in a text made up of these symbols: 3 0 Huffman’s algorithm Example 3 1 Huffman’s algorithm Example The Result : average bits per character: 2.25 for fixed-length encoding: 3 compression ratio: (3-2.25)/3*100% = 25% 3 2 Summary The greedy technique suggests constructing a solution to an optimization problem through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached. On each step, the choice made must be feasible, locally optimal, and irrevocable. Prim’s algorithm is a greedy algorithm for constructing a minimum spanning tree of a weighted connected graph. It works by attaching to a previously constructed subtree a vertex closest to the vertices already in the tree. Kruskal’s algorithm is another greedy algorithm for the minimum spanning tree problem. It constructs a minimum spanning tree by selecting edges in nondecreasing order of their weights provided that the inclusion does not create a cycle. Checking the latter condition efficiently requires an application of one of the so-called union-find algorithms. 3 3 Summary Dijkstra’s algorithm solves the single-source shortest-path problem of finding shortest paths from a given vertex (the source) to all the other vertices of a weighted graph or digraph. A Huffman tree is a binary tree that minimizes the weighted path length from the root to the leaves of predefined weights. The most important application of Huffman trees is Huffman codes. A Huffman code is an optimal prefix-free variable-length encoding scheme that assigns bit strings to symbols based on their frequencies in a given text. This is accomplished by a greedy construction of a binary tree whose leaves represent the alphabet symbols and whose edges are labeled with 0’s and 1’s. 3 4 List of Readings  Required Reading : Chapter 9 from Anany Levitin (2012). Introduction to the Design and Analysis of Algorithms. Pearson, 2012, 3rd edition  Recommending Reading : Chapter 16 from Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ( 2022 ). Introduction to Algorithms. MIT Press.Fourth edition Chapter 10 from Michael T.Goodrich, Roberto Tamassia (2014). Algorithm Design and Applications. First Edition Wiley. 3 5 Thank You