Assignment/allocation matching problems

3. This question should be answered on the sheet provided. A firm of auditors is to place one trainee accountant at each of its five offices. These are situated in Dundee, Edinburgh, Glasgow and London. There are two offices in London, one of which is the company's Head Office. The table summarises the trainees’ preferences.

1. Draw a bipartite graph to model this situation.
2. Explain why no complete matching is possible. Trainee \(T\) is persuaded that either office in London would be just as good for her personal development as the Edinburgh office.
3. Draw a second bipartite graph to model the changed situation. In an initial matching, trainee \(P\) is placed in the Dundee office, trainee \(R\) in the Glasgow office, and trainee \(S\) in the Edinburgh office.
4. Draw this initial matching.
5. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must indicate how the algorithm has been applied, stating clearly the alternating paths you use and the final matching.
   (7 marks) Turn over

1
A group of workers is involved in a decorating project. The table shows the activities involved. Each worker can perform any of the given activities. The activity network for the project is given in Figure 1 below.

1. Find the earliest start time and the latest finish time for each activity, inserting their values on Figure 1.
2. Hence find:
   1. the critical path;
   2. the float time for activity \(D\).
3. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-02_647_1657_1640_180}
   \end{figure}
4. 1. The critical path is \(\_\_\_\_\)
   2. The float time for activity \(D\) is \(\_\_\_\_\)
5. Given that each activity starts as early as possible and assuming that there is no limit to the number of workers available, draw a resource histogram for the project on Figure 2 below, indicating clearly which activities are taking place at any given time.
6. It is later discovered that there are only 8 workers available at any time. Use resource levelling to construct a new resource histogram on Figure 3 below, showing how the project can be completed with the minimum extra time. State the minimum extra time required.
7. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-03_586_1708_922_150}
   \end{figure}
8. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-03_496_1705_1672_153}
   \end{figure} The minimum extra time required is \(\_\_\_\_\)

1. \begin{figure}[h] \end{figure} Figure 1 shows a network of roads connecting six villages \(A , B , C , D , E\) and \(F\). The lengths of the roads are given in km .

1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. The table can now be taken to represent a complete network.
2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once.
   (3)
3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
   (1)
4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.
   (2)

1. The table below shows the least costs, in pounds, of travelling between six cities, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.
   (2)
2. Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
   (1)
3. Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.
4. State the best upper bound from your answers to (b) and (c).
5. Starting by deleting A , and all of its arcs, find a lower bound for the route length.

7 Annie (A), Brigid (B), Carla (C) and Diane ( \(D\) ) are hanging wallpaper in a stairwell. They have broken the job down into four tasks: measuring and cutting the paper ( \(M\) ), pasting the paper ( \(P\) ), hanging and then trimming the top end of the paper ( \(H\) ) and smoothing out the air bubbles and then trimming the lower end of the paper ( \(S\) ). They will each do one of these tasks.

• Annie does not like climbing ladders but she is prepared to do tasks \(M , P\) or \(S\)
• Brigid gets into a mess with paste so she is only able to do tasks \(M\) or \(S\)
• Carla enjoys hanging the paper so she wants to do task \(H\) or task \(S\)
• Diane wants to do task \(H\)

Initially Annie chooses task \(M\), Brigid task \(S\) and Carla task \(H\).

1. Draw a bipartite graph to show the available pairings between the people and the tasks. Write down an alternating path to improve the initial matching and write down the complete matching from your alternating path. Hanging the wallpaper is part of a bigger decorating project. The table lists the activities involved, their durations and precedences.
2. Maximin value \(=\) Route \(=\)

4 Anya \(( A )\), Ben \(( B )\), Connie \(( C )\), Derek \(( D )\) and Emma \(( E )\) work for a local newspaper. The editor wants them each to write a regular weekly article for the paper. The items needed are: problem page \(( P )\), restaurant review \(( R )\), sports news \(( S )\), theatre review \(( T )\) and weather report \(( W )\). Anya wants to write either the problem page or the restaurant review. She is given the problem page. Ben wants the restaurant review, the sports news or the theatre review. The editor gives him the restaurant review. Connie wants either the theatre review or the weather report. The editor gives her the theatre review. Derek wants the problem page, the sports news or the weather report. He is given the weather report. Emma is only interested in writing the problem page but this has already been given to Anya.

