Only sequence b is concave while a is not.

Let i(k) be the largest index that maximizes the sum a_i + b_k-i. Show that when b is concave, i(k) is non-decreasing as a function of k, i.e. i(k) i(k+1).

Assuming that b is concave but a is not, give a divide-and-conquer algorithm to compute the entire sequence c_k for all k = 0, 1, ..., n in time O(nlogn). Assume for simplicity and without loss of generality that n = s^l. Give a brief (2-3 line) and informal argument for correctness.

You want to buy a new laptop and a new phone but you don't know how much to spend on each item. You have done your research and have quantified how happy you will be spending your money on each of the items. You know that if you spend i dollars on a laptop and j dollars on a phone, your total happiness is ai + bj, for two non-decreasing sequences ao, ai,..., an and bo,bi,... ,bn that you have calculated. Given that you have a budget of k dollars, how should you spend your money? Your goal is now to calculate the maximum achievable happiness for some budget Bedse salving the pbofns drgs as you spend more money on the item. We call such a sequence s, concave, which means that s - s,-si when lSi<.>