$1.$ Apply Kruskal's algorithm to find the minimum spanning tree. Use makeset $($ x $),$ find$($ x $),$ and union $($ x$,$y $)$ to determine if there are cycles. Using the forest representation of subsets taught in class, show the tree after all edges have been processed $($do not use path compression$).$ When processing edges, make sure lower letters appear first $($i$.$e$.$ use AB$,$ not BA$).$ When drawing the tree, put lower letters in left subtrees so that all the vertices in a level are sorted alphabetically from left to right.

Edges in MST:

Weight of MST:

Final tree resulting from union$-$find algorithm:

$2.$ Use Dijkstra's algorithm to find the shortest path between nodes A and F$.($Start at A$,$ end at F; if two neighbors are at the same distance, pick first the neighbor with the lowest letter in alphabetical order$)$

Path:

Distance:

$3.$ a$.$ Construct a Huffman tree for the following data:

b$.$ Encode ABACABAD using the tree you generated for $($a$).$

c$.$ Decode $100010111001010$ using the tree you generated for $($a$).$

d$.$ What compression gain $($percent of improvement$)$ do we get by using Huffman encoding instead of a fixed$-$length encoding scheme $($assume the fixed$-$length scheme would require $3$ bits for each character$)?$