7.03h Best/worst/typical case: run-time analysis

4 Answer this question on the insert provided. The list of numbers below is to be sorted into decreasing order using shuttle sort. $$\begin{array} { l l l l l l l l l } 21 & 76 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$

1. How many passes through shuttle sort will be required to sort the list? After the first pass the list is as follows. $$\begin{array} { l l l l l l l l l } 76 & 21 & 65 & 13 & 88 & 62 & 67 & 28 & 34 \end{array}$$
2. State the number of comparisons and the number of swaps that were made in the first pass.
3. Write down the list after the second pass. State the number of comparisons and the number of swaps that were used in making the second pass.
4. Complete the table in the insert to show the results of the remaining passes, recording the number of comparisons and the number of swaps made in each pass. You may not need all the rows of boxes printed. When the original list is sorted into decreasing order using bubble sort there are 30 comparisons and 17 swaps.
5. Use your results from part (iv) to compare the efficiency of these two methods in this case. Katie makes and sells cookies. Each batch of plain cookies takes 8 minutes to prepare and then 12 minutes to bake. Each batch of chocolate chip cookies takes 12 minutes to prepare and then 12 minutes to bake. Each batch of fruit cookies takes 10 minutes to prepare and then 12 minutes to bake. Katie can only bake one batch at a time. She has the use of the kitchen, including the oven, for at most 1 hour.
   [0pt]
6. Each batch of cookies must be prepared before it is baked. By considering the maximum time available for baking the cookies, explain why Katie can make at most 4 batches of cookies. [2] Katie models the constraints as $$\begin{gathered} x + y + z \leqslant 4 \\ 4 x + 6 y + 5 z \leqslant 24 \\ x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{gathered}$$ where \(x\) is the number of batches of plain cookies, \(y\) is the number of batches of chocolate chip cookies and \(z\) is the number of batches of fruit cookies that Katie makes.
7. Each batch of cookies that Katie prepares must be baked within the hour available. By considering the maximum time available for preparing the cookies, show how the constraint \(4 x + 6 y + 5 z \leqslant 24\) was formed.
8. In addition to the constraints, what other restriction is there on the values of \(x , y\) and \(z\) ? Katie will make \(\pounds 5\) profit on each batch of plain cookies, \(\pounds 4\) on each batch of chocolate chip cookies and \(\pounds 3\) on each batch of fruit cookies that she sells. Katie wants to maximise her profit.
9. Write down an expression for the objective function to be maximised. State any assumption that you have made.
10. Represent Katie's problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm, choosing to pivot on an element from the \(x\)-column. Show how each row was obtained. Write down the number of batches of cookies of each type and the profit at this stage. After carrying out market research, Katie decides that she will not make fruit cookies. She also decides that she will make at least twice as many batches of chocolate chip cookies as plain cookies.
11. Represent the constraints for Katie's new problem graphically and calculate the coordinates of the vertices of the feasible region. By testing suitable integer-valued coordinates, find how many batches of plain cookies and how many batches of chocolate chip cookies Katie should make to maximise her profit. Show your working.

3 [Figure 3, printed on the insert, is provided for use in this question.]
The following network shows eight vertices. The number on each edge is the cost of travelling between the corresponding vertices. A negative number indicates a reduction by the amount shown. \includegraphics[max width=\textwidth, alt={}, center]{587bccdf-abd7-4a08-a76e-61374f322e2e-03_595_1234_1866_386}

1. Use dynamic programming to find the minimum cost of travelling from \(A\) to \(H\). You may use Figure 3 for your working.
2. State the minimum cost and the possible routes corresponding to this minimum cost.

5 [Figure 3, printed on the insert, is provided for use in this question.]
A maker of exclusive furniture is planning to build three cabinets \(A , B\) and \(C\) at the rate of one per month. The order in which they are built is a matter of choice, but the costs will vary because of the materials available and suppliers' costs. The expected costs, in pounds, are given in the table.

1. Use dynamic programming, working backwards from month 3, to determine the order of manufacture that minimises the total cost. You may wish to use Figure 3 for your working.
2. It is discovered that the figures given were actually the profits, not the costs, for each item. Modify your solution to find the order of manufacture that maximises the total profit. You may wish to use the final column of Figure 3 for your working.

5 [Figure 3, printed on the insert, is provided for use in this question.]
A small firm produces high quality cabinets.
It can produce up to 4 cabinets each month.
Whenever at least one cabinet is made during that month, the overhead costs for that month are \(\pounds 300\). It is possible to hold in stock a maximum of 2 cabinets during any month.
The cost of storage is \(\pounds 50\) per cabinet per month.
The orders for cabinets are shown in the table below. There is no stock at the beginning of January and the firm plans to clear all stock after completing the April orders.

1. Determine the total cost of storing 2 cabinets and producing 3 cabinets in a given month.
2. By completing the table of values on Figure 3, or otherwise, use dynamic programming, working backwards from April, to find the production schedule which minimises total costs.
3. Each cabinet is sold for \(\pounds 2000\) but there is an additional cost of \(\pounds 300\) for materials to make each cabinet and \(\pounds 2000\) per month in wages. Determine the total profit for the four-month period.

5 [Figure 2, printed on the insert, is provided for use in this question.]
A company has a number of stores. The following network shows the possible actions and profits over the next five years. The number on each edge is the expected profit, in millions of pounds. A negative number indicates a loss due to investment in new stores. \includegraphics[max width=\textwidth, alt={}, center]{1bf0d8b7-9f91-437a-bc18-3bfe5ca12223-06_1006_1583_591_223}

1. Working backwards from \(\boldsymbol { T }\), use dynamic programming to maximise the expected profits over the five years. You may wish to complete the table on Figure 2 as your solution.
2. State the maximum expected profit and the sequence of vertices from \(S\) to \(T\) in order to achieve this.
   (2 marks)