Homework 5 (assigned July 20, due July 26)

1. Exercises 19, 45, and 46 on pages 61-62. (3 points each)

2. Exercises 7, 15, 16, 19, 21, and 24 on pages 148-149. (5 points each)

3. Exercise 30 on page 169. Omit the part of the exercise that asks for Theta notation. (5 points)

4. Given a nondecreasing list s of n real numbers and a value key, the following version of binary search determines whether or not key is in the list, returning an index k such that key = s[k] if key is in the list and 0 otherwise.

   binary_search(s in nondecreasing order, n, key)
   01 i := 1
   02 j := n
   03 while i <= j
   04       m := floor[(i+j)/2]
   05       if key = s[m] then return(m)
   06       if key < s[m] then j := m-1
   07       else i := m+1
   08       end(while)
   09 return(0)

   (a) In the worst case, how many times is the while loop test i ≤ j on line 3 evaluated when the size of the input list is n? (3 points)

   (b) Give an example to show that if the input is not in nondecreasing order, the algorithm may not find key even if it is present. (3 points)