Greedy Algorithems question

2. This question is about the greedy approach to algorithm design The stacking problem is concerned with stacking items on top of one another. Items / have a weight w, and a crumple strength s which is the total weight that they can hold. A stack is a sequence of items ....W which represents item is on the top, then ta, etc, down to i. at the bottom The problem is to assess whether there is a stacking ordering of all the items so that every item has strength to hold all of the items on top of it The following is proposed as a greedy algorithm for this problem: Consider items in order of smallest w + s (sum of weight plus strength). In each case add an item to the end of the stack sequence if the strength can support all of the items already in the sequence If there is not sufficient strength at any point then the algorithm returns "not possible" and the sequence of items obtained to that point (not including the item that did not have sufficient strength). If all items have been added to the stack then the algorithm returns "stacking possible", and the sequence of items obtained (a) What is the time complexity of this greedy algorithm? 15 marks) (b) Apply the greedy algorithm to the following set of items. What does the algorithm return? Name A malo D mwN00 Weight Strength 1 8 3 7 5 1 25 17 8 No HINI (c (d) [10 marks) If a non-crumpling stack contains X immediately before Y at some point in the stack, but with S. + w. > S + W show that the same stack except with the positions of X and Y exchanged is also non-crumpling, [10 marks] Explain briefly (by considering inversions or otherwise) why the result of part (e) means that this greedy algorithm does indeed give the correct solution 15 marks) if the algorithm terminates with "not possible", then is it the case that the sequence returned is a maximal set of items that can be stacked without crumpling? Justify your answer. 15 marks) le)