SI335: Week 1

P1

Relying on what you learned of runtime analysis in data-structures, what is the worst-case running time of algorithm linearSearch given below? What is the best case running time?

Algorithm: linearSearch
Input: $A$, a sorted array of $n$ ints, and $x$, an int to search for
Output: $k$, an index such that $A[k] = x$, if one exists, and 'NOT FOUND' otherwise

i = 0
while i < n and A[i] < x 
  i = i + 1
if i < n and A[i] == x
  return i
else
   return 'NOT FOUND'

P2

Section 4 of the Unit 1 notes describes the "gallopSearch" algorithm: read it! Consider the following array $A$:

11

17

19

28

33

34

40

42

46

51

57

0

1

2

3

4

5

6

7

8

9

10

When gallopSearch is called on array $A$ above searching for $x = 34$, what are the values of i, left and right immediately prior to the call to binarySearch in the last line of the algorithm?
When gallopSearch is called on array $A$ above searching for $x = 53$, what are the values of i, left and right immediately prior to the call to binarySearch in the last line of the algorithm?
When gallopSearch is called on array $A$ above searching for $x = 19$, what are the values of i, left and right immediately prior to the call to binarySearch in the last line of the algorithm?

P3

Define a PROBLEM for "max": given a list of integers, return the largest one.

In your definition, be precise and try not to use the word "max" but rather define it in terms of basic comparisons like greater-than or less-than.

P4

Consider the algorithm "percolateMax" given below that (hopefully) solves the "max" problem you defined above:

percolateMax(A,n) /* A is an array of n integers */
  i = 0
  while i < n - 1 do
    if A[i] > A[i+1]
      swap(A[i],A[i+1])
    i = i + 1
  return A[n-1]

Give a loop invariant for the "while" loop in this algorithm, i.e. a condition that is true every time test condition is evaluated, and which makes it easy to give a convincing argument that the algorithm is correct.
Prove the loop invariant always holds: i.e. prove that it holds prior to the first loop iteration, and prove that assuming it holds at the beginning of a loop iteration, it must hold at the end of that loop iteration.
Use the fact that the loop invariant is now proven to always hold to prove that percolateMax really is correct.