Edexcel A Level Maths D1 · Decision Mathematics 1 June 2011 question paper 6689

1. Jenny 2. Merry 3. Charles 4. Ben 5. Toby 6. Hyo 7. Kim 8. Richard 9. Greg 10. Freya A binary search is to be performed on the names in the list above to locate the name Kim.

Explain why a binary search cannot be performed with the list in its present form.

Using an appropriate algorithm, alter the list so that a binary search can be performed, showing the state of the list after each complete iteration. State the name of the algorithm you have used.

Define the terms

tree,

minimum spanning tree.

Use Kruskal’s algorithm to find a minimum spanning tree for the network shown in Figure 1. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.

Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book.

State whether your minimum spanning tree is unique. Justify your answer.

Figure 2

Figure 2 shows the constraints of a linear programming problem in x and y, where R is the feasible region.

Write down the inequalities that form region R. The objective is to maximise 3 x + y.

Find the optimal values of x and y. You must make your method clear.

Obtain the optimal value of the objective function. Given that integer values of x and y are now required,

write down the optimal values of x and y.

Figure 3 shows the possible allocations of five workers, Adam (A), Catherine (C), Harriet (H), Josh (J) and Richard (R) to five tasks, 1, 2, 3, 4 and 5. Figure 4 shows an initial matching. There are three possible alternating paths that start at A. One of them is A – 3 = R – 4 = C – 5

Find the other two alternating paths that start at A.

List the improved matching generated by using the alternating path A – 3 = R – 4 = C – 5.

Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path used and your final matching.

[The total weight of the network is 98 km] Figure 5 models a network of gas pipes that have to be inspected. The number on each arc represents the length, in km, of that pipe. A route of minimum length that traverses each pipe at least once and starts and finishes at A needs to be found.

Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.

Write down a possible shortest inspection route, giving its length.

It is now decided to start the inspection route at D. The route must still traverse each pipe at least once but may finish at any node.

Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route.

Figure 6 shows a network of cycle tracks. The number on each arc gives the length, in km, of that

Use Dijkstra’s algorithm to find the shortest route from A to H. State your shortest route and its length.

Explain how you determined your shortest route from your labelled diagram.

The track between E and F is now closed for resurfacing and cannot be used.

Find the shortest route from A to H and state its length.

A project is modelled by the activity network shown in Figure 7. 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.

Complete the precedence table in the answer book.

Complete Diagram 1 in the answer book, to show the early event times and late event times.

State the critical activities.

On the grid in your answer book, draw a cascade (Gantt) chart for this project.

By considering the activities that must take place between time 7 and time 16, explain why it is not possible to complete this project with just 3 workers in the minimum time.

A firm is planning to produce two types of radio, type A and type B. Market research suggests that, each week:

• At least 50 type A radios should be produced.

• The number of type A radios should be between 20% and 40% of the total number of radios produced.

Each type A radio requires 3 switches and each type B radio requires 2 switches. The firm can only buy 200 switches each week. The profit on each type A radio is £15. The profit on each type B radio is £12. The firm wishes to maximise its weekly profit. Formulate this situation as a linear programming problem, defining your variables.

4.