This is java

(1) Setup:

Create new Eclipse Java Project, Lab8. Be sure to "use project folder as root for source and class files". Add the algs4.jar and stdlib.jar files as external libraries.

Download this file into your new Eclipse project: Lab8_files.tgz

In your terminal (bash), cd to your Lab8 eclipse project folder, and run the command

% tar xzf Lab8_files.tgz

This will place two java files and two folders into that directory

In Eclipse, refresh the project - the java files will appear (as will the folders).

(2) (80% of lab grade)

Think back to exam question 6 (slightly modified for simplicity):

Given two arrays of integers a[] and b[], design two algorithms to determine whether the two arrays contain precisely the same set of points (though possibly in a different order).

(2a) Design an algorithm for the problem whose running time is linearithmic in the worst case and uses at most constant extra space.

The solution proposed in class was to sort both arrays, then compare the sorted arrays. How can we sort in linearithmic guaranteed time and constant extra space? (discuss this in your README).

(2b) Design an algorithm for the problem whose running time is linear under reasonable assumptions and uses at most linear extra space.

The solution proposed in class was to place all elements from one array in a hash table, then test if all elements in the other are present. What assumption does this make about your hashing function? (README)

Implement these two solutions in the context of the CompareTwoArrays.java file I've provided. You'll need to fill in details for the functions compareWithHeap() and compareWithHash().

Test using pairs of arrays from the folder single_arrays/. In this folder, there are arrays of lengths ranging from 100 (e.g. 100A.txt) to 10 million (e.g. 10mA.txt) integers, with a trio of files for each length of array. The A and B variant should match, while C should not match A or B.

How effective are these the two methods you've implemented? (a) do they work, and (b) what are the run times of the approaches? What is the impact of the method of collision detection, and the size of the underlying array? Document these in your README.

(3) (extra credit)

Think back to exam question 7 (slightly modified for simplicity):

Given k sorted arrays containing N keys in total (notice: this is N total keys, not Nk total keys), design an algorithm that determine whether there is any key that appears more than once. Your algorithm should run in time at most proportional to N log k in the worst case, and use extra space at most proportional to k.

The solution discussed in class was to

create a Red-Black Tree, T, and place the first element from each array into T, then

repeatedly remove the minimum from T, noting the array it came from, and replace that entry with the next smallest entry from that array.

Somehow, you need to recognize when a duplicate is present. How to do this? (README)

Implement this solution in the context of the CheckArraysForDuplicates.java file I've provided. You'll need to understand how to put/get entries in the RB tree, and take care with duplicate detection.

Test with the files found in the k_arrays/ directory, which contains inputs with varying numbers of total entries (n) and total arrays (k). How does your solution's run time scale with n and k