$(30)($a$)$ Let $P_1,P_2,$dots,$P_n$ be a set of $n$ programs that are to be stored on a memory chip of capacity $L.$ Program $P_i$ requires $a_i$ amount of space. Note that $L$ and $a_i\text{'}$s are all integers. We assume that $a_1+a_2+$dots$+a_n>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 ${\displaystyle \underset{P_i\text{i}\text{n}\text{Q}}{\overset{?}{}}}{a}_{i}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,$dots,$a_n,$ 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.