As with other homeworks, you may not need to pass all tests for a full score.
The assignment can be submitted in the usual fashion and is due at **11:59pm** on **Wednesday, November 27th**.

## Navigation

## A. Union-Find

Consider the contiguous set of integers $1$ to $V$. Each integer is part of some partition.
Initially, there are $V$ partitions, with each partition containing a single integer.
We want to support the operations of finding which partition any given
integer belongs to and merging two partitions into one ("union"). We identify
partitions by choosing one representative member for each.
Fill in the file `UnionFind.java`

to implement the `find`

and `union`

operations.
Do ** not** use any data structures from the Java library (the utilities
in the

`Arrays`

class are OK), and do **define any classes other than**

*not*`UnionFind`

. Just use arrays and primitive values.Tip: If you need to speed up your Union-Find operations, you can try:

- Implementing path compression
- Re-considering how you are currently deciding which sub-tree to pick as the root when unioning. (Should you pick the larger or smaller tree?)

## B. Minimum Spanning Trees

Consider an undirected graph whose vertices are numbered $1$ to $V$ and
whose edges are labeled with non-negative integer weights. Given such a graph,
we would like to find a minimal spanning tree in the form of an array of edges
from the graph that are included in the tree. To give you some exercise in
true data-structure hacking, for this problem we'll represent the graph using
only arrays and ints. Fill in the skeleton file `MST.java`

to use Kruskal's
Algorithm to create this tree.
Assume that we will be giving you *large* graphs to operate on.
As for part A, do ** not** use any data structures from the
Java library (the utilities in the

`Arrays`

class are OK).The class `MSTTest`

runs some JUnit tests on your MST algorithm. If a test case
fails, you can use the main program of `Utils.java`

to see exactly what graph was
fed to it, if desired.

The test cases will print out parameters for the main program that generate the
graph in the test case. Executing the following command (after replacing the
arguments with the printed out parameters) prints the corresponding test case
and the MST your program produces from it.

` java Utils V MINEDGES MAXWEIGHT RANDOM-SEED true`

(The arguments V through RANDOM-SEED tell `Utils.randomConnectedGraph`

what graph to generate). This is less helpful on really large test cases,
of course.