Q: Pages 61, section 2.2, exercise 11

Lighter or heavier? You have n > 2 identical-looking coins and a two-pan balance scale with no weights. One of the coins is a fake, but you don’t know whether it’s lighter or heavier than the genuine coins, which all weigh the same.

Design a \Theta(1) algorithm to determine whether the fake coin is lighter or heavier than the others.

Q: Pages 68, section 2.3, exercise 5

Consider the following algorithm:

ALGORITHM Secret(A[0..n-1])
    // Input: An array A[0..n-1] of n real numbers
    minval \leftarrow A[0]; maxval \leftarrow A[0]
    for i \leftarrow 1 to n-1 do
        if A[i] \lt minval
            minval \leftarrow A[i]
        if A[i] \gt maxval
            maxval \leftarrow A[i]
    return maxval \text{$-$} minval

1. What does this algorithm compute?
2. What is its basic operation?
3. How many times is the basic operation executed?
4. What is the efficiency class of this algorithm?
5. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.

Q: Pages 76-79, section 2.4, exercise 1d

Solve the following recurrence relation:

x(n) = x(n/2) + n \text{ for } n > 1, \quad x(1) = 1 \text{ (solve for $n=2^k$)}

Q: Pages 76-79, section 2.4, exercise 13

Frying hamburgers There are n hamburgers to be fried on a small grill that can hold only two hamburgers at a time.

Each hamburger has to be fried on both sides; frying one side of a hamburger takes 1 minute, regardless of whether one or two hamburgers are fried at the same time.

Consider the following recursive algorithm for executing this task in the minimum amount of time:

• If n \le 2, fry the hamburger or the two hamburgers together on each side.
• If n > 2, fry any two hamburgers together on each side and then apply the same procedure recursively to the remaining n - 2 hamburgers.

1. Set up and solve the recurrence for the amount of time this algorithm needs to fry n hamburgers
2. Explain why this algorithm does not fry the hamburgers in the minimum amount of time for all n > 0
3. Give a correct recursive algorithm that executes the task in the minimum amount of time