CSCI 3333
Data Structures
Summer 2008
Suggested Solution to Homework #4

(1) C3-2

Algorithm FindRepeat(a,n)
Input: an int array a[0..n-1] that stores the integers 1 to n-1 inclusively, with exactly one integer repeating. n>=2.
Output: the repeated integer

return sum(a)-n(n-1)/2.

(2) C3-3

Algorithm FindRepeat(a,n)
Input: an int array a[0..n-5] that stores the integers 1 to n-1 inclusively, with exactly five integers repeating. n>=10.
Output: result: an integer array[0..4] storing the five repeated integers

int array b = sort(a);
int array result[0..4] = [];
i = 0;
while (i < n-7)
   if b[i] == b[i+1]
      push b[i] into result;
      i = i + 2;
   else
      i++;
   end if;
end while;
return result;

(3) C3-10

Algorithm ReverseList(L)
Input: a linked list L
Output: no
Side Effect: the linked list is reversed.

if L is empty return without any action.
prevNode = null;
currentNode = L.head;
nextNode = currNode->next;
while (nextNode refers to an non-empty node)
   currNode->next = prevNode
   prevNode = currNode;
   currNode = nextNode;
   nextNode = currNode->next;
}
L.head = currNode;

(4) R-4.7: 20

(5) R-4.15: O(n)

(6) R-4.17: O(n2)

(7) R-4.19: O(n3)

(8) C-4.5

LHS = (2n3+3n2+n)/6 = O(n3)