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

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 x-coordinates, breaking ties by y-coordinates. With an "<" defined for Coords, we can now use data structures like balanced binary trees. Give a new algorithm, wormIntersection2.0, by applying the time-space tradeoff idea (and balanced binary trees) for this problem, and provide an analysis of the algorithm's worst-case 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 n-2 do
  m = i
  for j from i+1 to n-1 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 n-2 do
  j = i + 1
  while j > 0 and A[j] < A[j-1] do
    swap(A[j],A[j-1])
    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: