1.
$$\begin{array} { l l l l l l l l l }
4.2 & 1.8 & 3.1 & 1.3 & 4.0 & 4.1 & 3.7 & 2.3 & 2.7
\end{array}$$
- Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 7.8
- Determine whether the number of bins used in (a) is optimal. Give a reason for your answer.
- The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-02_586_1356_906_358}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure} - Use Kruskal's algorithm to find a minimum spanning tree for the network in Figure 1. You must show clearly the order in which you consider the arcs. For each arc, state whether or not you are including it in your minimum spanning tree.
A new spanning tree is required which includes the arcs AB and DE , and which has the lowest possible total weight.
- Explain why Prim's algorithm could not be used to complete the tree.