Greedy algorithms
1.[3p] What exactly does the greedy choice property claim?
What exactly does the greedy choice property claim?
The answer is: Some optimal solution contains the choice the greedy rule makes first
The answer is: Some optimal solution contains the choice the greedy rule makes first
The answer is: Some optimal solution contains the choice the greedy rule makes first
2.[2p] For interval scheduling, the rule that works is
For interval scheduling, the rule that works is
The answer is: take the talk that finishes earliest
The answer is: take the talk that finishes earliest
The answer is: take the talk that finishes earliest
3.[3p] Apply that rule to the intervals (1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11), (8,12), (2,13), (12,14). How many talks are scheduled?
Apply that rule to the intervals (1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11), (8,12), (2,13), (12,14). How many talks are scheduled?
4.[2p] How many would the earliest-start rule schedule on that same set?
How many would the earliest-start rule schedule on that same set?
5.[3p] Six symbols occur 40, 20, 15, 12, 8 and 5 times. How many bits does the Huffman code take for the whole 100-symbol message?
Six symbols occur 40, 20, 15, 12, 8 and 5 times. How many bits does the Huffman code take for the whole 100-symbol message?
6.[2p] What percentage does that save against a fixed-width three-bit code?
What percentage does that save against a fixed-width three-bit code?
7.[2p] Huffman coding reaches Shannon's entropy exactly.
Huffman coding reaches Shannon's entropy exactly.
The answer is: False
8.[3p] A bag holds 50 kg. Items are worth 60 at 10 kg, 100 at 20 kg and 120 at 30 kg. What value does the greedy ratio rule achieve on the 0/1 problem?
A bag holds 50 kg. Items are worth 60 at 10 kg, 100 at 20 kg and 120 at 30 kg. What value does the greedy ratio rule achieve on the 0/1 problem?
9.[3p] Greed fails on 0/1 knapsack but not on fractional knapsack because
Greed fails on 0/1 knapsack but not on fractional knapsack because
The answer is: with whole items there is no unit to exchange, so the exchange argument has nothing to work with
The answer is: with whole items there is no unit to exchange, so the exchange argument has nothing to work with
The answer is: with whole items there is no unit to exchange, so the exchange argument has nothing to work with