Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
Perproblem 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 n1, each appearing exactly once, but allowed
to appear in any order. Here is an algorithm to solve the problem:
isPermV1(A,n)
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
else
return TRUE
Give an analysis of the worstcase running time of this 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,...,n1}, 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.
 For $n = 16$, we get this picture:
Put an X in each cell (index i) you actually compute
distance d for.

Analyze and give a lower bound on $T_I(n)$, the running time
of onWormSPD for this family of inputs.

What have we learned about $T_w(n)$ for onWormSPD from the
previous question? $T_w(n)
\in$ ________