7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin

30312522318136101524

1. The list of ten numbers above is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. The ten numbers are to be packed into bins of size \(n\), where \(n\) is a positive integer.
   When the first-fit bin packing algorithm is applied to the original list of ten numbers, the following allocation is obtained.

   Bin 1:	30	12	2
   Bin 2:	5	23	10
   Bin 3:	18	15
   Bin 4:	36
   Bin 5:	24

2. Explain why the value of the integer \(n\) must be either 44 or 45
3. Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45
   

1. A gardener needs the following lengths of string. All lengths are in metres.
   0.4
   1.7
   1.3
   2.5
   2.1
   3.4
   4.3
   4.7
   5.1
   5.9
   6.1

She cuts the lengths from balls of string. Each ball contains 10 m of string.

1. Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear.
2. Use the first-fit bin packing algorithm to determine how the lengths could be cut from the balls of string.
   

4. The eleven distinct numbers listed below are to be packed into bins of size 40 $$\begin{array} { l l l l l l l l l l l } 15 & 22 & 3 & 9 & 23 & x & 5 & 4 & 18 & 20 & 13 \end{array}$$ It is known that \(x\)

• is an integer less than 40
• is the largest number in the list
  1. Explain why it is not possible to pack the numbers into 3 bins of size 40

Given that it is possible to pack the numbers into 4 bins of size 40

determine the range of values for \(x\)

Use the first-fit bin packing algorithm to determine how the numbers can be packed into bins of size 40

Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly. When the first-fit decreasing bin packing algorithm is applied to the list, neither the 15 nor the 13 is placed in the first bin.

Determine the value of \(x\). You must give reasons for your answer.

1. $$\begin{array} { l l l l l l l l l l l } 17 & 8 & 16 & 12 & 24 & 19 & 23 & 11 & 20 & 13 & 4 \end{array}$$ The eleven numbers listed above are to be packed into bins of size \(n\) where \(n\) is a positive integer. When the first-fit bin packing algorithm is applied to the eleven numbers, the bins are packed as shown below. Bin 1: 17812
Bin 2: 1624
Bin 3: 19114
Bin 4: 2313
Bin 5: 20

1. Explain why this packing means that the value of \(n\) must be 40 The original list of eleven numbers is to be sorted into descending order.
2. Use a quick sort to obtain the fully sorted list. You must make your pivots clear.
3. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 40

1. 11
17
10
14
8
13
6
4
15
7

1. Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
2. Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
3. Calculate a lower bound for the minimum number of bins required. You must show your working.

4
15
7

1. Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
2. Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
3. Calculate a lower bound for the minimum number of bins required. You must show your working.
   2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
   1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
   2. State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
   3. 1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
      2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
      3. State the new minimum cost of connecting the nine buildings.
         3. \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
         \end{figure} \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
         \end{figure} Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6. Figure 3 shows an initial matching.
   4. Define the term 'matching'.
      (2)
   5. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.
      (3) After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.
   6. Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
      (3)
      4. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390} \captionsetup{labelformat=empty} \caption{Figure 4
      [0pt] [The total weight of the network is 367 metres]}
      \end{figure} Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe. A robot will travel along each pipe to check that the pipe is in good repair.
      The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.
   7. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   8. Write down the length of a shortest inspection route. A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .
   9. Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.

17
10
14
8
13
6
4
15
7

1. Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
2. Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
3. Calculate a lower bound for the minimum number of bins required. You must show your working.
   2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
   1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
   2. State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
   3. 1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
      2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
      3. State the new minimum cost of connecting the nine buildings.
         3. \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
         \end{figure} \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
         \end{figure} Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6. Figure 3 shows an initial matching.
   4. Define the term 'matching'.
      (2)
   5. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.
      (3) After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.
   6. Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
      (3)
      4. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390} \captionsetup{labelformat=empty} \caption{Figure 4
      [0pt] [The total weight of the network is 367 metres]}
      \end{figure} Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe. A robot will travel along each pipe to check that the pipe is in good repair.
      The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.
   7. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   8. Write down the length of a shortest inspection route. A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .
   9. Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.
      5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-6_560_1134_251_470} \captionsetup{labelformat=empty} \caption{Figure 5}
      \end{figure} Figure 5 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road.
   10. Use Dijkstra's algorithm to find the shortest route from S to T . State your route and its length. The road represented by arc CE is now closed for repairs.
   11. Find two shortest routes from S to T that do not include arc CE . State the length of these routes.
       (3)
       6. A linear programming problem in \(x\) and \(y\) is described as follows. Minimise \(\quad C = 2 x + 5 y\) subject to $$\begin{aligned} x + y & \geqslant 500 \\ 5 x + 4 y & \geqslant 4000 \\ y & \leqslant 2 x \\ y & \geqslant x - 250 \\ x , y & \geqslant 0 \end{aligned}$$
   12. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
   13. Use point testing to determine the exact coordinates of the optimal point, P. You must show your working. The first constraint is changed to \(x + y \geqslant k\) for some value of \(k\).
   14. Determine the greatest value of \(k\) for which P is still the optimal point.
       7. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-8_582_1226_248_422} \captionsetup{labelformat=empty} \caption{Figure 6}
       \end{figure} A project is modelled by the activity network shown in Figure 6. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
   15. Complete Diagram 1 in the answer book to show the early event times and late event times.
   16. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
   17. Use your cascade chart to determine a lower bound for the number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. The project is to be completed in the minimum time using as few workers as possible.
   18. Schedule the activities, using Grid 2 in the answer book.
       8. A charity produces mixed packs of posters and flyers to send out to sponsors. Pack A contains 40 posters and 20 flyers.
       Pack B contains 30 posters and 50 flyers.
       The charity must send out at least 15000 flyers.
       The charity wants between \(40 \%\) and \(60 \%\) of the total packs produced to be Pack As.
       Posters cost 15p each and flyers cost 3p each.
       The charity wishes to minimise its costs.
       Let \(x\) represent the number of Pack As produced, and \(y\) represent the number of Pack Bs produced.
       Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients.
       You should not attempt to solve the problem.
       (Total 6 marks)

10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

1. Calculate a lower bound for the number of rolls needed.
   (2)
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.

12
10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

1. Calculate a lower bound for the number of rolls needed.
   (2)
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.

2.
32
45
17
23
38
28
16
9
12
10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

1. Calculate a lower bound for the number of rolls needed.
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.

17
23
38
28
16
9
12
10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

