Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________
Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

Problem 0 (assessment: self_______ final_______)

Do the reading. Give a one sentence summary of the main points of Unit 1 section 2. Give yourself a 0 if you didn't actually do the reading.

Problem 1 (assessment: self_______ final_______)

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? Both should be given in terms of $n$, the number of elements in the range being searched.

Algorithm: linearSearch
Input: $(A,i,j,x)$, an instance of the Sorted Array Search problem
Output: $k$, an index such that $A[k] = x$, if one exists in $A[i\ldots j]$, and 'NOT FOUND' otherwise
k = i
while k < j and A[k] < x 
  k = k + 1
if k ≤ j and A[k] == x
  return k
else
   return 'NOT FOUND'
	    
Section 4 of the Unit 1 notes describes the "gallopSearch" algorithm: read it! Consider the following array $A$:

1117192833344042465157
012345678910

Problem 2 (assessment: self_______ final_______)

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

Problem 3 (assessment: self_______ final_______)

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

Problem 4 (assessment: self_______ final_______)

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