Question 2: (4 Marks) (a) Use parts b and c of Question 1 to show if the number of trucks used by the algorithm is 2q+1 for some q0, then an optimal solution must use at least q+1 trucks. (b) Use parts b and c of Question 1 to show if the number of trucks used by the algorithm is 2q for some q>0, then an optimal solution must use at least q trucks. Question 3: (4 Marks) Suppose A={a1,a2,,an} is a set of positive integers and b is a positive integer. We assume aib for all aiA. The problem is to find a subset SA such that aiSaib so as to maximize aiSai. For example, if A={2,4,8} and b=11, then S={2,4} is a feasible solution with aiSai=6. A better feasible solution would be S={2,8} since aiSai=10. In fact S={2,8} is an optimal solution for this problem instance. Note that S={4,8} is not a feasible solution since 4+8>11. Consider the following algorithm for this problem: Answer the following questions: (a) Show that if there exists jb, then at least one of i=1j1ai and aj is at least b/2. (b) Use part a to show that the algorithm is a 21-approximation algorithm. That is, show that the solution return by the algorithm has sum at least half the sum of an optimal solution