Assignment/allocation matching problems

4 Bob is extending his attic with the help of some friends, including his architect friend Archie. The activities involved, their durations (in days) and Bob's notes are given below. Archie has started to construct an activity network to represent the project.
\includegraphics[max width=\textwidth, alt={}, center]{c2deec7d-0617-4eb0-a47e-5b42ba55b753-5_401_1253_1475_406}

1. Complete the activity network in the Printed Answer Booklet and use it to determine
   • the minimum completion time
   • the critical activities
     for the project.
   • Give two different reasons why the project might take longer than the minimum completion time.
   • For the activity with the longest float
   • calculate this float, in days
   • interpret this float in context.

2 Some of the activities that may be involved in making a cup of tea are listed below. A: Boil water.
B: Put teabag in teapot, pour on boiled water and let tea brew.
C: Get cup from cupboard.
D: Pour tea into cup.
E: Add milk to cup.
F: Add sugar to cup. Activity A must happen before activity B.
Activities B and C must happen before activity D .
Activities E and F cannot happen until after activity C.
Other than that, the activities can happen in any order.

1. Lisa does not take milk or sugar in her tea, so she only needs to use activities \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . In how many different orders can activities \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D be arranged, subject to the restrictions above?
2. Mick takes milk but no sugar, so he needs to use activities \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E . Explain carefully why there are exactly nine different orders for these activities, subject to the restrictions above.
3. Find the number of different orders for all six activities, subject to the restrictions above. Explain your reasoning carefully.

2 A project is represented by the activity network and cascade chart below. The table showing the number of workers needed for each activity is incomplete. Each activity needs at least 1 worker.
\includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_202_565_1605_201}
\includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_328_560_1548_820}

1. Complete the table in the Printed Answer Booklet to show the immediate predecessors for each activity.
2. Calculate the latest start time for each non-critical activity. The minimum number of workers needed is 5 .
3. What type of problem (existence, construction, enumeration or optimisation) is the allocation of a number of workers to the activities? There are 8 workers available who can do activities A and B .
4. 1. Find the number of ways that the workers for activity A can be chosen.
   2. When the workers have been chosen for activity A , find the total number of ways of choosing the workers for activity B for all the different possible values of x , where \(\mathrm { x } \geqslant 1\).

1 Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F . She wants to find a suitable route that does not involve her driving too far.

1. Which standard network problem does Fiona need to solve? The shortest distances between clients, in km, are given in the matrix below.

   	A	B	C	D	E
   A	-	12	8	6	4
   B	12	-	10	8	10
   C	8	10	-	13	10
   D	6	8	13	-	10
   E	4	10	10	10	-

2. Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations.
   State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree. The distance from Fiona's house to each client, in km, is given in the table below.

   	A	B	C	D	E
   F	2	11	9	7	5

3. Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route.
4. (a) Find all the cycles that result from using the nearest neighbour method, starting at F .
   (b) Use these to find an upper bound for the length of Fiona's route.
5. Fiona wants to drive less than 35 km . Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length.

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, Amrit (A), Bernard (B), Cameron (C), David (D), Emily (E) and Francis (F), to six tasks, 1, 2, 3, 4, 5 and 6

1. Explain why it is not possible to find a complete matching. Figure 2 shows an initial matching. Starting from this initial matching,
2. find the two alternating paths that start at C .
3. List the two improved matchings generated by using the two alternating paths found in (b). After training, task 5 is added to Bernard's possible allocation.
   Starting from either of the two improved matchings found in (c),
4. use the maximum matching algorithm to obtain a complete matching. You must list the additional alternating path that you use, and state the complete matching.
   (3)

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.

1. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You must list the alternating path used and state your improved matching.
2. Explain why it is not possible to find a complete matching. Now, exactly one worker may be trained so that a complete matching becomes possible.
   Either worker A can be trained to do task 1 or worker E can be trained to do task 4.
3. Decide which worker, A or E , should be trained. Give a reason for your answer. You may now assume that the worker you identified in (c) has been trained.
4. Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You must list the alternating path used and state your complete matching.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, \(1,2,3\), 4, 5 and 6. Each task must be assigned to only one worker and each worker must be assigned to exactly one task. Figure 2 shows an initial matching.

1. Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from A to 4 . Hence find an improved matching. You should list the alternating path you use, and state your improved matching.
2. Explain why it is not possible to find a complete matching. After training, task 1 is added to worker A's possible allocations.
3. Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you use, and state your complete matching.
   (3)

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \section*{D} \begin{verbatim} B $$\mathrm { A }$$ \end{verbatim} \begin{verbatim} \(\stackrel { \bullet } { \text { E } }\) \end{verbatim} \section*{Diagram 1} Weight of the minimum spanning tree: \(\_\_\_\_\)

4.
.
\section*{Grid 1}

