INDA Winter 2000
Quiz #2

This quiz is open book, i.e., you may have ONE Java text book and ONE algorithms and data structures text book of your choice.  You may also have an X-English dictionary where X is a language of your choice.

The quiz is worth 30 points.  It consists of two problems each worth 15 points.  Please be sure to print clearly "INDA Quiz 2", your name and personnummer at the top of your papers.

Good luck!


1.

Is the following statement true or false?

     Let T1(n) and T2(n) both be O(f(n)). Then T1(n)/T2(n) is O(1).

Prove your answer.  Remember - no proof, no credit!

Solution:

False. The proof is by counterexample. Let T1(n)=n and T2(n)=1. Then both T1 and T2 are O(n). But T1/T2=n which is clearly
not O(1).


2.

There is a bug in the following binary search algorithm. Give an example input where the algorithm fails and explain what happens
and why.

BinarySearch(key, In, low, high)

/* Returns the index in the array In at which the element
 * key is found, if there is such an index between low
 * and high.
 *
 * Example:
 *   Let In[0..4] be 5, 7, 9, 11, 13 respectively.
 *   BinarySearch(3, In, 0, 4) will fail.
 *   BinarySearch(5, In, 0, 3) will return 0.
 *   BinarySearch(5, In, 1, 3) will fail.
 */

if low = high then           /* If the sequence has size 1 then */
  if key = In[low] then      /* check whether the single */
    return low               /* element is the desired element. */
    else
    return unsuccessfully
mid = |_(low + high)/2_|     /* find the midpoint */
                             /* Note that |_x_| means the */
                             /* greatest integer <= x. */
if key <= In[mid] then
  return BinarySearch(key, In, low, mid)
  else
  return BinarySearch(key, In, mid, high)

Solution:

The bug is in the second recursive call (last line of the pseudo code):

   BinarySearch(key, In, mid, high)

When the input is divided into two parts, the mid element is included in both calls.

Consider what happens on the example input In = (5, 7, 9, 11, 13) and the call BinarySearch(7, In, 0, 1), i.e. we want to find element 7 at the beginning of the vector. Here is the sequence of calls:

BinarySearch(7, In, 0, 1)
BinarySearch(7, In, 0, 1)
...

Follow the sequence of calls and you will find that we are stuck in an infinite loop.

To correct the algorithm, change the last recursive call to be

   BinarySearch(key, In, mid + 1, high)