Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.

We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.

Question 2

Question 2.1

On the first call to union, we'd find what Sets Cheetah and Wolf are in (2 and 3, respectively), and then link up the sets by changing the pointers of the root nodes based on weight.

Since Set 2 has more weight than Set 3, we set the root node of Set 3 (Wolf) to point to the root node of Set 2, (Tiger), ending up with something like this

On the second call to union, we find what Sets Wolf and Lion are in. Since they are both in Set 2, we don't do anything!

Question 2.2 and Question 2.3

On the first call to union("Cheetah", "Wolf"), we end up with the same set as Question 2.1

Now calling union("Wolf", "Crow"), we first find which sets each are in. Crow is in Set 1, and Wolf is in Set 2.

Since Set 1 and Set 2 are tied in terms of weight, we can break the tie arbitrarily, and end up with one of the following.

Question 3

Question 3.1 and Question 3.2

Since this graph has 6 vertices and 15 edges, it would make more sense to use Prim's algorithm, since Prim's works by going vertex to vertex, as opposed to Kruskal's, which goes edge-by-edge and in which we would have to do the unnecessary task of sorting all the edges first.

In general, when you have a lot of edges (in a dense graph), you want to use Prim's. When you have a graph with relatively few edges (a sparse graph) or if you have a graph with pre-sorted edges, Kruskal's is the way to go.

Question 4