OCR GCE AS Level Further Maths B (MEI) Modelling with Algorithms (optional - choose any two of Y411/Y412/Y413/Y414) November 2020 question paper Y413

The table in Fig. 1 lists the immediate predecessors required for each activity in a project.

Draw an activity network, using activity on arc, to represent the project. Your network should

only contain two dummy activities.

Given that each activity in Fig. 1 takes 1 hour to be completed, state the activities that cannot

possibly be critical.

The fundraising committee at a school are planning a dance event. There must always be one teacher on duty throughout the event. The event is planned to last for 2 hours 30 minutes, which has been split into five slots of 30 minutes each.

Five teachers, Mr Baldock (B), Miss Cash (C), Mr Dawes (D), Dr Evans (E) and Miss Fondu (F), each agree to be on duty for one 30-minute slot. The table in Fig. 2.1 shows which teacher is prepared to take each 30-minute slot.

Represent this information as a bipartite graph with five vertices in each set.

Formulate the problem of finding a maximal matching for the bipartite graph drawn in part (a)

as an LP.

The LP was run in a solver and the output is shown in Fig. 2.2.

Interpret the output to give a solution to the matching problem.

Explain whether this solution is unique.

The list below shows the sizes of eight items.

32 37 25 18 34 27 15 30

Show the result of applying the first fit algorithm to pack the items into bins that have a

capacity of 70.

An algorithm for sorting a list of n numbers into descending order is given below.

The first pass consists of the following. Compare the second value with the first and swap if necessary (that is if the second value is larger than the first).

The second pass consists of the following. Compare the third value with the second and swap if necessary. If a swap happened compare the new second value with the first as in the first pass.

The third pass consists of the following. Compare the fourth value with the third and swap if necessary. If a swap happened compare the new third value with the second as in the second pass.

Continue in this way for n - 1 passes.

Starting at the left-hand end of the list the result after each pass through the above algorithm on the original list of eight numbers is shown below.

Complete the table in the Printed Answer Booklet showing the number of comparisons and

swaps during each pass through the algorithm.

Show the result of applying the first fit decreasing algorithm to pack items with the sizes listed

above into bins that have a capacity of 70.

The number of comparisons is used as a measure of the complexity of the above sorting algorithm.

State, in terms of n, the order of the best-case complexity of the sorting algorithm.

Draw an example of a simply connected graph with five nodes of orders 1, 1, 2, 2 and 4.

A simply connected graph G has seven nodes.

Write down the minimum number of arcs in G.

Write down the maximum number of arcs in G.

Write down the adjacency matrix for the graph in Fig. 4.

A graph has seven nodes of orders 1, 2, 3, 3, 3, 3 and x where x > 0. Determine why this

graph, regardless of the value of x, cannot be a tree.

Explain why the maximum possible flow along SB must be less than 47 litres per minute.

The cut α partitions the vertices into the sets {S, A, B, E}, {C, D, F, G, T}. Calculate the

capacity of the cut α.

It is given that when water is flowing through the pipes the arcs out of nodes B, D and E are saturated. Use the diagram in the Printed Answer Booklet to show how a flow of 116 litres per

minute can be achieved.

Use a suitable cut to prove that this is the maximum possible flow through the system of pipes.

One of the three pipes from S is to have its capacity increased so that the maximum possible flow through the system can be increased too.

• Determine which of the three pipes should have its capacity increased.

• Determine the new capacity of this pipe.

• State the new maximum possible flow through the system.

Fig. 6 shows a network.

Dijkstra’s algorithm has been applied to the network and the shortest path from A to G is ACFEDG.

Complete the table in the Printed Answer Booklet showing the weight of each arc. Note that

you will not be able to determine the weight of one of the arcs.

When Prim’s algorithm is applied to the network, starting from A, the order in which the arcs are selected for the minimum spanning tree is AC, CF, EF, DE, DG, GH and BE.

Given that the weight of each arc is both integer-valued and unique.

Determine the range of possible values for the missing arc weight from part (a).

When Kruskal’s algorithm is applied to the network, the order in which the arcs are selected for the minimum spanning tree is EF, GH, DE, AC, DG, CF and BE.

Write down the missing arc weight from part (a).

• Complete the initial tableau in the Printed Answer Booklet so that the simplex method may be used to solve this problem.

• Show how the constraints for the problem have been made into equations using slack

variables.

After one iteration of the simplex method a computer produces the tableau in Fig. 7.1.

Explain how the tableau in Fig. 7.1 shows that the solution obtained after the first iteration is

not optimal.

Perform a second iteration of the simplex method, giving each entry as an exact value.

The final tableau, after a third iteration of the simplex method, is given in Fig. 7.2.

State the number of each size of tent that should be placed on the site.

Determine the total expected profit.

The owner of the site realises that for health and safety reasons the total number of small and medium tents must be at least 100.

Explain why the simplex method cannot be used to solve the problem with this additional

constraint.

The two-stage simplex method is to be used to solve this modified problem.

• Formulate the additional constraint as an equation.

• Define the new objective function.

In both cases, you are required to define the variables you use.