1. \begin{displayquote} McCANN
SMITH
QUAGLIA
CONGDON
EVES
PATEL
BUSH
FOX
OSBORNE

1. Use a quick sort to produce a list of these names in alphabetical order. You must make your pivots clear.
2. Use the binary search algorithm on your list to locate the name PATEL. State the number of iterations you use. \end{displayquote} The binary search algorithm is to be used to search for a name in an alphabetical list of 641 names.
3. Find the maximum number of iterations needed, justifying your answer.

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}$$

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 7.8
2. Determine whether the number of bins used in (a) is optimal. Give a reason for your answer.
3. 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}
4. 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.
5. Explain why Prim's algorithm could not be used to complete the tree.

1. \(\quad \begin{array} { l l l l l l l l l l } 175 & 135 & 210 & 105 & 100 & 150 & 60 & 20 & 70 & 125 \end{array}\)

The numbers in the list above represent the weights, in kilograms, of ten crates. The crates are to be transported in trucks that can each hold a maximum total crate weight of 300 kg .

1. Calculate a lower bound for the number of trucks that will be needed to transport the crates.
2. Using the list provided, carry out a bubble sort to produce a list of the weights in descending order. You need only give the state of the list after each pass.
3. Use the first-fit decreasing bin packing algorithm to allocate the crates to the trucks.

2. A list of eleven numbers is to be sorted into descending order. After one pass, the quick sort algorithm produces the following list $$\begin{array} { l l l l l l l l l l l } 17 & 33 & 14 & 25 & 23 & 28 & 21 & 13 & 9 & 6 & 10 \end{array}$$

1. State, with a reason, which number was used as a pivot for the first pass.
2. Starting at the left-hand end of the above list, obtain the fully sorted list using a bubble sort. You need to write down only the list that results at the end of each pass.
3. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 85

20
23
17
15
22
19
25
13
28
32 A lower bound for the number of bins required is 4

1. Determine the range of possible values of \(n\). You must make your method clear.
   (3)
2. 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.
   (4) When the first-fit bin packing algorithm is applied to the original list of numbers, the following allocation is achieved. \end{table}
   \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-14_1193_1586_1270_185}
   Shortest path from A to J: \(\_\_\_\_\)
   Length of shortest path from A to J: \(\_\_\_\_\) \section*{2.
   \(\_\_\_\_\)} \section*{3.}

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   4. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{d409aaae-811d-4eca-b118-efc927885f97-22_755_1157_246_404} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure}

3. Activity	Immediately preceding activities
   A
   B
   C
   D
   E

   Activity	Immediately preceding activities
   F
   G
   H
   I
   J

   Activity	Immediately preceding activities
   K
   L
   M

   $$v = \ldots \quad x = \ldots \quad y = \ldots$$ \includegraphics[max width=\textwidth, alt={}, center]{d409aaae-811d-4eca-b118-efc927885f97-23_2255_56_315_37}
   \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-23_1153_1338_303_310}
   \section*{Grid 2} 5. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{d409aaae-811d-4eca-b118-efc927885f97-24_591_1433_255_260} \captionsetup{labelformat=empty} \caption{Figure 3
   [0pt] [The total weight of the network is 166]}
   \end{figure} 6.
   \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-26_1287_1645_301_162}
   \section*{Diagram 1} 7. \(\begin{array} { l l l l l l l l l l l } 14 & 20 & 23 & 17 & 15 & 22 & 19 & 25 & 13 & 28 & 32 \end{array}\)

2. At Tesafe supermarket there are 5 trainee staff, Homan \(( H )\), Jenna \(( J )\), Mary \(( M )\), Tim \(( T )\) and Yoshie ( \(Y\) ). They each must spend one week in each of 5 departments, Delicatessen ( \(D\) ), Frozen foods \(( F )\), Groceries \(( G )\), Pet foods \(( P )\), Soft drinks \(( S )\). Next week every department requires exactly one trainee. The table below shows the departments in which the trainees have yet to spend time. Initially \(H , J , M\) and \(T\) are allocated to the first department in their list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way. Starting from this matching,
2. use the maximum matching algorithm to find a complete matching. You must make clear your alternating path and your complete matching.
   (4)

2. (a)
\(\begin{array} { l l l l l l l l l l l } 18 & 20 & 11 & 7 & 17 & 15 & 14 & 21 & 23 & 16 & 9 \end{array}\) The list of numbers shown above is to be sorted into ascending order. Apply quick sort to obtain the sorted list. You must make your pivots clear. \begin{figure}[h] \end{figure} Figure 3 represents a network of paths in a park. The number on each arc represents the length of the path in metres.
(b) Using your answer to part (a) and Kruskal's algorithm, find a minimum spanning tree for the network in Figure 3. You should list the arcs in the order in which you consider them and state whether you are adding it to your minimum spanning tree.
(c) Find the total weight of the minimum spanning tree.

