Let A and B be two sets of n positive integers. You get to reorder each set however you like. After reording, let ai be the i-th element of A and bi be the i-th element of B. The goal is to maximize the function n i=1 (ai)^(bi) . You will develop a greedy algorithm for this task

(a) Describe a greedy idea on how to solve this problem, and shortly argue why you think it is correct (not a formal proof).

(b) Describe your greedy algorithm in pseudocode. What is its runtime?

2. Given a sequence A = {a1, . . . , an} of points on the real line. The task is to determine the smallest set of unit-length (closed) intervals that contains all of the input points. Consider the following two greedy approaches:

(a) Let I be an interval that covers the most points in A. Add I to the solution, remove the points covered by I from A, and recurse/continue.

(b) Add the interval I = [a1, a1 + 1] to the solution, remove the points covered by I from A, and recurse/continue.

One of these approaches is correct, the other one is not. Show which of the approaches is not correct by finding a counter-example. (The counter example consists of an example input and two solutions one is the actual optimal solution, the other is the solution computed by the greedy algorithm, which is not as good as the optimal solution.)