1. Draw a bipartite graph to show the possible pairings between the writers ( \(A , B , C , D\) and \(E\) ) and the articles ( \(P , R , S , T\) and \(W\) ). On your bipartite graph, show who has been given which article by the editor.
2. Construct the shortest possible alternating path, starting from Emma, to find a complete matching between the writers and the articles. Write a list showing which article each writer is given with this complete matching. When the writers send in their articles the editor assigns a sub-editor to each one to check it. The sub-editors can check at most one article each. The table shows how long, in minutes, each sub-editor would typically take to check each article.

   \multirow{8}{*}{Sub-editor}	\multirow{2}{*}{}	Article
   		\(P\)	\(R\)	\(S\)	\(T\)	\(W\)
   	Jeremy ( \(J\) )	56	56	51	57	58
   	Kath ( \(K\) )	53	52	53	54	54
   	Laura ( \(L\) )	57	55	52	58	60
   	Mohammed ( \(M\) )	59	55	53	59	57
   	Natalie ( \(N\) )	57	57	53	59	60
   	Ollie ( \(O\) )	58	56	51	56	57

   The editor wants to find the allocation for which the total time spent checking the articles is as short as possible.
3. Apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the sub-editors and the articles. Explain how each table is formed and write a list showing which sub-editor should be assigned to which article. If each minute of sub-editor time costs \(\pounds 0.25\), calculate the total cost of checking the articles each week.

1 Andy ( \(A\) ), Beth ( \(B\) ), Chelsey ( \(C\) ), Dean ( \(D\) ) and Elly ( \(E\) ) have formed a quiz team. They have entered a quiz in which, as well as team questions, each of them must answer individual questions on a specialist topic. The specialist topics could be any of: food \(( F )\), geography \(( G )\), history \(( H )\), politics ( \(P\) ), science ( \(S\) ) and television ( \(T\) ). The team members do not know which five specialist topics will arise in the quiz. Andy wants to answer questions on either food or television; Beth wants to answer questions on geography, history or science; Chelsey wants to answer questions on geography or television; Dean wants to answer questions on politics or television; and Elly wants to answer questions on history or television.

1. Draw a bipartite graph to show the possible pairings between the team members and the specialist topics. In the quiz, the first specialist topic is food, and Andy is chosen to answer the questions. The second specialist topic is geography, and Beth is chosen. The next specialist topic is history, and Elly is chosen. The fourth specialist topic is science. Beth has already answered questions so Dean offers to try this round. The final specialist topic is television, and Chelsey answers these questions.
2. Draw a second bipartite graph to show these pairings, apart from Dean answering the science questions. Write down an alternating path starting from Dean to show that there would have been a better way to choose who answered the questions had the topics been known in advance. Write down which team member would have been chosen for each specialist topic in this case.
3. In a practice, although the other team members were able to choose topics that they wanted, Beth had to answer the questions on television. Write down which topic each team member answered questions on, and which topic did not arise.

1 Four friends, Amir (A), Bex (B), Cerys (C) and Duncan (D), are visiting a bird sanctuary. They have decided that they each will sponsor a different bird. The sanctuary is looking for sponsors for a kite \(( K )\), a lark \(( L )\), a moorhen \(( M )\), a nightjar \(( N )\), and an owl \(( O )\). Amir wants to sponsor the kite, the nightjar or the owl; Bex wants to sponsor the lark, the moorhen or the owl; Cerys wants to sponsor the kite, the lark or the owl; and Duncan wants to sponsor either the lark or the owl.

1. Draw a bipartite graph to show which friend wants to sponsor which birds. Amir chooses to sponsor the kite and Bex chooses the lark. Cerys then chooses the owl and Duncan is left with no bird that he wants.
2. Write down the shortest possible alternating path starting from the nightjar, and hence write down one way in which all four friends could have chosen birds that they wanted to sponsor.
3. List a way in which all four friends could have chosen birds they wanted to sponsor, with the owl not being chosen.

1 Five film studies students need to review five different films for an assignment, but only have one evening left before the assignment is due in. They decide that they will share the work out so that each of them reviews just one film. Jack \(( J )\) wants to review a horror movie; Karen \(( K )\) wants to review an animated film; Lee \(( L )\) wants to review a film that is suitable for family viewing; Mark ( \(M\) ) wants to review an action adventure film and Nikki ( \(N\) ) wants to review anything that is in 3D. The film "Somewhere" ( \(S\) ) has been classified as a horror movie and is being shown in 3D; "Tornado Terror" ( \(T\) ) has been classified as an action adventure film that is suitable for family viewing; "Underwater" \(( U )\) is an animated action adventure film; "Vampires" ( \(V\) ) is an animated horror movie that is suitable for family viewing and "World" ( \(W\) ) is an animated film.

