$(15+10+20)($a$)$ Let P$1,$ P$2,...,$ Pn be a set of n programs that are to be stored on a memory chip of capacity L$.$ Program Pi requires ai amount of space. Note that L and ai $$s are all integers. We assume that a$1+$ a$2+...+$ an $>$ L$.$ The problem is to select a maximum subset Q of the programs for storage on the chip. A maximum subset is one with the maximum number of programs in it$.$ Give a greedy algorithm that always finds a maximum subset Q such that P Pi in Q ai $$ L$.$ You also have to prove that your algorithm always finds an optimal solution. Note that a program is either stored on the chip or not stored at all $($in other words, you do not store part of a program$).($b$)$ Suppose that the objective now is to determine a subset of programs that maximizes the amount of space used, that is$,$ minimizes the amount of unused space. One greedy approach for this case is as follows: As long as there is space left, always pick the largest remaining program that can fit into the space. Prove or disprove that this greedy strategy yields an optimal solution. $($c$)$ We can formulate the problem in $($b$)$ into a decision problem as follows: given n programs of sizes a$1,$ a$2,...,$ an$,$ with chip capacity L$,$ and integer k$,$ is there a packing of programs onto the chip such that the unused space is k or less. Show that this decision problem is NP$-$complete.