Provide efficient algorithms for each of the problems below. You should describe
ID: 3670776 • Letter: P
Question
Provide efficient algorithms for each of the problems below. You should describe the main idea in a few sentences and provide pseudo code. Your pseudocode can use any previously taught algorithm as a function call. Just specify what the call does and its time complexity. Also, write down the worst case complexities for your algorithms. Assume all arrays below are integer arrays.
(A, 5 points) Given sorted arrays a and b, each of size n, do they have an element in common?
(B, 5 points) Given a sorted array a of size m and an unsorted array b of size n, do they have an element in common? Your solution must not sort the array b.
Explanation / Answer
Time Complexity: O(m*n) of given sorted arrays x and y:
public class commonelement {
public static void main(String[] args) {
int x[] = { 1, 2, 4, 5, 8 };
int y[] = { 2, 3, 5, 6 ,8};
common(x, y);
}
private static void common(int[] x, int[] y) {
int i = 0, j = 0;
while (i < x.length && j < y.length) {
if (x[i] > y[j]) {
j++;
} else if (y[j] > x[i]) {
i++;
} else {
System.out.println(x[i]);
i++;
j++;
}
}
}
}
Time complexity of this method is (m+n) by assumption of hash table search and insert operations take (1) time.
import java.util.HashSet;
public class commonelement {
public static void main(String[] args) {
Integer[ ] array1 = { 1,2,3,4,5,6,7,9};
Integer[ ] array2 = { 2,4,5,7,9 };
Integer[ ] common =commonelement.findCommon( array1, array2 );
System.out.print( "Common Elements Between Two Arrays: " );
for( Integer E : common ) {
System.out.print( E + " " );
}
}
public static Integer[ ] findCommon( Integer[ ] array1, Integer[ ] array2 ) {
Integer[ ] Hasharray;
Integer[ ] Searcharray;
if( array1.length < array2.length ) {
Hasharray = array1;
Searcharray = array2;
} else
{
Hasharray = array2;
Searcharray = array1;
}
HashSet<Integer> intersection = new HashSet<Integer>( );
HashSet<Integer> hArray = new HashSet<Integer>( );
for( Integer E : Hasharray ) {
hArray.add( E );
}
for( Integer E : Searcharray ) {
if( hArray.contains( E ) ) {
intersection.add( E );
}
}
return intersection.toArray( new Integer[ 0 ] );
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.