3. There is a set of n employees E1; :::;En, and a set of tasks T1; :::; Tn. Each employee must be assigned to one task, and every task must be assigned to an employee. Each task Ti has a difficulty level di, 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 Tf(i), we wish to minimize

1

n

Xn

i=1

jsi ???? df(i)j

.

Part a: Consider the algorithm that begins with with employee E1, and assigns 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 employee E2 the task with difficulty level closest to E2'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 O(n log n) algorithm to find the optimal solution.

 

4. You have a set of coins. Each coin i has value vi. Your goal is to find a set of coins with total value exactly equal to V . You can use only one copy of each coin. Design a dynamic programming algorithm to determine whether it is possible to accomplish this. You don't need to output which coins are used, just whether it is possible or not. Hint: this is similar to, but not the same as, the knapsack problem without item repetition. Like we did in the edit distance problem and the knapsack without repetition problem, you will need a 2-dimensional DAG. Define P(i;W) = True if you can get value W using coins 1; :::; i. How do you calculate P(i;W) using subproblems?