Computer Science Homework Help

I’m working on a algorithms & data structures question and need guidance to help me learn.

1. We have n apparently identical gold coins. One of them is false and lighter, but is otherwise indistinguishable from the others. We also have a scale with two pans but without weights. So any measurement will tell us only if the loaded pans weigh the same or, if not, which one weighs more.

How many measurements are necessary and sufficient to find the false gold coin?

1. Provide an algorithm (in words if you wish)
2. Write a recurrence equation
3. Solve the recurrence equation.
4. ——————————————————————————————————————————

1. Consider the algorithm below:

SPLIT (List, lower, upper, pivot_loc)

{

//Upper ≥ pivot_loc≥lower > 0

pivot = List[pivot_loc];

exchange List[lower] and List[pivot_loc];

low= lower; high= upper

while (high > low)

{

while (upper ≥ low and pivot ≥ List[low] )

low ++;

while (high ≥ lower and List[high] > pivot)

high–;

if (high > low) then exchange List[low] and List[high];

}

pivot_loc=high;

exchange List[lower] and List[pivot_loc];

return pivot_loc;

}

Assume array start from 1.

1. What does this algorithm do? Explain all steps.
2. Apply this algorithm on the list 5 4 3 2 1 where pivot_loc =3. Show your work.
3. Apply the partition algorithm we used in quick sort (Algorithm 2.7 of the textbook) on the list 3 5 4 1 2.