Question $1.(15$ marks$)$ We are given a sequence of $n$ books of depths $d_1,d_2,$dots,$d_n($see figure on the

left below$).$ We must place these books one after the other in the given order on successive shelves,

each of length $L$max$(d_1,d_2,$dots,$d_n),$ so that the sum of the depths of the books on each shelf does not

exceed $L.$

The following greedy algorithm places books on the shelves according to these rules. Intuitively it packs

as many books as possible on each shelf, and uses a new shelf if and only if the next book does not fit on

the current shelf.

a$.$ Does this algorithm minimize the sum of empty spaces on the shelves used? Justify your answer.

b$.$ Does this algorithm minimize the maximum empty space on any shelf used? Justify your answer.

Note: When disproving the correctness of a proposed algorithm, it is not sufficient to just give a coun$-$

terexample, i$.$e$.,$ an input on which the algorithm does not work correctly. You must also indicate what the

algorithm does on your counterexample, and why that is not the correct answer. Your counterexamples

should be short and illuminating.