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