1. Draw a bipartite graph to show which student ( \(J , K , L , M , N\) ) wants to review which films ( \(S , T , U\), \(V , W\) ). Initially Jack says that he will review "Somewhere", Karen then chooses "Underwater" and Lee chooses "Tornado Terror", but this would leave both Mark and Nikki with films that they do not want.
2. Write down the shortest possible alternating path starting from Nikki, and hence write down an improved, but still incomplete, matching.
3. From this incomplete matching, write down the shortest possible alternating path starting from "World", and hence write down a complete matching between the students and the films.
4. Show that this is the only possible complete matching between the students and the films.

1 A TV soap opera has five main characters, Alice ( \(A\) ), Bob ( \(B\) ), Charlie ( \(C\) ), Dylan ( \(D\) ) and Etty ( \(E\) ). A different character is scheduled to play the lead in each of the next five episodes. Alice, Dylan and Etty are all in the episode about the fire ( \(F\) ), but Bob and Charlie are not. Alice and Bob are the only main characters in the episode about the gas leak ( \(G\) ). Alice, Charlie and Etty are the only main characters in the episode about the house break-in (H). The episode about the icy path (I) stars Alice and Charlie only. The episode about the jail break ( \(J\) ) does not star any of the main characters who were in the episodes about the fire or the house break-in.

1. Draw a bipartite graph to show which main characters ( \(A , B , C , D , E\) ) are in which of the next five episodes \(( F , G , H , I , J )\). The writer initially decides to make Alice play the lead in the episode about the fire, Bob in the episode about the gas leak and Charlie in the episode about the house break-in.
2. Write down the shortest possible alternating path starting from Dylan. Hence draw the improved, but still incomplete, matching that results.
3. From this incomplete matching, write down the shortest possible alternating path starting from the character who still has no leading part allocated. Hence draw the complete matching that results.
4. By starting with the episode about the jail break, explain how you know that this is the only possible complete matching between the characters and the episodes.

2 A talent contest has five contestants. In the first round of the contest each contestant must sing a song chosen from a list. No two contestants may sing the same song. Adam (A) chooses to sing either song 1 or song 2; Bex (B) chooses 2 or 4; Chris (C) chooses 3 or 5; Denny (D) chooses 1 or 3; Emma (E) chooses 3 or 4.

1. Draw a bipartite graph to show this information. Put the contestants (A, B, C, D and E) on the left hand side and the songs ( \(1,2,3,4\) and 5 ) on the right hand side. The contest organisers propose to give Adam song 1, Bex song 2 and Chris song 3.
2. Explain why this would not be a satisfactory way to allocate the songs.
3. Construct the shortest possible alternating path that starts from song 5 and brings Denny (D) into the allocation. Hence write down an allocation in which each of the five contestants is given a song that they chose.
4. Find a different allocation in which each of the five contestants is given a song that they chose. Emma is knocked out of the contest after the first round. In the second round the four remaining contestants have to act in a short play. They will each act a different character in the play, chosen from a list of five characters. The table below shows how suitable each contestant is for each character as a score out of 10 (where 0 means that the contestant is completely unsuitable and 10 means that they are perfect to play that character).

   \multirow{2}{*}{}	Character
   	Fire Chief	Gardener	Handyman	Juggler	King
   Adam	4	9	7	0	7
   Bex	6	8	3	8	0
   Chris	7	4	5	2	7
   Denny	6	6	2	7	1

   The Hungarian Algorithm is to be used to find the matching with the greatest total score. Before the Hungarian Algorithm can be used, each score is subtracted from 10 and then a dummy row of zeroes is added at the bottom of the table.
5. Explain why the scores could not be used as given in the table and explain why a dummy row is needed.
6. Apply the Hungarian Algorithm, showing your working carefully, to match the contestants to characters.

1

