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.

Install gnome-nibbles on your VM 

sudo apt-get install gnome-nibbles
and run it. You don't have to play much, just enough to get the gist. Notice that you have this "worm" that lives on a grid. It's body is made up of a bunch of contiguous cells on that grid. (NOTE: The worm body cannot cross itself! So a worm of length n consists of n distinct cells.) This problem concerns such a worm.

Problem: WormContains
Input: Given arrays X and Y containing the coordinates of the blocks comprising the body of a worm of length n [assume the head is at coordinate (X[0],Y[0]) and remember, no repeated blocks in a worm body!] and a grid coordinate (x,y)
Solution: true if the worm "contains" (x,y), and false otherwise. I.e. true if (X[i],Y[i]) = (x,y) for some i in {0,...,n-1}, false otherwise

For this input, the solution is "false".
Example:
if n = 5,   X : [ 4 4 3 2 1 ],   x = 2  ----> return true
            Y : [ 5 6 6 6 6 ],   y = 6

if n = 5,   X : [ 4 4 3 2 1 ],   x = 2  ----> return false
            Y : [ 5 6 6 6 6 ],   y = 5

Problem 0 (assessment: self_______ final_______)

Here is a simple recursive algorithm for the Worm Contains Problem. 
      Algorithm: onWormEZ(X,Y,n,x,y)
      Input:  arrays X and Y of n integers that represent a worm body, and grid coordinate (x,y)
      Output: true if (X[i],Y[i]) = (x,y) for some i in {0,...,n-1}, false otherwise

      res1 = (X[n-1] == x and Y[n-1] == y)
      if res1 == true or n == 1
        return res1
      else
        return onWormEZ(X,Y,n-1,x,y)
Your Job: Prove that this algorithm is correct.

Problem 1 (assessment: self_______ final_______)

Write a recurrence relation giving an upper bound on the worst case running time of onWormEZ in terms of $n$.

Problem 2 (assessment: self_______ final_______)

A somewhat cleverer algorithm is based on the observation that each successive block in a worm body differs from the previous block only by +/-1 in one coordinate. So if I'm looking at a worm-body block at (1,2) and (x,y) = (3,3), I know that the next two blocks of the worm body cannot possibly be (3,3), so I can skip over them. If we apply this kind of logic cleverly, we get the following algorithm: 
Algorithm: onWormSPD(X,Y,n,x,y)
Input:  arrays X and Y of n integers that represent a worm body, and grid coordinate (x,y)
Output: true if (X[i],Y[i]) = (x,y) for some i in {0,...,n-1}, false otherwise

i = 0, d = 0
do {
  i = i + d // d = 0 first time through, so this has no effect.
            // Afterwards, this skip over the next d entries of X & Y		 

  d = |X[i] - x| + |Y[i] - y| // d is the "Manhattan distance" of (x,y) from  (X[i],Y[i]), i.e. the # of
                              // steps to adjacent squares you'd need to take to get from one to the other.
} while (i+d < n and d > 0 )

return d == 0
Your Job: Given the input pictured to the right, list the values of $d$ and $i$ at the end of every iteration through the do-while loop.

Problem 3 (assessment: self_______ final_______)

Algorithm: findFirstMissing
Input: $A$ and $B$, both sorted arrays of $n$ ints
Output: $j$, the least index such that $B[j]$ is not an element of $A$, or 'NOT FOUND' if no such element of $B$ exists
j = -1, k = -1
while k ≠ NOTFOUND and j < n-1 do
  j = j + 1
  k = search(A,0,n-1,B[j]) ← we assume "search" is an algorithm for the search problem, we
if k = NOTFOUND              could equally well use linearSearch, binarySearch or gallopSearch.
  return j
else                         
  return NOTFOUND
I recommend tracing through this algorithm on example input. For instance, with n=8 and A and B given below you should return 5.
A:
B:
Your Job: give a loop invariant for the while loop that would allow you to prove that this algorithm is correct. (No proof needed, just the condition.)