CS180 Homework 2
All algorithms/proofs should be in bullet form: step by step or psuedo code.
1. Exercise 3 Page 107
2. Exercise 4 on Page 107
3. Exercise 9 on page 110
4. Exercise 11 on page 111
5. Exercise 12 on page 112
6. An array of n elements contains all but one of the integers from 1 to n+1.
(a) Give the best algorithm you can for determining which number is
missing if the array is sorted, and analyze its asymptotic worst-case
running time.
(b) Give the best algorithm you can for determining which number is
missing if the array is not sorted, and analyze its asymptotic worstcase running time.