1. Calculate a lower bound for the number of rolls needed.
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.
   3. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-3_755_624_283_283} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-3_750_620_285_1146} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Figure 1 shows the possible allocations of six workers, Charlotte (C), Eleanor (E), Harry (H), Matt (M), Rachel (R) and Simon (S) to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.
   1. List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
   2. Explain why it is not possible to find a complete matching. Simon (S) now has task 3 added to his possible allocation.
   3. Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating path you use and your complete matching.
      (3)
      4. Miri
      Jessie
      Edward
      Katie
      Hegg
      Beth
      Louis
      Philip
      Natsuko
      Dylan
   4. Use the quick sort algorithm to sort the above list into alphabetical order.
      (5)
   5. Use the binary search algorithm to locate the name Louis.
      5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-5_940_1419_262_322} \captionsetup{labelformat=empty} \caption{Figure 3}
      \end{figure} [The total weight of the network is 625 m ]
      Figure 3 models a network of paths in a park. The number on each arc represents the length, in m , of that path.
      Rob needs to travel along each path to inspect the surface. He wants to minimise the length of his route.
   6. Use the route inspection algorithm to find the length of his route. State the arcs that should be repeated. You should make your method and working clear.
      (6) The surface on each path is to be renewed. A machine will be hired to do this task and driven along each path.
      The machine will be delivered to point G and will start from there, but it may be collected from any point once the task is complete.
   7. Given that each path must be traversed at least once, determine the finishing point so that the length of the route is minimised. Give a reason for your answer and state the length of your route.
      (3)
      6. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-6_899_1493_262_285} \captionsetup{labelformat=empty} \caption{Figure 4}
      \end{figure} Figure 4 represents a network of roads. The number on each arc gives the length, in km , of that road.
   8. Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
      (6)
   9. State the shortest distance from A to G .
      (1)
      7. Rose makes hanging baskets which she sells at her local market. She makes two types, large and small. Rose makes \(x\) large baskets and \(y\) small baskets. Each large basket costs \(\pounds 7\) to make and each small basket costs \(\pounds 5\) to make. Rose has \(\pounds 350\) she can spend on making the baskets.
   10. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint.
       (2) Two further constraints are $$\begin{aligned} & y \leqslant 20 \text { and } \\ & y \leqslant 4 x \end{aligned}$$
   11. Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
   12. On the grid provided, show these three constraints and \(x \geqslant 0 , y \geqslant 0\). Hence label the feasible region, R. Rose makes a profit of \(\pounds 2\) on each large basket and \(\pounds 3\) on each small basket. Rose wishes to maximise her profit, £P.
   13. Write down the objective function.
   14. Use your graph to determine the optimal numbers of large and small baskets Rose should make, and state the optimal profit.
       8. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-8_809_1541_283_262} \captionsetup{labelformat=empty} \caption{Figure 5}
       \end{figure} A construction project is modelled by the activity network shown in Figure 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
   15. Complete Diagram 2 in the answer book, showing the early and late event times.
   16. State the critical activities.
   17. Find the total float for activities M and H . You must make the numbers you use in your calculations clear.
   18. On the grid provided, draw a cascade (Gantt) chart for this project. An inspector visits the project at 1 pm on days 16 and 31 to check the progress of the work.
   19. Given that the project is on schedule, which activities must be happening on each of these days?

3. Five workers, A, B, C, D and E, are to be assigned to five tasks, 1, 2, 3, 4 and 5 . Each worker must be assigned to only one task and each task must be done by only one worker. The cost, in pounds, of assigning each worker to each task is shown in the table below. The cost of assigning worker D to task 4 is \(\pounds x\), where \(x > 38\) The total cost is to be minimised.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.
   (8)
2. Find the minimum total cost.
   (1) Workers A and D decide that they do not like the task they have been allocated and are allowed to swap tasks with each other. The other three allocations are unchanged. The cost now of allocating the five workers to the five tasks is now \(\pounds 5\) more than the minimum cost found in (b).
3. Calculate the value of \(x\). You must show your working.
   (2)

3. Five friends have rented a house that has five bedrooms. They each require their own bedroom. The table below shows how each friend rated the five bedrooms, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , where 0 is low and 10 is high. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total of all the ratings. You must make your method clear and show the table after each stage.
(Total 8 marks)

2 In an investigation into a burglary, Agatha has five suspects who were all known to have been near the scene of the crime, each at a different time of the day. She collects evidence from witnesses and draws up a table showing the number of witnesses claiming sight of each suspect near the scene of the crime at each possible time. Suspect \begin{table}[h] \end{table}

1. Use the Hungarian algorithm on a suitably modified table, reducing rows first, to find the matchings for which the total number of claimed sightings is maximised. Show your working clearly. Write down the resulting matchings between the suspects and the times. Further enquiries show that the burglary took place at 5 pm , and that Dr Silverbirch was not the burglar.
2. Who should Agatha suspect?

2. Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances. Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm.

1. Four sales representatives ( \(R _ { 1 } , R _ { 2 } , R _ { 3 }\) and \(R _ { 4 }\) ) are to be sent to four areas ( \(A _ { 1 } , A _ { 2 } , A _ { 3 }\) and \(A _ { 4 }\) ) such that each representative visits one area. The estimated profit, in tens of pounds, that each representative will make in each area is shown in the table below.