1. A café sells five different types of filled roll. Mr King buys one of each to take home to his family. The family consists of Mr King's daughter Fiona ( \(F\) ), his mother Gwen ( \(G\) ), his wife Helen ( \(H\) ), his son Jack ( \(J\) ) and Mr King ( \(K\) ). The table shows who likes which rolls.

   		\(F\)	\(G\)	\(H\)	\(J\)	\(K\)
   Avocado and bacon	\(( A )\)	\(\checkmark\)		\(\checkmark\)
   Beef and horseradish	\(( B )\)		\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)
   Chicken and stuffing	\(( C )\)		\(\checkmark\)		\(\checkmark\)
   Duck and plum sauce	\(( D )\)			\(\checkmark\)		\(\checkmark\)
   Egg and tomato	\(( E )\)	\(\checkmark\)

   1. Draw a bipartite graph to represent this information. Put the fillings ( \(A , B , C , D\) and \(E\) ) on the left-hand side and the members of the family ( \(F , G , H , J\) and \(K\) ) on the right-hand side. Fiona takes the avocado roll; Gwen takes the beef roll; Helen takes the duck roll and Jack takes the chicken roll.
   2. Draw a second bipartite graph to show this incomplete matching.
   3. Construct the shortest possible alternating path from \(E\) to \(K\) and hence find a complete matching. State which roll each family member has with this complete matching.
   4. Find a different complete matching.
2. Mr King decides that the family should eat more fruit. Each family member gives a score out of 10 to five fruits. These scores are subtracted from 10 to give the values below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Family member}

   		\(F\)	\(G\)	\(H\)	\(J\)	\(K\)
   Lemon	\(L\)	8	8	8	8	1
   Mandarin	\(M\)	4	8	6	4	2
   Nectarine	\(N\)	9	9	9	7	1
   Orange	\(O\)	4	6	5	4	3
   Peach	\(P\)	6	9	7	5	0

   \end{table} The smaller entries in each column correspond to fruits that the family members liked most.
   Mr King buys one of each of these five fruits. Each family member is to be given a fruit.
   Apply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working clearly. Which family member should be given which fruit?

1 Adam, Barbara and their children Charlie, Donna, Edward and Fiona all want cereal for breakfast. The only cereal in the house is a pack of six individual portions of different cereals. The table shows which family members like each of the cereals in the pack.

1. Draw a bipartite graph to represent this information. Adam gives the cornflakes to Fiona, the oatie bits to Edward, the rice pips to Donna, the choco pips to Charlie and the wheat biscs to Barbara. However, this leaves the honey footballs for Adam, which is not a possible pairing.
2. Draw a second bipartite graph to show this incomplete matching.
3. Construct the shortest possible alternating path from 6 to \(A\) and hence find a complete matching between the cereals and the family members. Write down which family member is given each cereal with this complete matching.
4. Adam decides that he wants cornflakes. Construct an alternating path starting at \(A\), based on your answer to part (iii) but with Adam being matched to the cornflakes, to find another complete matching. Write down which family member is given each cereal with this matching.

1 Six students are choosing their tokens for a board game. The bipartite graph in Fig. 1 shows which token each student is prepared to have. \begin{figure}[h] \end{figure} Initially Ezra takes the flat iron, Jonah the old boot, Lily the racing car and Molly the scottie dog. This leaves Adele and Noah with tokens that they do not want. This incomplete matching is shown in Fig. 2 below. \begin{table}[h] \end{table}

1. Write down the shortest possible alternating path that starts at A and finishes at either B or T . Hence write down a matching that only excludes Noah and one of the tokens.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at N and finishes at whichever of B and T has still not been taken. Hence write down a complete matching between the students and the tokens.
3. By starting at B on Fig. 1, show that there are exactly two complete matchings between the students and the tokens.

1 The infamous fictional detective Agatha Parrot is working on a case and decides to invite each of the four suspects to visit her for tea. She will invite one suspect to tea on Sunday (S), another on Monday (M), another on Tuesday (T) and the final suspect on Wednesday (W).

• Beryl Batty (B) could come to tea on Sunday or Monday but she is away for a few days after that.
• Colonel Chapman (C) could come to tea on Sunday or Tuesday, but is busy on the other days.
• Dimitri Delacruz (D) could only come to tea on Monday or Wednesday.
• Erina El-Sayed (E) could come to tea on Sunday, Monday or Tuesday, but will be away on Wednesday.
  1. Draw a bipartite graph to show which suspects could come to tea on which day.

Agatha initially intended to invite Beryl to tea on Sunday, Dimitri on Monday and Colonel Chapman on Tuesday. However this would mean that Erina would not be able to come to tea, as she will be away on Wednesday.

Draw a second bipartite graph to show this incomplete matching.

