Lesson test: Greedy algorithms

1.[3p]
What exactly does the greedy choice property claim?

Some optimal solution contains the choice the greedy rule makes first

Correct

Every optimal solution contains the greedy choice

The answer is: Some optimal solution contains the choice the greedy rule makes first

The greedy choice is the best available at that step

The answer is: Some optimal solution contains the choice the greedy rule makes first

The problem breaks into independent subproblems

The answer is: Some optimal solution contains the choice the greedy rule makes first

2.[2p]
For interval scheduling, the rule that works is

take the talk that finishes earliest

Correct

take the talk that starts earliest

The answer is: take the talk that finishes earliest

take the shortest talk

The answer is: take the talk that finishes earliest

take the talk that conflicts with fewest others

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?

CorrectNot quite: 4

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?

CorrectNot quite: 233

7.[2p]
Huffman coding reaches Shannon's entropy exactly.

True

The answer is: False

False

Correct

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?

CorrectNot quite: 160

9.[3p]
Greed fails on 0/1 knapsack but not on fractional knapsack because

with whole items there is no unit to exchange, so the exchange argument has nothing to work with

Correct

the fractional problem has fewer items

The answer is: with whole items there is no unit to exchange, so the exchange argument has nothing to work with

the 0/1 problem lacks optimal substructure

The answer is: with whole items there is no unit to exchange, so the exchange argument has nothing to work with

the ratios are computed differently

The answer is: with whole items there is no unit to exchange, so the exchange argument has nothing to work with

Sign in

Greedy algorithms

1.[3p]
What exactly does the greedy choice property claim?

2.[2p]
For interval scheduling, the rule that works is

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?

4.[2p]
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?

6.[2p]
What percentage does that save against a fixed-width three-bit code?

7.[2p]
Huffman coding reaches Shannon's entropy exactly.

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?

9.[3p]
Greed fails on 0/1 knapsack but not on fractional knapsack because

1.[3p] What exactly does the greedy choice property claim?

2.[2p] For interval scheduling, the rule that works is

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?

4.[2p] 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?

6.[2p] What percentage does that save against a fixed-width three-bit code?

7.[2p] Huffman coding reaches Shannon's entropy exactly.

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?

9.[3p] Greed fails on 0/1 knapsack but not on fractional knapsack because

1.[3p]
What exactly does the greedy choice property claim?

2.[2p]
For interval scheduling, the rule that works is

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?

4.[2p]
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?

6.[2p]
What percentage does that save against a fixed-width three-bit code?

7.[2p]
Huffman coding reaches Shannon's entropy exactly.

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?

9.[3p]
Greed fails on 0/1 knapsack but not on fractional knapsack because