Name: ____________________________________________________ Alpha: _____________________

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

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

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?