ALGORITHM EFFICIENCY PROBLEMS

  1. Let A be a list of N integers in increasing order, N > 0. There are no duplicates. Consider the following algorithm for binary search (div means integer division - i.e. discard the fractional remainder when you divide). This algorithm outputs the index of the target if it is in the list and -1 if it is not. 

    1. Set low = 0. 
2. Set high = N-1. 
3. Set mid = (low + high) div 2. 
4. While low ≤ high and target ≠ A[mid] do the following: 
   a. If target < A[mid], set high = mid-1; otherwise, set low = mid+1. 
   b. Set mid = (low + high) div 2.
5. If low ≤ high, output mid.
   Otherwise, output -1.

    1. Trace this algorithm for the following list (N=9) and a target value of 73, showing the value of low, high, and mid immediately before the loop starts and after each iteration of the loop. What is the final value that is output? 

         0    1    2    3    4    5    6    7    8 
 --------------------------------------------
| 13 | 29 | 33 | 40 | 58 | 64 | 68 | 73 | 89 |
 --------------------------------------------

    2. Repeat part (a) for a target value of 36.

    3. If you had 1 billion data values in increasing order and you had to search for a specific target using binary search, approxmiately how many data values do you need to look at in order to determine if the target is present or not? Explain your answer.

  2. You have three algorithms to solve a problem. The problem involves examining N objects for defects. Each examination of an object takes 1 minute.

    1. How long would it take to examine 4 objects (i.e. N=4) if your algorithm requires the following number of steps:

      1. Algorithm 1: log2N steps
      2. Algorithm 2: N2 steps
      3. Algorithm 3: 2N steps

    2. How many more minutes would be needed to use the same algorithms above if you examined four times as many objects (i.e. N=16)?

    3. Which of the three algorithms would you use on a warehouse of 1 million objects? Explain.

  3. In an American Idol competition, there are 10 contestants. Each constestant sings one song, and then one contestant is eliminated. The remaining contestants sing one song each, and then one contestant is eliminated again. This continues until one contestant remains and is declared the winner. The winner sings one song at the end of the competition.

    1. How many songs are sung in this competition if it starts with 10 contestants? Show your work.

    2. If there were N contestants in this competition, N > 0, exactly how many songs are sung in this competition as a function of N?

    3. Answer part (b) using Big O notation in simplest form. Explain what your big O notation says about this problem.

  4. Consider the following algorithm that computes the sum of the first n non-negative powers of 2: 20 + 21 + ... + 2n-1, where n ≥ 1. 

    1. Input n (assume n ≥ 1)
2. Set sum to 1 
3. Set value to 2 
4. Do the following n-1 times: 
   a. Add value to sum 
   b. Multiply value by 2 
5. Output sum

    1. Counting assignments ("Set ..."), additions and multiplications as operations, exactly how many operations does the algorithm perform in terms of the variable n?

    2. What is the order of complexity of this algorithm in big O notation? Explain your answer.

    3. (HARDER) Use induction to show that the sum that is computed in the algorithm is also equal to 2n-1, n ≥ 1. HINT: Show that the sum is 2n-1 when n = 1. Then show that if the sum is 2n-1 for some n, then the sum = 2n+1-1 for n+1.