Due to the tragic news that a much-beloved queen has passed, her citizens have put together an organising committee for the funeral. As the death was sudden, the committee has little time. Tradition dictates that the monarch's funeral service must feature richly embroidered carpet that covers the length of the church aisle. That is, it must be exactly T = 200 metres long, no more or no less. The organisers have searched through their inventory and discovered that they have a very large collection of embroidered carpets that are suitable. Each carpet is of integer length (in metres). Due to the time constraints, the organisers have decided that they will simply line these carpets end-to-end to achieve the desired length. Cutting them to size is not an option because of their immense value; nor is overlapping the carpets, as this would not allow the embroidery to be on full display. However, the committee cannot be sure if this strategy will indeed exactly cover the desired length of the church. In a panic, they summon Professor Smart at the local university to see if she can help determine its feasibility. (a) [5 pt] Let n be the number of carpets in their collection. If the committee were to exhaustively check all possible selections from their carpet collection, how many selections would they encounter? (b) [5 pt] Give a sub-problem definition using suffixes that Professor Smart can use to devise (using Dynamic Programming) an algorithm that answers the committee's question. Hint: The committee's question is a decision problem having True or False outputs. (c) [5 pt] Using the sub-problem definitions from part (b), characterise the optimal substructure of the problem by giving the sub-problem relation. Justify, in words, why the sub-problem relation holds. Provide the base case(s) of your sub-problem relation. (d) [5 pt] Provide the pseudo-code for a bottom-up algorithm that will tell Professor Smart whether the com- mittee's plan is feasible or not in O(nT) time.