6. \(\quad \begin{array} { l l l l l l l l } 25 & 22 & 30 & 18 & 29 & 21 & 27 & 21 \end{array}\)
The list of numbers above is to be sorted into descending order.
- Perform the first pass of a bubble sort, giving the state of the list after each exchange.
- Perform further passes, giving the state of the list after each pass, until the algorithm terminates.
(5)
The numbers represent the lengths, in cm, of pieces to be cut from rods of length 50 cm .
- Show the result of applying the first fit decreasing bin packing algorithm to this situation.
- Determine whether your solution to (b) (i) has used the minimum number of 50 cm rods.
(4)
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{01b167aa-2a77-4487-882c-20b1b74ecc90-7_714_1807_353_138}
\end{figure}
Figure 4 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow from sources \(A\) and \(B\) to sinks \(I , J\) and \(K\).
\section*{Take this as the initial flow pattern.}
- On Diagram 1 in the answer booklet, add a supersource \(S\) and a supersink \(W\) to obtain a capacitated network with a single source and single sink. State the minimum capacities of the arcs you have added.
(3) - Use the given initial flow and the labelling procedure on Diagram 2 to find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
- Verify that your flow is maximal.
- Show your maximum flow pattern on Diagram 3.