$2$

$1$

$.$

$$Find the minimum spanning tree using the less efficient Simple algorithm. Be careful not to introduce a disconnected subgraph. Show the MST and the total weight of the MST

$.$

$($

$1$

$$pt

$)$

$2$

$2$

$.$

$$Find the minimum spanning tree using Prim's algorithm and list the edges in the order added to the MST

$.$

$$ Prim

$$

s algorithm can start at any vertex but without losing generality, you may start from D for easy comparison of your answers with others. Be careful not to form a cycle.

$($

$1$

$$pt

$)$

$2$

$3$

$.$

$$Find the minimum spanning tree using Kruskal's algorithm and list the edges in the order added to the MST

$.$

$$Kruskal

$$

s algorithm can start at any vertex but without losing generality, you may start from D for easy comparison of your answers with others. Be careful not to form a cycle.

$($

$1$

$$pt

$)$

$2$

$4$

$.$

$$With the assumptions made in the lecture, build a Huffman tree to encode the following string, $\backslash "$EBBEATTETETTWZZWALMETW$\backslash "$ using the frequency table built from the given string. Finally, show the encoded binary string of the original string.

$($

$2$

$$pts

$)$

$2$

$5$

$.$

$[$

Maxflow

$/$

Min cut: Ford

$-$

Fulkerson Algorithm

$]$

$$

$)$