Publish on 07th November 2019
Category: Birds
0

Greedy Algorithms

Alexandra Stefan

1

Greedy Method forOptimization Problems

Greedy:take the action that is best now (out of the current options) according to your criterion (i.e. commit to/pick a local optimal)it may cause you to miss the optimal solutionYou build the solution as you go. No need tobacktraceit.Examples:KnapsackPic the item with the largest value/weight ratio.Other possible measures: largest value, smallest weight.Interval schedulingPick the interval that finishes firstHuffman codesPrefix codes: no code is also a prefix of another code.Huffman tree to decode (the code for a character, x, takes you to the leaf with x)Edit distance– greedy? – not clear.

2

Knapsack versions

Unbounded(electronics warehouse)Unlimited amounts of each item.Cannot take fractions of an item.0/1 Fractional(market: flour, rice,wine)0/1 – have only one of each itemCan take a fraction of an item.What would a greedy thief do?Method:Sort in decreasing order of value/weight ratio.Pick as many of the largest ratio as possible. After that, try to take as many of the next ratio as possible and so on.Does NOT give an optimal solution. See next page.Would any of the above problems be solved optimally using Greedy?(Prove or give counter-example)Yes. The fractional version.

3

Greedy forKnapsack – Criterion: Ratio

4

Unbounded (not fractional)

Unbounded, fractional

0/1 (not fractional)

0/1, fractional

Counter example used to prove that Greedy fails for Unbounded Knapsack

Goal: construct an Unbounded Knapsack instance where Greedy does not give the optimal answer.Intuition: We want Greedy to pick only one item, when in fact two other items can be picked and together give a higher value:Item B: weight 2 (can fit 2), value 3 => total value 6Item A: weight 3, value 5 => total value 5Knapsack max weight: 4!!! You must double-check that Greedy would pick item A=> check the ratios: 5/3 > 3/2 (1.66 > 1.5).If item A had value 4, Greedy would also have picked B.Same example can be modified to work for 0/1 Knapsack:Item A: 3kg, $5ItemB: 2kg,$3ItemC: 2kg,$3

5

$32kg

$53kg

Item B

Item A

$32kg

Item C

A$53kg

DP

Greedy

B$3,2kg

C$3,2kg

$32kg

$53kg

$32kg

$32kg

$53kg

DP

Greedy

Item B

Item A

$6

$5

$6

$5

Interval scheduling versionsWorksheet

With values( job = (start, end, value) ):Each interval has a value. Goal: maximize sum of values of picked non-overlapping jobs.Greedy solution?AlgorithmIs it optimal?Give proof or counter example.Without values( job = (start,end) ):Pick the largest number of non-overlapping intervals.“Activity selection problem” in CLRS (page 415)Greedysolution?AlgorithmIsit optimal? Give proof or counter example. (CLRS proof at page 418, proof of Theorem 16.1)Which of the two versions is more general?Is one a special case (or special instance) of the other?If you have a program to solve problems of one type, can you easily use it to solve problems of the other type? Which type should the program solve (with value, or without value)?

6

1

6

7

12

5

8

Example showing that Greedy withlargest valueDoes not give an optimal solution.Greedy will pick the red job. Nothing else fits.Better(optimal): the 2 blue jobs.

10$

9$

9$

Problem version:All jobs have the SAME value. => maximize number of jobs you can pick.Optimal:jobthatfinishesfirstjob thatstarts last(See book for proof is interested)NOT optimal:Shortest durationLeast overlapsEarliest start time

7

Interval Scheduling Greedy Criteria

1

6

7

12

5

8

Example showing that Shortest durationDoes not give an optimal solution.Greedy will pick the red job. Nothing else fits.Better(optimal): the 2 blue jobs.

Huffman code

Application: file compressionExample from CLRS:File with 100,000 characters.Characters:a,b,c,d,e,fFrequency in thousands (e.g. the frequency of b is 13000):Goal: binary encoding that requires less memory.

8

Huffman codes

Internal nodes contain the sum of probabilities of the leaves in that subtree.

Optimal prefixcodewordtree(Huffman tree) – optimal encoding

Fixed-lengthcodewordtree

(Images from CLRS.)

Compute the number of bits needed for the whole file using each of these encodings.

9

45,000*1 + 13,000* 3 + 12,000*3 +16,000*3 + 9,000* 4 + 5,000* 4= 224,000

100,000 * 3 = 300,000

a->0b->101c->100d->111e->1101f->1100

Number of bits in code

Building the Huffman Tree

Make ‘leaves’ with letters and their frequency and arrange thems.t.they are always inincreasing order(of frequency).Repeatuntil there is only one tree:Create anew tree from the two leftmost trees(with the smallest frequencies) andPut it in its place.Label left/right branches with 0/1Encoding of char = path from root to leaf that has that charTreeproperty: Everyinternal node has two childrenSee book or lecture video for the step-by-step solution.In exam orhw, you must use this method. Make sure that you alwaysput the smallest child node to the left.

10

Glancing at implementation issues and options

Good reference:https://www2.cs.duke.edu/csed/poop/huff/info/File Compressionwith Huffman coding -Practical IssuesGiven an encoded file,how will youknow when it ended?Typically files are stored by the OS in sizes that are multiples of a specific value, so even though your actual file takes 121 bits, on disk 128 bits are written and in that will be read when you open the file. You need to know that after 121 you are done.=> need a new symbol to indicate end of file. Note that you must add this symbol (with count 1) to your set of distinct symbols used in building the Huffman tree, because you must be able to recognize it (decode it from bits into the symbol).Given an encoded file,how will you know how to decode it?Encoding tree is not standard, but depends on the given file =>Must record some information to know how to decode the file along with the file (at the beginning)=>Store the Huffman treeStore enough info to regenerate the tree.Build the tree efficiently – use a HeapHeaps are efficient (lgN) for finding min, removing min, inserting new itemWith heap: O(NlgN)Withsort and reinsert (like on paper): O(N2)Heaps will be covered in future lectures

11

Extra

Decoding info

Useful data

File format

Greedy Algorithms

Greedy algorithms do not always guarantee optimal solution. It depends on the problem.Difference between Greedy and Dynamic Programming:InDP typically you solve all the problems and then make your choice.In greedy, you make the greedy choice and you are left with only one problem.

12

0

Embed

Upload

Greedy Algorithms - University of Texas at Arlington