21-01-2013, 03:00 PM
Greedy Algorithms
1Greedy Algorithms[.pdf (Size: 707.29 KB / Downloads: 19)
The Essence of Greedy
•At each step in a greedy algorithm, an ‘optimal’ local decision is made, based on minimum cost
•May or may not work
Minimum Spanning Trees
•Weighted undirected graph
–Find a tree consisting of all nodes of the graph and such that the sum of all tree edge weights is minimal
•Given an undirected graph G = (V, E) with edge weights we, find a tree T = (V, E*) that minimizes
Cut Property
•At any given time in Kruskal’s algorithm, the edges already chosen form a partial solution
–A collection of connected components, each of which has a tree structure
•The next edge, e, to be chosen connects two of these components
–It is the minimum cost edge between these two components
•Suppose edges X are part of an MST of G = (V,E)
•Pick any subset of nodes, S, for which X doesn’t cross between S and V-S
•Let e be the minimal cost edge across this partition
•Then, X ∪ {e} is part of some MST
Kruskal’s Implementation
•At any given time in Kruskal’s algorithm, the edges already chosen form a partial solution
–A collection of connected components, each of which has a tree structure
•We need to choose a minimal cost edge between two different components and then merge the two components into one larger component
•The algorithm will work with a collection of disjoint sets, each containing vertices of a particular component
•At first, each vertex is in a component by itself
–makeset(x): Create a singleton set containing just x
•Test pairs of nodes to see whether they belong to the same component
–find(x): Find the set to which x belongs
•We need to merge two components into one
–union(x,y): Merge the sets containing x and y
Huffman Encoding
•A coding scheme in which more frequently occurring patterns have shorter codes
•Signal compression
–Sampling at regular intervals yields a sequence of real numbers
•At 50,000 samples per second, a 30 minute sample would derive 30 x 60 x 50,000 measurements
•Each real-valued sample is quantized
–Approximated by a nearby number from a codebook
•Each codebook value is encoded in binary