MskProdComputing
Back to the topic

The mark scheme starts on a new page, so you can print pages one and two for a student and keep the last page yourself. Everything prints in black on white whichever theme you are using.

Python · A Level 11

Dynamic Programming and Greedy Algorithms

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 20 marks. Total 30 marks.

Name

Class

Date

Mark  / 30

Section A

Circle the letter of the correct answer. One mark each.

  1. 1What does a greedy algorithm do at each step?1
    1. ATries every possible choice and keeps the best
    2. BStores every earlier result in a table
    3. CSplits the problem into two equal halves
    4. DTakes the choice that looks best at that moment and never reconsiders it
  2. 2Coins are worth 1p, 3p and 4p. A greedy algorithm gives change for 6p. How many coins does it give, and is that the fewest?1
    1. A2 coins (3, 3), which is the fewest
    2. B3 coins (3, 3, 1), which is the fewest
    3. C3 coins (4, 1, 1), and the fewest is 2 coins (3, 3)
    4. D2 coins (4, 1), which is the fewest
  3. 3Which of these is a greedy algorithm?1
    1. AMerge sort
    2. BBinary search
    3. CBubble sort
    4. DKruskal's algorithm for a minimum spanning tree
  4. 4What two features suggest that dynamic programming will work for a problem?1
    1. AOverlapping subproblems and optimal substructure
    2. BA large number of loops and a queue
    3. CA base case and a stack
    4. DA sorted input and a small output
  5. 5What is the difference between memoisation and tabulation?1
    1. ATabulation does not store any results
    2. BMemoisation is top-down recursion with a cache; tabulation fills a table from the smallest case up
    3. CMemoisation uses loops and tabulation uses recursion
    4. DMemoisation is faster for every problem
  6. 6Why does dynamic programming make the naive recursive Fibonacci function so much quicker?1
    1. AIt removes the base case
    2. BIt sorts the values first
    3. CEach value is calculated once and then looked up
    4. DIt uses fewer variables
  7. 7The 0/1 knapsack has n items and a weight limit of W. What is the cost of the table method?1
    1. AO(n x W)
    2. BO(n)
    3. CO(log n)
    4. DO(2^n)
  8. 8What does the edit distance between two words measure?1
    1. AThe fewest insertions, deletions and substitutions to turn one word into the other
    2. BThe number of vowels that differ
    3. CThe difference in length between the words
    4. DThe number of letters the words share
  9. 9A travelling salesperson problem has 20 towns. Why is a heuristic used instead of checking every route?1
    1. AA computer cannot store the coordinates of 20 towns
    2. BThere are far too many routes to check in a reasonable time
    3. CChecking every route needs a sorted list
    4. DHeuristics always give the shortest route
  10. 10What is a heuristic?1
    1. AAn algorithm that always finds the best answer
    2. BA proof that an algorithm is correct
    3. CA way of storing results in a table
    4. DA shortcut that gives a good answer quickly but with no guarantee of the best

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

  1. 1ExplainExplain what is meant by a greedy algorithm.3
  2. 2ShowA country has coins worth 1p, 3p and 4p. A greedy algorithm gives change by always using the largest coin that fits. Show, with a worked example, that this does not always give the fewest coins.3
  3. 3CalculateThe table shows the fewest coins needed to make each amount from 0p to 5p using coins of 1p, 3p and 4p. Calculate the values for 6p and 7p, showing your working.4
    amount:        0  1  2  3  4  5  6  7
fewest coins:  0  1  2  1  1  2  ?  ?
  4. 4DescribeDescribe two features of a problem that mean it can be solved using dynamic programming.4
  5. 5DiscussA programmer must write a program to choose which of 40 items to load onto a lorry so that the total value is as high as possible without exceeding the weight limit. Discuss the approaches the programmer could take.6

Mark scheme

Section A

1D2C3D4A5B6C7A8A9B10D

Section B

1 Explain what is meant by a greedy algorithm. 3

One mark for each of the following, to a maximum of 3.

  • It builds the solution one step at a time
  • At each step it takes the choice that looks best at that moment
  • It never goes back to change a choice it has made

