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$:

## 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?