2. Suppose there are n machines with their available cycles given in an array P[1..n], and...

Transcribed Image Text:

2. Suppose there are n machines with their available cycles given in an array P[1..n], and n jobs with size S[1..n]. Ideally we would like to assign a job to a machine such that the size of the job roughly matches the available number of cycles on the machine. The goal is to find such an assignment to minimize the average mismatch. That is, if job i is assigned to machine j, then the mismatch is |S[i] P[j]]. Notice that one job can only be assigned to one machine and vice versa. Design an efficient algorithm for this purpose. If you use a greedy algorithm, you must prove that it is correct. 3. Consider the following problem. The input is a collection A = {a,, an} of n points on the real line. The problem is to find a minimum cardinality collection S of unit intervals that cover every point in A. These intervals can be placed anywhere on the line. (a) Prove or disprove that the following algorithm correctly solves this problem. Let I be the interval that covers the most number of points in A. Add I to the solution set S. Then recursively continue on the points in A not covered by I. (10pts) (b) Prove or disprove that the following algorithm correctly solves this problem. Let the smallest (leftmost) point in A. Add the interval I = [aj, aj+1] to the solution set S. Then recursively continue on the points in A not covered by I. (10 pts) aj be 2. Suppose there are n machines with their available cycles given in an array P[1..n], and n jobs with size S[1..n]. Ideally we would like to assign a job to a machine such that the size of the job roughly matches the available number of cycles on the machine. The goal is to find such an assignment to minimize the average mismatch. That is, if job i is assigned to machine j, then the mismatch is |S[i] P[j]]. Notice that one job can only be assigned to one machine and vice versa. Design an efficient algorithm for this purpose. If you use a greedy algorithm, you must prove that it is correct. 3. Consider the following problem. The input is a collection A = {a,, an} of n points on the real line. The problem is to find a minimum cardinality collection S of unit intervals that cover every point in A. These intervals can be placed anywhere on the line. (a) Prove or disprove that the following algorithm correctly solves this problem. Let I be the interval that covers the most number of points in A. Add I to the solution set S. Then recursively continue on the points in A not covered by I. (10pts) (b) Prove or disprove that the following algorithm correctly solves this problem. Let the smallest (leftmost) point in A. Add the interval I = [aj, aj+1] to the solution set S. Then recursively continue on the points in A not covered by I. (10 pts) aj be

Answer rating: 100% (QA)

2 To design an efficient algorithm for assigning jobs to machines to minimize the average mismatch we can use a greedy algorithm approach The algorithm can be outlined as follows 1 Sort the machines i... View the full answer