ALGORITHM HAS TO BE WRITTEN IN JAVA!! Bob has a set, A, of n nuts and a set B of
ID: 3851781 • Letter: A
Question
ALGORITHM HAS TO BE WRITTEN IN JAVA!!
Bob has a set, A, of n nuts and a set B of n bolts, such that each nut has a unique matching bolt. Unfortunately, the nuts in A all look the same, and the bolts in B all look the same as well. The only comparison that Bob can make is to take a nut-bolt pair (a,b), such that a A and b B, and test if the threads of a are larger, smaller, or a perfect match with the threads of b.But the carpenter cannot compare two nuts or two bolts directly. Here are the requirements
1. Your algorithm must be no worse than O(nlogn). Implement this as a function sortNutsNBolts.
2. Create a test program NutsNBolts.java that takes two commandline arguments for filenames.
for ex NutsNBolts nuts.txt bolts.txt
The files nuts.txt and bolts.txt each contain n integers for the nuts and bolts respectively. Your program should read these files and call the function.
3. Describe your algorithm in README. Describe a cost model and recurrence relation for the algorithm. Use Master Theorem and show that the upper bound of your approach on O(nlogn).
Explanation / Answer
1)
Algorithm:
Suppose that there are n nuts and bolts. A simple modification of Quicksort shows that there are randomized algorithms whose expected number of comparisons (and running time) are O(n log n): pick a random bolt, compare it to all the nuts, find its matching nut and compare it to all the bolts, thus splitting the problem into two problems, one consisting of the nuts and bolts smaller than the matched pair and one consisting of the larger ones. Repeating in this manner yields an algorithm whose expected running time can be analyzed by imitating the known analysis for Quicksort (see, e.g., the book by Coreman, Leiserson and Rivest, Algorithms, MIT Press, 1990.) showing that it is O(n log n).
2)
java code
public class NutsAndBoltsMatch
{
//Driver method
public static void main(String[] args)
{
// Method based on quick sort which matches nuts and bolts
char[] nuts = nuts.tochararray();
char[] bolts = bolts.tochararray();
sortNutsNBolts(nuts, bolts, 0, 5);
System.out.println("Matched nuts and bolts are : ");
printArray(nuts);
printArray(bolts);
}
// Method to print the array
private static void printArray(char[] arr) {
for (char ch : arr){
System.out.print(ch + " ");
}
System.out.print(" ");
}
// Method which works just like quick sort
private static void sortNutsNBolts(string nuts, string bolts, int low,
int high)
{
if (low < high)
{
// Choose last character of bolts array for nuts partition.
int pivot = partition(char[] nuts, char[] bolts, int low,
int high)
// Now using the partition of nuts choose that for bolts
// partition.
partition(bolts, low, high, nuts[pivot]);
// Recur for [low...pivot-1] & [pivot+1...high] for nuts and
// bolts array.
matchPairs(nuts, bolts, low, pivot-1);
matchPairs(nuts, bolts, pivot+1, high);
}
}
// Similar to standard partition method. Here we pass the pivot element
// too instead of choosing it inside the method.
private static int partition(char[] arr, int low, int high, char pivot)
{
int i = low;
char temp1, temp2;
for (int j = low; j < high; j++)
{
if (arr[j] < pivot){
temp1 = arr[i];
arr[i] = arr[j];
arr[j] = temp1;
i++;
} else if(arr[j] == pivot){
temp1 = arr[j];
arr[j] = arr[high];
arr[high] = temp1;
j--;
}
}
temp2 = arr[i];
arr[i] = arr[high];
arr[high] = temp2;
// Return the partition index of an array based on the pivot
// element of other array.
return i;
}
}
3)complexity O(NLOGN) DUE TO QUICK SORT PARTIONiNG
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.