B. You are given a pyramid of boxes each of which contains a number. You start...

   

Transcribed Image Text:

B. You are given a pyramid of boxes each of which contains a number. You start at one at the top and at each step you move to the level below in one of the adjacent boxes. Your goal is to find the path with minimum sum of entries. For example, in the image below the largest sum is achieved by the path shown: 3 5 7 6 2 3 4 1 3 (i) Find a counterexample for each of the following greedy algorithms: Start from the root and always follow the smallest value. Start from the bottom and always follow the smallest value. Start from the root and always choose the next step that would give the optimal path when looking at most two steps ahead. [5 marks] [5 marks] (ii) Design an algorithm to efficiently solve this problem and give pseudocode for your algorithm, explaining clearly which algorithmic principles you are using. [5 marks] [15 marks] (iii) Argue about correctness of your algorithm and determine the time and space complexity. [10 marks] B. You are given a pyramid of boxes each of which contains a number. You start at one at the top and at each step you move to the level below in one of the adjacent boxes. Your goal is to find the path with minimum sum of entries. For example, in the image below the largest sum is achieved by the path shown: 3 5 7 6 2 3 4 1 3 (i) Find a counterexample for each of the following greedy algorithms: Start from the root and always follow the smallest value. Start from the bottom and always follow the smallest value. Start from the root and always choose the next step that would give the optimal path when looking at most two steps ahead. [5 marks] [5 marks] (ii) Design an algorithm to efficiently solve this problem and give pseudocode for your algorithm, explaining clearly which algorithmic principles you are using. [5 marks] [15 marks] (iii) Argue about correctness of your algorithm and determine the time and space complexity. [10 marks]