York University EECS 3101Z January 17, 2020

Homework Assignment

Due: January 24, 2020 at 2:30 p.m.

1.In olden days, people like your grandparents used to use printed books called dictionaries that listed words in alphabetical order, together with their definitions. It would be possible to look for a word in the dic- tionary using binary search, but this is not what people typically did. For example, to look up the word confusticate, instead of starting by looking at the middle of the dictionary, one might start by looking at a page that is about 15% of the way into the dictionary, since the letter c comes near the beginning of the alphabet. If the first word on that page iscatarrh, then one might just flip a small number of pages forward to get closer toconfusticate. Willemina uses this idea as inspiration to design an algorithm to search for an integerkin a sorted array A[1..n] of integers. She is hoping that it will outperform binary search if the values in the array are somehow uniformly distributed so that she can estimate roughly where in the array the desired key lies. As usual, the postconditions are that the algorithm does not modify the arrayAand

• ifkappears inA[1..n] then the algorithm returns an indexisuch thatA[i] =k, and
• ifkdoes not appear inA[1..n] then the algorithm returns “not found”.

As in binary search, the algorithm keeps track of a subarrayA[lo..hi]. Instead of comparingkto the
middle element of that subarray, she estimates where in the subarray the keykought to be and comparesk
with that element. Willemina estimates that the fraction of elements inA[lo..hi] that are less thankshould
be aboutA[khi−]A−[Alo[]lo]. She writes down the following algorithm.

1 Search(k, A[1..n])
2 Precondition:nis a positive integer andA[1]≤A[2]≤···≤A[n]
3 lo← 1
4 hi←n
5 loop
6 exit whenlo=hi
7 m←lo+

⌊

k−A[lo]
A[hi]−A[lo]·(hi−lo)

⌋

8 ifk > A[m] thenlo←m+ 1
9 elsehi←m
10 end if
11 end while
12 ifA[hi] =kthen returnhi
13 else return “not found”
14 end if
15 endSearch

(a) Willemina implements the algorithm in Java and starts testing it.

(i) Give an example input where Willemina’s algorithm generates an array out of bounds error.
(ii) Give an example input where Willemina’s algorithm generates a division by 0 error.
(iii) Give an example input where Willemina’s algorithm does not terminate.

(b)Modify the exit condition on line 6 so that Willemina’s algorithm becomes a correct search algorithm.
You should not modify or add any other line.
Hint: Think about how you can design the exit condition to eliminateallof the errors identified in
part (a) and still give the right result when the code reaches line 12.

(c)State a loop invariant that can be used to prove the algorithm is correct.

1 over...

EECS 3101Z Assignment 2 January 17, 2020

(d)Prove your answer to part (c) really is a loop invariant.

(e)Prove that the algorithm terminates and satisfies its postconditions.

(f) What is the worst-case running time of the algorithm? State your answer in terms ofnusing Θ
notation.

(g)Prove your answer in part (g) is correct. For full marks, you have to prove both the upper bound and
a matching lower bound on the worst-case complexity.

2