Quiz 4 -- Princeton Algorithm

Intersection of two sets. Given two arrays 𝚊[] and 𝚋[], each containing n distinct 2D points in the plane, design a subquadratic algorithm to count the number of points that are contained both in array 𝚊[] and array 𝚋[].

Hint: shellsort (or any other subquadratic sort).

something like mergesort, sort a[] and b[] separately by x coordinate, and then by y coordinate with stable sorting and then iterate a[] with i, b[] with j

while ( i < a.length && j < b.length) {

if (a[i].y < b[j].y) i++;

else if (a[i].y > b[j].y) j++;

else if (a[i].x < b[j].x) i++;

else if (a[i].x > b[j].x) j++;

else {

    count++;

    i++;

    j++;

}

}

Permutation. Given two integer arrays of size n, design a subquadratic algorithm to determine whether one is a permutation of the other. That is, do they contain exactly the same entries but, possibly, in a different order.

Hint: sort both arrays.

sort them separately to see whether they are equal.

use hash map to counter the frequency of each number in first array and then check whether the second one has the same frequency of each number. 

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.

three way partition