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

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:
isPermV1(A,n)
i = 0
while i < n do

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

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

i = i + 1

return FALSE
else
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$ ________