Model answer. A greedy algorithm builds a solution one step at a time. At each step it makes the choice that looks best at that moment, without looking ahead, and it never goes back to change a choice it has already made. It is usually quick and simple, but it only gives the best answer when the problem is one where the locally best choice is safe.

2 A country has coins worth 1p, 3p and 4p. A greedy algorithm gives change by always using the largest coin that fits. Show, with a worked example, that this does not always give the fewest coins. 3

One mark for each of the following, to a maximum of 3.

  • Chooses an amount where it fails, such as 6p
  • Shows greedy gives 4 + 1 + 1, which is three coins
  • Shows 3 + 3 uses only two coins, so greedy is not optimal

Model answer. For 6p the greedy algorithm first takes the largest coin that fits, which is 4p, leaving 2p. It then has to use two 1p coins, so it gives 4 + 1 + 1, three coins in total. But 3 + 3 makes 6p using only two coins, so the greedy answer is not the fewest.

3 The table shows the fewest coins needed to make each amount from 0p to 5p using coins of 1p, 3p and 4p. Calculate the values for 6p and 7p, showing your working. 4

One mark for each of the following, to a maximum of 4.

  • Uses the rule best[a] = 1 + the smallest best[a - coin] over the coins
  • For 6p considers best[5] + 1, best[3] + 1 and best[2] + 1
  • States the value for 6p is 2
  • States the value for 7p is 2 (best[4] + 1 or best[3] + 1)

Model answer. Each value is 1 plus the smallest value found by taking one coin away. For 6p, taking away a 1p coin leaves 5p, which needs 2 coins, so that gives 3. Taking away a 3p coin leaves 3p, which needs 1 coin, so that gives 2. Taking away a 4p coin leaves 2p, which needs 2 coins, so that gives 3. The smallest is 2, so 6p needs 2 coins. For 7p, taking away 1p leaves 6p, which needs 2, giving 3. Taking away 3p leaves 4p, which needs 1, giving 2. Taking away 4p leaves 3p, which needs 1, giving 2. The smallest is 2, so 7p needs 2 coins (3 + 4).

4 Describe two features of a problem that mean it can be solved using dynamic programming. 4

One mark for each of the following, to a maximum of 4.

  • Overlapping subproblems: the same smaller problem is needed more than once
  • So the answer to each is stored and reused instead of being recalculated
  • Optimal substructure: the best solution is made from the best solutions to the smaller problems
  • An example such as Fibonacci, knapsack or edit distance

Model answer. The first feature is overlapping sub-problems: the same smaller problem has to be solved many times, as fib(3) is needed by both fib(4) and fib(5). Dynamic programming stores each answer in a table or cache the first time it is worked out and reuses it, instead of recalculating it. The second feature is optimal substructure: the best solution to the whole problem can be built from the best solutions to its smaller sub-problems, as the fewest coins for 6p is built from the fewest for smaller amounts.

5 A programmer must write a program to choose which of 40 items to load onto a lorry so that the total value is as high as possible without exceeding the weight limit. Discuss the approaches the programmer could take. 6

One mark for each of the following, to a maximum of 6.

  • Brute force would test every combination, 2^40 of them, which is over a trillion
  • This is far too slow, because the work doubles with every extra item
  • A greedy method that takes items with the best value per kilogram first is fast, but may not give the best answer
  • Dynamic programming builds a table of the best value for each weight limit using the first i items
  • It finds the best answer in O(n x W), which is quick when the weight limit is a modest number
  • A reasoned conclusion: dynamic programming, since it is exact and fast enough, using more memory

Model answer. Brute force would check every combination of items. With 40 items there are 2^40, over a trillion combinations, and the number doubles with each extra item, so it is not feasible. A greedy method, taking the items with the best value for their weight first, is very quick, but it can fill the lorry badly and so may not give the highest value. Dynamic programming builds a table holding the best value for each possible weight limit using the first i items, and reads the answer from the last cell. It is guaranteed to give the best answer and takes O(n x W) steps, which is fast when the weight limit is a modest number, at the cost of the memory for the table. The programmer should therefore use dynamic programming.