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_______)

The isPermuation problem is this: Given an array A of n integers, determine whether A represents a permutation, i.e. determine whether A contains exactly the numbers from 0 to n-1, each appearing exactly once, but allowed to appear in any order. Here is an algorithm to solve the problem:
bad = 0
i = 0
while i < n do

  if A[i] < 0 or A[i] >= n    \__ increment bad if A[i] is out of range
    bad = bad + 1             /

  j = 0                       \
  while j < i do               |__ increment bad if A[i] has a duplicate earlier in A
    if A[j] = A[i]             |
      bad = bad + 1            |
    j = j + 1                 /

  i = i + 1

if bad > 0
   return FALSE
   return TRUE
Give an analysis of the worst-case running time of this algorithm.

Problem 1 (assessment: self_______ final_______)

Use the idea of time-space tradeoff to write down an improved version of this algorithm. Hint: declare an array X of n zeros prior to entering the outer while and try to think about how having that on hand allows you to speed up the algorithm.

Problem 2 (assessment: self_______ final_______)

Consider the onWormSPD(X,Y,n,x,y) algorithm from homework 5 problem 2.
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
It's clear that $T_w(n) \in O(n)$ and $T_w(n) \in \Omega(1)$. But it's actually hard to say much else about it. So, consider the following input family shown on the right.
  1. For $n = 16$, we get this picture:
    (x,y) worm body
    Put an X in each cell (index i) you actually compute distance d for.
  2. Analyze and give a lower bound on $T_I(n)$, the running time of onWormSPD for this family of inputs.
  3. What have we learned about $T_w(n)$ for onWormSPD from the previous question? $T_w(n) \in$ ________