Instructions: All answers must be proved: it is not sucient to simply state the answer. All answers must be written in your own words. Treat single arithmetic operations (addition, subtraction, multiplication, and division) as constant time operations. Note: Please answer me about each thing that is asked in question. I am sending time posting this same question becasue of not satisfy with answer.

3. There is a set of n employees E En, and a set of tasks T,..., Tn. Each employee must be assigned to one task, and every task must be assigned to an employee. Each task T has a difficulty level dit and each employee has a skill level si. The goal is to match employees to tasks such that the average difference between each employee's skill level and his or her task's difficulty level is minimized. In other words, if employee Ei is matched to task T we wish to minimize y(), Part a: Consider the algorithm that begins with with employee E, and as signs that employee the task with the difficulty level that is closest to E1's skill level. Remove E1 and the selected task from the pool, and assign em- ployee E2 the task with difficulty level closest to Ee's skill level. Repeat until all employees and tasks are matched. Give a counterexample showing when this method fails to find the optimal solution. Part b: Describe an om log n) algorithm to find the optimal solution