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 *T _{1}(n)* and

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

**Solution**:

False. The proof is by counterexample. Let *T _{1}(n)=n *and

not

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)``
`