Use the Hungarian method to obtain an allocation which will maximise the total profit made from the visits. Show the state of the table after each stage in the algorithm.

1. Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:

• strip the wallpaper,
• paint the woodwork and ceiling,
• hang the new wallpaper,
• replace the fittings and tidy up.

The table below shows the time, in hours, that each of the friends is likely to take to complete each job. As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.

1. Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
2. Hence find the minimum time in which the friends can redecorate the lounge.
   

1. \(3.7 \quad 2.5\) \(5.4 \quad 1.9\) 2.7
3.2
3.1
2.7
4.2
2.0

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 8.5 The first-fit bin packing algorithm is to be used to pack \(n\) numbers into bins. The number of comparisons is used to measure the order of the first-fit bin packing algorithm.
2. By considering the worst case, determine the order of the first-fit bin packing algorithm in terms of \(n\). You must make your method and working clear.

2 Seven items need to be packed into bins. Each bin has capacity 30 kg . The sizes of the items, in kg, in the order that they are received, are as follows.
12
23
15
18
8
7
5

1. Find the packing that results using each of these algorithms.
   1. The next-fit method
   2. The first-fit method
   3. The first-fit decreasing method
2. A student claims that all three methods from part (a) can be used for both 'online' and 'offline' lists. Explain why the student is wrong. The bins of capacity 30 kg are replaced with bins of capacity \(M \mathrm {~kg}\), where \(M\) is an integer.
   The item of size 23 kg can be split into two items, of sizes \(x \mathrm {~kg}\) and \(( 23 - x ) \mathrm { kg }\), where \(x\) may be any integer value you choose from 1 to 11. No other item can be split.
3. Determine the smallest value of \(M\) for which four bins are needed to pack these eight items. Explain your reasoning carefully.

5

1. Find the packing that results using each of these algorithms.
   1. The next-fit method
   2. The first-fit method
   3. The first-fit decreasing method
2. A student claims that all three methods from part (a) can be used for both 'online' and 'offline' lists. Explain why the student is wrong. The bins of capacity 30 kg are replaced with bins of capacity \(M \mathrm {~kg}\), where \(M\) is an integer.
   The item of size 23 kg can be split into two items, of sizes \(x \mathrm {~kg}\) and \(( 23 - x ) \mathrm { kg }\), where \(x\) may be any integer value you choose from 1 to 11. No other item can be split.
