Recall that we ask you to put each problem set solution on its own page. For purposes of this problem, assume that each solution may be on at most one page. Youve solved then problems of a problem set, with values v1,v2, . . . ,vn, but you only have available a set of k pieces of paper p1,p2, . . . ,pk of various shapes and sizes. Each page can fit only some problem solutions: for each i[n] and j[k], you know either that solution i can fit on page pj (in which case we say ai,j= 1) or not (ai ,j= 0). (Note that its possible that solution i fits on page j but not jand solution i fits on page j but not j.) You want to submit the set of solutions that maximizes your score.

(a) Consider the following greediest algorithm: starting with the highest-value problem and working down, assign a solution to an arbitrary empty page that can fit it if there is one, and throw it out if not. Show that the greediest algorithm doesnt always maximize your score. (To show this, you should give an example instance of the probleman n,k, set of problem values, and a description of which problems fit on which pagesand show a solution produced by the greedy algorithm and another solution that gives you a better score.)

(b)To design a less greedy algorithm, we need a subroutine. Suppose we have an assignment of a set S of solutions to pages, and were given a new solution t. Wed like to know whether its possible to assign all the solutions S{t}to pages (possibly rearranging which solutions are assigned to which pages) and output an assignment if so or impossible if not. Give an algorithm to do so. (Hint: First, given a solution, find all the other solutions whose pages it could commandeer, making a graph on the solutions. Search that graph, looking for a solution that could be assigned to a new page.)

(c) Consider the following less greedy algorithm: starting with the highest-value problem and working down, attempt to assign a solution to a page using the subroutine from the previous problem part. If there is a way, do it; if not, throw out the solution. Show that the less greedy algorithm finds the optimal score.(Hint: Suppose you have two assignments of solutions to pages: an optimal one and one found by the less greedy algorithm. It suffices (why?) to show that you can match each solutions assigned to a page in only the optimal assignment with a solutions at least as valuable as s thats assigned to a page in only the less greedy algorithm. To find such a matching, try swapping whether pages hold the solution from the optimalalgorithm or the solution they held in the less greedy algorithm, starting with the page that held s.)