LAB 8

Sample Solutions for Lab 8

Matching Pairs, Straightforward

boolean matchingPairs(int[] A, int s)
   for i := 1 to A.length do
      for j := i+1 to A.length do
         if A[i] + A[j] = s
            then return true
   return false

Matching Pairs, Optimized

boolean matchingPairs(int[] A, int s)
   sort(A)
   i := 1; j := A.length;
   while i < j and A[i] + A[j] != s do
      if A[i] + A[j] > s
         then j--
     else i++
   if i >= j 
      then return false
      else return true

Matching Pairs, Optimized version 2

boolean matchingPairs(int[] A, int s)
   sort(A)
   for i := 1 to A.length do
      if binarySearch(A,s-A[i]) != -1
         then return true
   return false


boolean matchingPairs(int[] A, int s)
   sort(A)
   i := 1
   while i <= A.length and binarySearch(A,s-A[i]) = -1 do
      i++
   if i <= A.length
      then return true
      else return false


boolean matchingPairs(int[] A, int s)
   sort(A)
   i := 1
   found := false
   while i <= A.length && not found do
      if binarySearch(A,s-A[i]) > -1 
         then found := true
         else i++
   return found

Number of Values in Sorted Array

int numberOfValues(int[] C)

   currentValue := C[1]
   numberOfValues := 1

   for i:=2 to C.length do
      if C[i] != currentValue
         then numberOfValues++
              currentValue := C[i]
   return numberOfValues

Duplicate Elimination, Straightforward

Idea:
- Create one output array, say C,
that has the same length as A
- for each number in A,
check whether it has already been copied into C
if not, copy it
- create a new array B, with a length that is equal to the number of
different values found
- then copy the values found from C to B

Pseudocode:

  int[] C = new int[A.length]

  valuesFound := 0

  for i := 1 to A.length do
     j := 1
     while j <= valuesFound and  A[i] != C[j] do
         j++
     if j > valuesFound then
         valuesFound++         
         C[valuesFound] := A[i]

  int[] B := new int[valuesFound]
  for i := 1 to valuesFound do
       B[i] := C[i]

  return B

Duplicate Elimination, Efficient

Idea:
- Copy A into a new array, say C, and sort C;
- Create one output array, say B,
with length as the number of different values in A;
- Scan linearly C and each time we found a different
value we add it to B.

int[] eliminateDuplicatesSorted(int[] A)

   C := copy(A);
   sort(C);
   n := numberOfValues(C)
   int[] B = new int[n]

   currentIndex := 1
   currentVal := C[1]

   B[currentIndex] := currentValue

   for i:=2 to C.length do
      if C[i] != currentValue then
              currentVal := C[i]
              currentIndex++ 
              B[currentIndex] := currentVal
   return B

Duplicate Elimination Respecting Order

Idea:
- Start with an ordered version that is free of duplicates
- Data structures:
> sorted version of array
> array of boolean that says which number has been output already

  int[] ValuesSorted := eliminateDuplicatesSorted(A)
  n := ValuesSorted.length

  boolean[] ValueFound := new boolean[n]
  setToFalse(ValueFound)

  int[] B := new int[n]
  currentIndex := 1

  for i:=1 to A.length do
      index := binarySearch(ValuesSorted,A[i])
      if ValueFound[index] = false then
           ValueFound[index] = true
           B[currentIndex] := A[i]
           currentIndex++

Exact Contiguous Sum

We are given an array of positive integers A and a number s.
The question is whether there exists a segment A[i..j] of A
such that the sum of the numbers of this segment equals s.

Straightforward approach

  for i := 1 to A.length do
     for j := i to A.length do
        sum := 0
        for k := i to j do
           sum += A[k]
        if sum = s
           then return true
  return false

Sophisticated approach

  i := 1
  j := 1
  sum := A[1]

  while (sum < s && j < A.length)
        or (sum > s && (i < j || i < A.length)) do
     if sum < s
        then j++
             sum += A[j] 
     else if (i < j) 
        then sum -= A[i]
             i++
        else i++
             j++
         sum := A[i]
  if sum != s
     then return false
     else return true