You must follow these instructions for Problems 1. describe the algorithm you de

Question

You must follow these instructions for Problems

1. describe the algorithm you design for the problem in English,

2. write pseudocode in the style of the CLRS text for your algorithm,

3. define tight asymptotic upper bounds for your algorithm’s running time.

Problem 2 (25 points) A surfboard rental firm has msurfboards, where the height of the ith surfboard is si. There are n surfers who wish to rent surfboards, where the height of the ith surfer is hi. Ideally, each surfer should obtain a surfboard whose height matches his own height (10/6) as closely as possible. Design an efficient algorithm to assign surfboards to surfers so that the sum of the absolute differences of the heights of each surfer (10/6) and her/his surfboard is minimized. (For a reduction of a letter grade on this problem, assume m n).

Explanation / Answer

Answer 1:

We will use a greedy approch to solve the probelm, The logic is to satisfy the requirement of one surfer at a time and assign a surfboard to the surfer which minimizes the abs differance of the mentioned terms. So Sort the array which has the height of surboad in ascending order and also the surfers in ascending order. Mention a array V that indicates weather a surfboard is available or not 0 for available ,1 for not available .Take on surfer at a time and assign the surboard to him and if it is assigned, change the bool value of that particular surboard to 1 i.e (not available) . Do this for all the surfers.

Answer 2:

Lets solve with m=n ( Note it can be solved for any other case too)

We will use a greedy approch to solve the problem

1) Let S be the array containing the surfboards . ;

2) Sort the Surfboards in ascending order of their heights.

3) Let P be the array of people (surfers) and , arrange the people in array in ascending order of their heights.

4) Maintain a seprate array V denoting if the surfboard is available or taken . Initialize V with '0'

( so if v1 is 0: then surfboard s1 is available else if v1 is 1 then surboard is taken)

4) //Now iteratively do this for each surfer :

for i in range n:

          dif=INT_MAX; int j=-1;

          for k in range m:

        if (vk is 0 and abs(pi*10/6 - sk)<dif ) :

                                   if(j!=-1) vj=0 ;  

                                vk=1 ; j=k

Answer 3-

Asymtotic upper bound :

O (n2)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.