Difference between two sets in JAVA. Given two arrays a[] and b[], each containi

Question

Difference between two sets in JAVA.

Given two arrays a[] and b[], each containing distinct values, design a subquadratic algorithm to count the number of values that are contained either in array a[] and array b[] but not both. Create test program DiffSets.java that takes three commandline arguments <size_of_a> <size_of_b> <number of iterations>

For ex: java DiffSets 10 20 100

The program must do the following

1. Create arrays a and b of the mentioned size and fill it with uniformly random numbers between (0-max(size_a, size_b)) <- in this case this would be 0-20

2. Find the numbers that are only present in a or b but not both.

3. Repeat 1 and 2 for n iterations

Run your program for various sizes of a and b (run each 100 times). Observe the running time of your algorithm (either using java's in-built timers or by using the system time). Tabulate your results in the README file.

(Writeup only): How would you extend this algorithm to find unique values in k lists. Can you still maintain the same running time?

Explanation / Answer

import java.util.ArrayList;

import java.util.List;

import scala.actors.threadpool.Arrays; /** * Intersection of two sets. * Given two arrays a[] and b[], each containing N distinct 2D points in the plane,

public class ElementarySorts { class Point implements Comparable<Point>{ private int x; private int y; public Point(int x, int y) { this.x = x; this.y = y; } @Override public int compareTo(Point that) { if (that.x > this.x) return -1; if (that.x < this.x) return 1; if (that.y > this.y) return -1; if (that.y < this.y) return 1; return 0; } public int countIntersection(Point[] a, Point[] b) { Shell.sort(a); Shell.sort(b); int i = 0; int j = 0; int count = 0; while (i < a.length && j < b.length) { if (a[i].compareTo(b[j]) == 0) { count++; i++; j++; } else if (a[i].compareTo(b[j]) < 0) i++; else j++; } return count; } } public boolean isPerm(Integer[] a, Integer[] b) { if (a.length != b.length) return false; Shell.sort(a); Shell.sort(b); for (int i = 0; i < a.length; i++) { if (a[i] != b[i]) return false; } return true; } /* Question 3 Dutch national flag. Given an array of N buckets, each containing a red, white, or blue pebble, sort them by color. The allowed operations are: swap(i,j): swap the pebble in bucket i with the pebble in bucket j. color(i): color of pebble in bucket i. The performance requirements are as follows: At most N calls to color(). At most N calls to swap(). Constant extra space. */ enum Pebble { Red, White, Blue } class Buckets { private Pebble[] pebbles; private Pebble color(int i) { return pebbles[i]; } private int compare(Pebble p) { Pebble white = Pebble.White; return p.ordinal() - white.ordinal(); } private void swap(int i, int j) { Pebble tmp = pebbles[i]; pebbles[i] = pebbles[j]; pebbles[j] = tmp; } public void sort() { assert pebbles.length > 0; int r = 0; int runner = 0; int b = pebbles.length - 1; while (runner <= b) { Pebble color = color(runner); int cmp = compare(color); if (cmp < 0) { swap(runner++, r++); } else if (cmp > 0) { swap(runner, b--); } else { runner++; } } } } }

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.