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_______)
Let's revisit our good friend onWormSPD from last homework.
This time, though, let's assume we have an array of Coord
objects, each with an x and y field. So, if $A$ is an array of
$n$ Coord's representing a worm, then A[i].x and A[i].y would
give the coordinates of the $i$th cell of the worm's body.
Now consider the following problem: Given two worms of the
same length, determine whether they overlap, i.e. whether
there is a coordinate at which they both have cells.
Analyze the worst case running time $T_w(n)$ of the following
algorithm for this problem, using what we proved in previous
homeworks about the running time of onWormSPD. Give a clear
and complete explanation for your analysis.
wormIntersection(A,B,n)
Input : A an B are arrays of n Coord's, representing two worm bodies
Output: true if A and B have a common Coord, false otherwise
i = 0, found = false
while i < n and found == false
found = onWormSPD(B,n,A[i])
i = i + 1
return found
Problem 1 (assessment: self_______ final_______)
We can always compare two Coord's lexicograpically.
I.e. compare by xcoordinates, breaking ties by ycoordinates.
With an "<" defined for Coords, we can now use data
structures like balanced binary trees. Give a new algorithm,
wormIntersection2.0, by applying the timespace tradeoff idea
(and balanced binary trees) for this problem, and provide an
analysis of the algorithm's worstcase running time.
Problem 2 (assessment: self_______ final_______)
SelectionSort is one of the classic sorting algorithms.
Show the contents of array A as requested below:
selectionSort(A,n)
input: A an array of n objects for which "<" is defined
n the size of A
Output: side effect of leaving A in sorted order according to "<"
for i from 0 to n2 do
m = i
for j from i+1 to n1 do
if A[j] < A[m]
m = j
swap(A[i],A[m])
before i=0 iteration A: 

before i=1 iteration A: 

before i=2 iteration A: 

before i=3 iteration A: 

before i=4 iteration A: 

Problem 3 (assessment: self_______ final_______)
InsertionSort is one of the classic sorting algorithms.
Show the contents of array A as requested below:
insertionSort(A,n)
input: A an array of n objects for which "<" is defined
n the size of A
Output: side effect of leaving A in sorted order according to "<"
for i from 0 to n2 do
j = i + 1
while j > 0 and A[j] < A[j1] do
swap(A[j],A[j1])
j = j  1
before i=0 iteration A: 

before i=1 iteration A: 

before i=2 iteration A: 

before i=3 iteration A: 

before i=4 iteration A: 