1. Max Lauren John Hannah Kieran Tara Richard Imogen

1. Use a quick sort to produce a list of these names in ascending alphabetical order. You must make your pivots clear.
2. Use the binary search algorithm on your list from part (a) to try to locate the name 'Hugo'.

2. $$\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}$$ The numbers represent the sizes, in megabytes (MB), of eight files.
The files are to be stored on 50 MB discs.

1. Calculate a lower bound for the number of discs needed to store all eight files.
2. Use the first-fit bin packing algorithm to fit the files onto the discs.
3. Perform a bubble sort on the numbers in the list to sort them into descending order. You need only write down the final result of each pass.
4. Use the first-fit decreasing bin packing algorithm to fit the files onto the discs.

5.

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 20.
2. The list of numbers is to be sorted into descending order. Use a bubble sort to obtain the sorted list, giving the state of the list after each complete pass.
3. Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 20.
4. Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.

5. $$90,50,55,40,20,35,30,25,45$$

1. Use the bubble sort algorithm to sort the list of numbers above into descending order showing the rearranged order after each pass. Jessica wants to record a number of television programmes onto video tapes. Each tape is 2 hours long. The lengths, in minutes, of the programmes she wishes to record are: $$\text { 55, 45, 20, 30, 30, 40, 20, 90, 25, 50, } 35 \text { and } 35 .$$
2. Find the total length of programmes to be recorded and hence determine a lower bound for the number of tapes required.
3. Use the first fit decreasing algorithm to fit the programmes onto her 2-hour tapes. Jessica's friend Amy says she can fit all the programmes onto 4 tapes.
4. Show how this is possible.

1. The table above shows the points obtained by each of the teams in a football league after they had each played 6 games. The teams are listed in alphabetical order. Carry out a quick sort to produce a list of teams in descending order of points obtained.

4. The following list gives the names of some students who have represented Britain in the International Mathematics Olympiad. Roper ( \(R\) ), Palmer ( \(P\) ), Boase ( \(B\) ), Young ( \(Y\) ), Thomas ( \(T\) ), Kenney ( \(K\) ), Morris ( \(M\) ), Halliwell ( \(H\) ), Wicker ( \(W\) ), Garesalingam ( \(G\) ).

1. Use the quick sort algorithm to sort the names above into alphabetical order.
2. Use the binary search algorithm to locate the name Kenney.
   (4)
   \includegraphics[max width=\textwidth, alt={}, center]{9ca3e12a-63fa-49c9-91fc-eedfb024417a-4_488_1573_392_239} The network in Fig. 3 shows the activities involved in the process of producing a perfume. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, taken to complete the activity.
3. Calculate the early time and the late time for each event, showing them on Diagram 1 in the answer booklet.
4. Hence determine the critical activities.
5. Calculate the total float time for \(D\). Each activity requires only one person.
6. Find a lower bound for the number of workers needed to complete the process in the minimum time. Given that there are only three workers available, and that workers may not share an activity,
7. schedule the activities so that the process is completed in the shortest time. Use the time line in the answer booklet. State the new shortest time.
   (5)

1. \(\begin{array} { l l l l l l l l l } 29 & 52 & 73 & 87 & 74 & 47 & 38 & 61 & 41 \end{array}\) The numbers in the list represent the lengths in minutes of nine radio programmes. They are to be recorded onto tapes which each store up to 100 minutes of programmes.

1. Obtain a lower bound for the number of tapes needed to store the nine programmes.
2. Use the first-fit bin packing algorithm to fit the programmes onto the tapes.
3. Use the first-fit decreasing bin packing algorithm to fit the programmes onto the tapes.

1. $$\begin{array} { l l l l l l l l l } 31 & 10 & 38 & 45 & 19 & 47 & 35 & 28 & 12 \end{array}$$

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 60
2. 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.
3. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 60
4. Determine whether the number of bins used in (c) is optimal. Give a reason for your answer.

6.
\(\begin{array} { l l l l l l l l l } 24 & 14 & 8 & x & 19 & 25 & 6 & 17 & 9 \end{array}\) The numbers in the list represent the exact weights, in kilograms, of 9 suitcases. One suitcase is weighed inaccurately and the only information known about the unknown weight, \(x \mathrm {~kg}\), of this suitcase is that \(19 < x \leqslant 23\). The suitcases are to be transported in containers that can hold a maximum of 50 kilograms.

1. Use the first-fit bin packing algorithm, on the list provided, to allocate the suitcases to containers.
2. Using the list provided, carry out a quick sort to produce a list of the weights in descending order. Show the result of each pass and identify your pivots clearly.
3. Apply the first-fit decreasing bin packing algorithm to the ordered list to determine the 2 possible allocations of suitcases to containers. After the first-fit decreasing bin packing algorithm has been applied to the ordered list, one of the containers is full.
4. Calculate the possible integer values of \(x\). You must show your working.