Working from this incomplete matching, find the shortest possible alternating path, starting at Erina, to achieve a breakthrough. Write down which suspect is invited on which day with this matching. Before issuing invitations, Agatha overhears Erina making arrangements to go to tea with the vicar one day. She knows that Erina will not want to accept two invitations to tea on the same day. Unfortunately, Agatha does not know which day Erina has arranged to go to tea with the vicar, other than that it was not Sunday. Agatha invites Erina to tea on Sunday and the others when she can. After having tea with all four suspects she considers what they have said and invites them all back on Friday. She then accuses the person who came to tea on Monday of being guilty.

Who does Agatha accuse of being guilty?

1 Josh is making a calendar. He has chosen six pictures, each of which will represent two months in the calendar. He needs to choose which picture to use for each two-month period. The bipartite graph in Fig. 1 shows for which months each picture is suitable. \begin{figure}[h] \end{figure} Initially Josh chooses the sailing ships for March/April, the sunset for July/August, the snow scene for November/December and the swans for May/June. This incomplete matching is shown in Fig. 2 below. \begin{table}[h] \end{table}

1. Write down the shortest possible alternating path that starts at (JF) and finishes at either (2) or (4). Hence write down a matching that only excludes (SO) and one of the pictures.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at (SO) and finishes at whichever of (2) and (4) has still not been matched. Hence write down a complete matching between the pictures and the months.
3. Explain why three of the arcs in Fig. 1 must appear in the graph of any complete matching. Hence find a second complete matching.

1 [Answer this question on the insert provided.]
Six neighbours have decided to paint their houses in bright colours. They will each use a different colour.

• Arthur wants to use lavender, orange or tangerine.
• Bridget wants to use lavender, mauve or pink.
• Carlos wants to use pink or scarlet.
• Davinder wants to use mauve or pink.
• Eric wants to use lavender or orange.
• Ffion wants to use mauve.

Arthur chooses lavender, Bridget chooses mauve, Carlos chooses pink and Eric chooses orange. This leaves Davinder and Ffion with colours that they do not want.

1. Draw a bipartite graph on the insert, showing which neighbours ( \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) ) want which colours (L, M, O, P, S, T). On a separate diagram on the insert, show the incomplete matching described above.
2. By constructing alternating paths obtain the complete matching between the neighbours and the colours. Give your paths and show your matching on the insert.
3. Fill in the table on the insert to show how the Hungarian algorithm could have been used to find the complete matching. (You do not need to carry out the Hungarian algorithm.)

1. This question should be answered on the sheet provided.

\begin{figure}[h] \end{figure} The network in Figure 1 shows the distances, in miles, between the five villages in which Sarah is planning to enquire about holiday work, with village \(A\) being Sarah's home village.

1. Illustrate this situation as a complete network showing the shortest distances.
   (2 marks)
2. Use the nearest neighbour algorithm, starting with \(A\), to find an upper bound to the length of a tour beginning and ending at \(A\).
   (2 marks)
3. Interpret the tour found in part (b) in terms of the original network.
   (2 marks)

2. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 1 shows a network in which the nodes represent five major rides in a theme park and the arcs represent paths between these rides. The numbers on the arcs give the length, in metres, of the paths.

1. By inspection, add additional arcs to make a complete network showing the shortest distances between the rides.
   (2 marks)
2. Use the nearest neighbour algorithm, starting at \(A\), and your complete network to find an upper bound to the length of a tour visiting each ride exactly once.
3. Interpret the tour found in part (b) in terms of the original network.

5 A network of roads connects the villages \(A , B , C , D , E , F\) and \(G\) The weight on each arc in the network represents the distance, in miles, between adjacent villages. The network is shown in the diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-05_769_983_543_511} 5

1. Draw, in the space below, the spanning tree of minimum total length for this road network. 5
2. Find the total length of the spanning tree drawn in part (a). A Young Enterprise Company decides to sell two types of cakes at a breakfast club. The two types of cakes are blueberry and chocolate. From its initial market research, the company knows that it will:
   • sell at most 200 cakes in total
   • sell at least twice as many blueberry cakes as they will chocolate cakes
   • make 20 p profit on each blueberry cake they sell
   • make 15p profit on each chocolate cake they sell.
   The company's objective is to maximise its profit. Formulate the Young Enterprise Company's situation as a linear programming problem.

4 The complete bipartite graph \(K _ { 3,4 }\) connects the vertices \(\{ 2,4,6 \}\) to the vertices \(\{ 1,3,5,7 \}\).

