Below is the problem statement and example solution for each sub-problem (This is to give you more information on what the answers should look like). Now your task is to give an alternative solution to the problem, that is to prove the theorem using your own work.

Solution:

2 Problems 1. You, Alice and Bob manage "Fast Typing Consulting" a student based consulting company that completes urgent typing jobs. Your company operates as follows: - You have n student employees (including yourselves). - Each one can work a single job per day. - A student worker can type T[i]>0 words per minute. - Every morning your company accepts n jobs. - Each job has a word count W[i]>0. - Each job has a payout of $50 minus the number of minutes it takes to type it. You, Alice and Bob are discussing how to assign students to jobs so as to maximize your daily payout (which you divide evenly among your staff). a) Express this optimization problem formally with input and output conditions. b) Alice suggests starting with a simple instance where n=2 and where W[1]>W[2] and T[1]>T[2] (by assumption). There are only two ways to assign student workers to jobs in this case. State these two assignments and a formula expressing their total payout. c) Use algebra and the two formulas from part b) to show that one assignment has a greater payout than the other. d) How should you assign students to jobs to maximize your payout? State your answer like a greedy algorithm of the form "Always assign the tallest student to the loudest job." (replacing "tallest" and "loudest" with reasonable adjectives or mathematical formulas). e) Prove that your algorithm is correct for any n1. (Hint: It is helpful to assume your jobs (or students) is in the order you desire. Then focus your proof on the correct ordering of students (or jobs). Using the example above it might be helpful to assume our jobs are ordered from loudest to quietest and then prove that we should also order our students from the tallest to the shortest.) a) Express this optimization problem formally with input and output conditions. Solution: Typing Problem Input: T1..n a list of student typing speeds and W[1.n a liat of job word counts. Output: m a maximum earnings and an assignment of students to jobs that will achieve the maximum m. b) Alice suggests starting with a simple instance where n=2 and where W1>W2 and T1>T2 (by assumption). There are only two ways to assign student workers to jobs in this case. State these two assignments and a formula expressing their total payout. Solution: Assignment 1: Student 1 works job 1 and student 2 works job 2. Payout of Job 1=$50711w Payout of Job 2=$5072aw Total payout =$100(711w+T/2w) Assignment 2: Student 1 works job 2 and student 2 works job 1. Payout of Job 1=$50T21W11 Payout of Job 2=$50TIIw12 Total payout =$100(72Wu+T1W) c) Use algebra and the two formulas from part b) to show that one assignment has a greater payout than the other. Solution: Let p1 and p2 be the payout of assignment and 1 and 2 (respectively). I will compute the differences between the payouts: p2p1=$100(T2W1]+T1W2])($100(T1]W1]+T2]W2]))=$100T[2]W[1]T[1]W[2]$100+T1]W[1]+T[2]W[2]=T11]W[1]+T2W[2]T2W[1]T1]W[2]=W[1](T1]1T21)+W[2](T2]1T11)=W[1](T1]1T21)W2](T1]1T21)=(W[1]W[2])(T1]1T[2]1)i since all students ji we know that Ti>Tj and Wi>Wj. Now, consider O in which we swap i and j in O. Let p1 be the total payout of O and p2 be the total payout of O. O differs from O only in locations i and j so the payouts for all other jobs are the same. This means when we compare p1 and p2 we can ignore these other jobs. That is, p1p2=$100(TjWi+TiWj)($100(TiWi+TjWj))=$100TjWiTiWj$100+TiWi]+TjWj=Ti]Wi+TjWjTjWi]TiWj=Wi(Ti]1Tj1)+Wj(Tj1Ti]1)=Wi(Ti]1Tj1)Wj(Ti]1Tj1)=(WiWj)(Ti1Tj1)p2 and O is more optimal than O which is a contradiction. As a result O could not have chosen to assign student j to job i and must agree with S. Thus S is an optimal assignment of students to jobs