3. Determine the smallest value of \(M\) for which four bins are needed to pack these eight items. Explain your reasoning carefully. 3 The diagram shows a simplified map of the main streets in a small town. \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_531_1127_301_246} Some of the junctions have traffic lights, these junctions are labelled A to F .
   There are no traffic lights at junctions X and Y .
   The numbers show distances, in km, between junctions. Alex needs to check that the traffic lights at junctions A to F are working correctly.
   1. Find a route from A to E that has length 2.8 km . Alex has started to construct a table of shortest distances between junctions A to F. \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_543_1173_1420_246} For example, the shortest route from C to B has length 1.7 km , the shortest route from C to D has length 2.5 km and the shortest route from C to E has length 1.8 km .
   2. Complete the copy of the table in the Printed Answer Booklet.
   3. Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F .
      Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km .
   4. Write down the junctions in the order that Beth visited them. Do not draw on your answer from part (c). 4 Li and Mia play a game in which they simultaneously play one of the strategies \(\mathrm { X } , \mathrm { Y }\) and Z . The tables show the points won by each player for each combination of strategies.
      A negative entry means that the player loses that number of points.

      Mia X Y Z \multirow{3}{*}{Li} X 5 - 6 0 \cline { 2 - 5 } Y - 2 3 4 \cline { 2 - 5 } Z - 1 4 8 \cline { 2 - 5 } Mia X Y Z \multirow{2}{*}{Li} X 4 \cline { 2 - 5 } Y 11 5 \cline { 2 - 5 } Z 10 5 1 \cline { 2 - 5 } The game can be converted into a zero-sum game, this means that the total number of points won by Li and Mia is the same for each combination of strategies. Complete the table in the Printed Answer Booklet to show the points won by Mia. Convert the game into a zero-sum game, giving the pay-offs for Li . Use dominance to reduce the pay-off matrix for the game to a \(2 \times 2\) table. You do not need to explain the dominance. Mia knows that Li will choose his play-safe strategy. Determine which strategy Mia should choose to maximise her points. 5 A linear programming problem is formulated as below. Maximise \(\quad \mathrm { P } = 4 \mathrm { x } - \mathrm { y }\) subject to \(2 x + 3 y \geqslant 12\) \(x + y \leqslant 10\) \(5 x + 2 y \leqslant 30\) \(x \geqslant 0 , y \geqslant 0\) Identify the feasible region by representing the constraints graphically and shading the regions where the inequalities are not satisfied. Hence determine the maximum value of the objective. The constraint \(x + y \leqslant 10\) is changed to \(x + y \leqslant k\), the other constraints are unchanged. Determine, algebraically, the value of \(k\) for which the maximum value of \(P\) is 3 . Do not draw on the graph from part (a) and do not use the spare grid. Determine, algebraically, the other value of \(k\) for which there is a (non-optimal) vertex of the feasible region at which \(P = 3\). Do not draw on the graph from part (a) and do not use the spare grid. OCR Further Discrete AS 2021 November Q18 1 marks Moderate -0.8 18 8 7 5 Find the packing that results using each of these algorithms. The next-fit method The first-fit method The first-fit decreasing method A student claims that all three methods from part (a) can be used for both 'online' and 'offline' lists. Explain why the student is wrong. The bins of capacity 30 kg are replaced with bins of capacity \(M \mathrm {~kg}\), where \(M\) is an integer. The item of size 23 kg can be split into two items, of sizes \(x \mathrm {~kg}\) and \(( 23 - x ) \mathrm { kg }\), where \(x\) may be any integer value you choose from 1 to 11. No other item can be split. Determine the smallest value of \(M\) for which four bins are needed to pack these eight items. Explain your reasoning carefully. 3 The diagram shows a simplified map of the main streets in a small town. \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_531_1127_301_246} Some of the junctions have traffic lights, these junctions are labelled A to F . There are no traffic lights at junctions X and Y . The numbers show distances, in km, between junctions. Alex needs to check that the traffic lights at junctions A to F are working correctly. Find a route from A to E that has length 2.8 km . Alex has started to construct a table of shortest distances between junctions A to F. \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_543_1173_1420_246} For example, the shortest route from C to B has length 1.7 km , the shortest route from C to D has length 2.5 km and the shortest route from C to E has length 1.8 km . Complete the copy of the table in the Printed Answer Booklet. Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F . Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km . Write down the junctions in the order that Beth visited them. Do not draw on your answer from part (c). 4 Li and Mia play a game in which they simultaneously play one of the strategies \(\mathrm { X } , \mathrm { Y }\) and Z . The tables show the points won by each player for each combination of strategies. A negative entry means that the player loses that number of points. Mia X Y Z \multirow{3}{*}{Li} X 5 - 6 0 \cline { 2 - 5 } Y - 2 3 4 \cline { 2 - 5 } Z - 1 4 8 \cline { 2 - 5 } Mia X Y Z \multirow{2}{*}{Li} X 4 \cline { 2 - 5 } Y 11 5 \cline { 2 - 5 } Z 10 5 1 \cline { 2 - 5 } The game can be converted into a zero-sum game, this means that the total number of points won by Li and Mia is the same for each combination of strategies. Complete the table in the Printed Answer Booklet to show the points won by Mia. Convert the game into a zero-sum game, giving the pay-offs for Li . Use dominance to reduce the pay-off matrix for the game to a \(2 \times 2\) table. You do not need to explain the dominance. Mia knows that Li will choose his play-safe strategy. Determine which strategy Mia should choose to maximise her points. 5 A linear programming problem is formulated as below. Maximise \(\quad \mathrm { P } = 4 \mathrm { x } - \mathrm { y }\) subject to \(2 x + 3 y \geqslant 12\) \(x + y \leqslant 10\) \(5 x + 2 y \leqslant 30\) \(x \geqslant 0 , y \geqslant 0\) Identify the feasible region by representing the constraints graphically and shading the regions where the inequalities are not satisfied. Hence determine the maximum value of the objective. The constraint \(x + y \leqslant 10\) is changed to \(x + y \leqslant k\), the other constraints are unchanged. Determine, algebraically, the value of \(k\) for which the maximum value of \(P\) is 3 . Do not draw on the graph from part (a) and do not use the spare grid. Determine, algebraically, the other value of \(k\) for which there is a (non-optimal) vertex of the feasible region at which \(P = 3\). Do not draw on the graph from part (a) and do not use the spare grid. 6 Sarah is having some work done on her garden. The table below shows the activities involved, their durations and their immediate predecessors. These durations and immediate predecessors are known to be correct. Activity Immediate predecessors Duration (hours) A Clear site - 4 B Mark out new design A 1 C Buy materials, turf, plants and trees - 3 D Lay paths B, C 1 E Build patio B, C 2 F Plant trees D 1 G Lay turf D, E 1 H Finish planting F, G 1 Use a suitable model to determine the following. Sarah needs the work to be completed as quickly as possible. There will be at least one activity happening at all times, but it may not always be possible to do all the activities that are needed at the same time. Determine the earliest and latest times at which building the patio (activity E) could start. There needs to be a 2-hour break after laying the paths (activity D). During this time other activities that do not depend on activity D can still take place. Describe how you would adapt your model to incorporate the 2-hour break. Edexcel D1 2018 Specimen Q3 15 marks Easy -1.2 12.1 \quad 9.3 \quad 15.7 \quad 10.9 \quad 17.4 \quad 6.4 \quad 20.1 \quad 7.9 \quad 8.1 \quad 14.0 Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 33 \hfill [3] The list is to be sorted into descending order. Starting at the left-hand end of the list, perform two passes through the list using a bubble sort. Write down the state of the list that results at the end of each pass. Write down the total number of comparisons and the total number of swaps performed during your two passes. \hfill [4] Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear. \hfill [4] Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33 \hfill [3] Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer. \hfill [1] Edexcel D1 2003 January Q6 9 marks Easy -1.3 25 22 30 18 29 21 27 21 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] Edexcel D1 2005 January Q4 11 marks Easy -1.3 \(650 \quad 431 \quad 245 \quad 643 \quad 455 \quad 134 \quad 710 \quad 234 \quad 162 \quad 452\) The list of numbers above is to be sorted into descending order. Perform a Quick Sort to obtain the sorted list, giving the state of the list after each pass, indicating the pivot elements. [5] The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold in one metre lengths. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from the minimum number of one metre lengths. (You should ignore wastage due to cutting.) [4] Determine whether your solution to part (b) is optimal. Give a reason for your answer. [2] Edexcel D1 2010 June Q3 9 marks Easy -1.3 41 28 42 31 36 32 29 The numbers in the list represent the weights, in kilograms, of seven statues. They are to be transported in crates that will each hold a maximum weight of 60 kilograms. Calculate a lower bound for the number of crates that will be needed to transport the statues. [2] Use the first-fit bin packing algorithm to allocate the statues to the crates. [3] Use the full bin algorithm to allocate the statues to the crates. [2] Explain why it is not possible to transport the statues using fewer crates than the number needed for part (c). [2] (Total 9 marks)