1. How many arcs does the graph \(K _ { 3,4 }\) have?
2. Deduce how many different paths are there that pass through each of the vertices once and once only. The direction of travel of the path does not matter. The arcs are weighted with the product of the numbers at the vertices that they join.
3. (a) Use an appropriate algorithm to find a minimum spanning tree for this network.
   (b) Give the weight of the minimum spanning tree.

6 Sheona and Tim are making a short film. The activities involved, their durations and immediate predecessors are given in the table below.

1. By using an activity network, find:
   • the minimum project completion time
   • the critical activities
   • the float on each non-critical activity.
   • Give two reasons why the filming may take longer than the minimum project completion time.
   Each activity will involve either Sheona or Tim or both.
   • The activities that Sheona will do are ticked in the S column.
   • The activities that Tim will do are ticked in the T column.
   • They will do the planning and finishing together.
   • Some of the activities involve other people as well.
   An additional restriction is that Sheona and Tim can each only do one activity at a time.
2. Explain why the minimum project completion is longer than in part (i) when this additional restriction is taken into account.
3. The project must be completed in 14 days. Find:
   (a) the longest break that either Sheona or Tim can take,
   (b) the longest break that Sheona and Tim can take together,
   (c) the float on each activity.

3

1. Give an example of a standard sorting algorithm that can be used when some of the values are not known until after the sorting has been started. Becky needs to sort a list of numbers into increasing order.
   She uses the following algorithm:
   STEP 1: Let \(L\) be the first value in the input list.
   Write this as the first value in the output list and delete it from the input list.
   STEP 2: If the input list is empty go to STEP 7.
   Otherwise let \(N\) be the new first value in the input list and delete this value from the input list. STEP 3: \(\quad\) Compare \(N\) with \(L\).
   STEP 4: If \(N\) is less than or equal to \(L\)
   • write the value of \(N\) immediately before \(L\) in the output list,
   • replace \(L\) with the first value in the new output list,
   • then go to STEP 2.
   STEP 5: If \(N\) is greater than \(L\)
   • if \(L\) is the value of the last number in the output list, go to STEP 6;
   • otherwise, replace \(L\) with the next value in the output list and then go to STEP 3.
   STEP 6: \(\quad\) Write the value of \(N\) immediately after \(L\) in the output list. Let \(L\) be the first value in the new output list and then go to STEP 2. STEP 7: Print the output list and STOP.
2. Trace through Becky's algorithm when the input list is $$\begin{array} { l l l l l l } 6 & 9 & 5 & 7 & 6 & 4 \end{array}$$ Complete the table in the Printed Answer Booklet, starting a new row each time that STEP 3 or STEP 7 is used.
   You should not need all the lines in the Answer Booklet. Becky measures the efficiency of her sort by counting using the number of times that STEP 3 is used.
3. 1. How many times did Becky use STEP 3 in sorting the list from part (b)?
   2. What is the greatest number of times that STEP 3 could be used in sorting a list of 6 values? A computer takes 15 seconds to sort a list of 60 numbers using Becky's algorithm.
4. Approximately how long would you expect it to take the computer to sort a list of 300 numbers using the algorithm?

3

1. The list below is to be sorted into increasing order using bubble sort.
   \(\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}\)
   1. Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
   2. Write down the number of comparisons and the number of swaps used in each of these passes.
2. The list below is to be sorted into increasing order using shuttle sort.
   \(\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}\)
   1. Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
   2. Write down the number of comparisons and the number of swaps used in each of these passes.
3. Use the results from parts (a) and (b) to compare the efficiency of bubble sort with the efficiency of shuttle sort for the first three passes of this list. You do not need to consider what happens after these three passes.

3 The list of numbers below is to be sorted into increasing order.
\(\begin{array} { l l l l l l l l } 23 & 10 & 18 & 7 & 62 & 54 & 31 & 82 \end{array}\)

1. Sort the list using bubble sort. You do not need to show intermediate working.
   1. Record the list that results at the end of each pass.
   2. Record the number of swaps used in each pass.
2. Now sort the original list using shuttle sort. You do not need to show intermediate working.
   1. Record the list that results at the end of each pass.
   2. Record the number of swaps used in each pass.
3. Using the total number of comparisons plus the total number of swaps as a measure of efficiency, explain why shuttle sort is more efficient than bubble sort for sorting this particular list. Bubble sort and shuttle sort are both \(\mathrm { O } \left( n ^ { 2 } \right)\).
4. Explain what this means for the run-time of the algorithms when the length of the list being sorted changes from 1000 to 3000.