Questions D1 (899 questions)

Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 SPS SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
Edexcel D1 Q3
3. (a) Draw a graph with 6 vertices, each of degree 1 .
(b) Draw two graphs with 6 vertices, each of degree 2 such that:
  1. the graph is connected,
  2. the graph is not connected. A simple connected graph has 5 vertices each of degree \(x\).
    (c) Find the possible values of \(x\) and explain your answer.
    (d) For each value of \(x\) you found in part (c) draw a possible graph.
Edexcel D1 Q4
4. A company produces \(x _ { 1 }\) finished articles at the end of January, \(x _ { 2 }\) finished articles at the end of February, \(x _ { 3 }\) finished articles at the end of March, \(x _ { 4 }\) finished articles at the end of April. Other details for each month are as follows:
MonthJanuaryFebruaryMarchApril
Demand at end of month200350250200
Production costs per article£1000£1800£1600£1900
The cost of storing each finished but unsold article is \(\pounds 500\) per month. Thus, for example, any article unsold at the end of January would incur a \(\pounds 500\) charge if it is stored until the end of February or a \(\pounds 1000\) charge if it is stored until the end of March. There must be no unsold stock at the end of April.
The selling price of each article is \(\pounds 4000\) and the total profit ( \(\pounds P\) ) must be maximised.
  1. Rewrite \(x _ { 4 }\) in terms of the other 3 variables.
  2. Show that the total cost incurred \(( \pounds C )\) is given by: $$C = 600 x _ { 1 } + 900 x _ { 2 } + 200 x _ { 3 } + 1125000$$
  3. Hence, show that \(P = { } ^ { - } 600 x _ { 1 } - 900 x _ { 2 } - 200 x _ { 3 } + 2875000\).
  4. Three of the constraints operating can be expressed as \(x _ { 1 } \geq 200\), \(x _ { 2 } \geq 0\) and \(x _ { 3 } \geq 0\). Write down inequalities representing two further constraints.
    (2 marks)
  5. Explain why it is not appropriate to use a graphical method to solve this problem.
  6. An employee of the company wishes to use the Simplex algorithm to solve the problem. He tries to generate an initial tableau with \(x _ { 1 } , x _ { 2 }\) and \(x _ { 3 }\) as the non-basic variables. Explain why this is not appropriate and explain what he should do instead. You are not required to generate an initial tableau or to solve the problem.
    (2 marks)
Edexcel D1 Q5
5. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-05_956_1561_312_242} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} Figure 2 shows a weighted network representing the paths in a certain part of St. Andrews. The numbers on the arcs represent the lengths of the paths in metres.
  1. Use Dijkstra's algorithm to find a route of minimum length from \(P\) to \(F\). You do not need to consider routes via vertex \(Q\). You must show clearly:
    1. the order in which you labelled the vertices,
    2. how you found a route of minimum length from your labelling. Each night a security guard walks along each of the paths in Figure 2 at least once.
  2. The security office is at vertex \(A\), so she must start and finish her inspection at \(A\). Find the minimum distance that she must walk each night.
    (4 marks)
Edexcel D1 Q6
6. This question should be answered on the sheet provided. A town has adopted a one-way system to cope with recent problems associated with congestion in one area. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-06_670_1301_459_331} \captionsetup{labelformat=empty} \caption{Fig. 3}
\end{figure} Figure 3 models the one-way system as a capacitated directed network. The numbers on the arcs are proportional to the number of vehicles that can pass along each road in a given period of time.
  1. Find the capacity of the cut which passes through the \(\operatorname { arcs } A E , B F , B G\) and \(C D\).
    (2 marks) \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-07_659_1278_196_335} \captionsetup{labelformat=empty} \caption{Fig. 4}
    \end{figure} Figure 4 shows a feasible flow of 17 through the same network. For convenience, a supersource, \(S\), and a supersink, \(T\), have been used.
    1. Use the labelling procedure to find the maximum flow through this network. You must list each flow-augmenting route you use together with its flow.
    2. Show your maximum flow pattern and state its value.
  2. Prove that your flow is the maximum possible through the network.
  3. It is suggested that the maximum flow through the network could be increased by making road \(E F\) undirected, so that it has a capacity of 8 in either direction. Using the maximum flow-minimum cut theorem, find the increase in maximum flow this change would allow.
    (2 marks)
  4. An alternative suggestion is to widen a single road in order to increase its capacity. Which road, on its own, could lead to the biggest improvement, and what would be the largest maximum flow this could achieve.
    (2 marks)
Edexcel D1 Q7
7. A project involves six tasks, some of which cannot be started until others have been completed. This is shown in the table below. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-09_2036_1555_349_248}
  1. \(\_\_\_\_\)
  2. \(\_\_\_\_\)
    \section*{Sheet for answering question 5} NAME \section*{Please hand this sheet in for marking} Sheet for answering question 6
    NAME \section*{Please hand this sheet in for marking}

    1. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-11_666_1280_461_374}

    2. \includegraphics[max width=\textwidth, alt={}, center]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-11_657_1276_1356_376} Maximum Flow = \(\_\_\_\_\)
  3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
  4. \(\_\_\_\_\)
  5. \(\_\_\_\_\)
Edexcel D1 Q1
  1. (a) Use the binary search algorithm to locate the name PENICUIK in the following list.
\begin{displayquote} ANKERDINE CULROSS DUNOON ELGIN FORFAR FORT WILLIAM HADDINGTON KINCARDINE LARGS MALLAIG MONTROSE PENICUIK ST. ANDREWS THURSO
(b) Use the same algorithm to attempt to locate PENDINE.
(c) Explain the purpose of the mid-point in dividing up the ordered list when using this algorithm. \end{displayquote}
Edexcel D1 Q2
  1. The following lengths of cloth (in metres) are to be cut from standard 24 metre rolls.
$$\begin{array} { l l l l l l l l l l l l } 6 & 6 & 4 & 6 & 8 & 8 & 4 & 12 & 14 & 6 & 14 & 8 \end{array}$$
  1. Considering only the total amount, what is the least number of rolls that are needed?
  2. Using the first-fit decreasing algorithm, show that the lengths could be cut from 5 rolls.
  3. Using "full-bin" combinations show that it is possible to cut these lengths from the number of rolls found in part (a).
  4. Comment on this result.
Edexcel D1 Q3
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.
TraineePreferences
\(P\)Dundee, London (either)
\(Q\)Dundee, Edinburgh, Glasgow
\(R\)Glasgow, London (Head Office only)
SEdinburgh
\(T\)Edinburgh
  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
Edexcel D1 Q4
4. The following matrix gives the capacities of the pipes in a system.
To FromS\(T\)A\(B\)\(C\)D
S--1626--
T------
A----135
B-16---11
C-11----
D-11----
  1. Represent this information as a digraph.
  2. Find the minimum cut, expressing it in the form \(\{ \} \mid \{ \}\), and state its value.
  3. Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow.
  4. Explain how you know that this flow is maximal.
Edexcel D1 Q5
5. This question should be answered on the sheet provided. An algorithm is described by the flow chart shown in Figure 1 below. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1e518ab0-9852-4d1d-a4c9-344a5edf9547-05_1337_937_388_404} \captionsetup{labelformat=empty} \caption{Fig. 1}
\end{figure}
  1. Complete the table on the answer sheet recording the results of each instruction as the algorithm is applied and state the final output.
  2. Explain what the algorithm achieves.
  3. Attempt to apply the algorithm again, with the initial value of \(a\), as specified in Box 2, changed to 5 . Explain what happens.
    (2 mark)
  4. Find the set of positive initial values of \(a\) for which the algorithm will work.
    (2 marks)
Edexcel D1 Q6
6. The manager of a new leisure complex needs to maximise the Revenue \(( \pounds R )\) from providing the following two weekend programmes.
\(\frac { \text { Participants } } { \text { Children } }\)7 hours windsurfing, 2 hours sailing\(\frac { \text { Revenue } } { \pounds 50 }\)
Adults5 hours windsurfing, 6 hours sailing\(\pounds 100\)
The following restrictions apply to each weekend.
No more than 90 participants can be accommodated.
There must be at most 40 adults.
A maximum of 600 person-hours of windsurfing can be offered.
A maximum of 300 person-hours of sailing can be offered.
  1. Formulate the above information as a linear programming problem, listing the constraints as inequalities and stating the objective function \(R\).
  2. On graph paper, illustrate the constraints, indicating clearly the feasible region.
  3. Solve the problem graphically, stating how many adults and how many children should be accepted each weekend and what the revenue will be. The manager is considering buying more windsurfing equipment at a cost of \(\pounds 2000\). This would increase windsurfing provision by \(10 \%\).
  4. State, with a reason, whether such a purchase would be cost effective.
Edexcel D1 Q7
7. This question should be answered on the sheet provided. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1e518ab0-9852-4d1d-a4c9-344a5edf9547-07_576_1360_331_278} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure} Figure 2 shows an activity network modelling the tasks involved in widening a bridge over the B451. The arcs represent the tasks and the numbers in brackets gives the time, in days, to complete each task.
  1. Find the early and late times for each event.
  2. Determine those activities which lie on the critical path and list them in order.
  3. State the minimum length of time needed to widen the bridge. Each task needs a single worker.
  4. Show that two men would not be sufficient to widen the bridge in the shortest time.
    (2 marks)
  5. Draw up a schedule showing how 3 men could complete the project in the shortest time. \section*{Please hand this sheet in for marking}
  6. Complete matching:
    \(P\)\(\bullet\)\(\bullet\)\(D\)
    \(Q\)\(\bullet\)\(\bullet\)\(G\)
    \(R\)\(\bullet\)\(\bullet\)\(E\)
    \(S\)\(\bullet\)\(\bullet\)\(L ( H )\)
    \(T\)\(\bullet\)\(\bullet\)\(L\)
    \section*{Please hand this sheet in for marking}
  7. \(x\)\(a\)\(b\)\(( a - b ) < 0.01\) ?
    1005026No
    -2614.923No
    Final output
  8. \(\_\_\_\_\)
  9. \(x\)\(a\)\(b\)\(( a - b ) < 0.01 ?\)
    100
  10. \(\_\_\_\_\)
    \section*{Please hand this sheet in for marking}

  11. \includegraphics[max width=\textwidth, alt={}, center]{1e518ab0-9852-4d1d-a4c9-344a5edf9547-11_768_1689_427_221}
  12. \(\_\_\_\_\)
  13. \(\_\_\_\_\)
  14. 051015202530354045505560
    Worker 1
    Worker 2
  15. 051015202530354045505560
    Worker 1
    Worker 2
    Worker 3
Edexcel D1 2015 January Q1
1.
ABCDEFGH
A-981317111210
B9-11211524137
C811-2023171715
D132120-15281118
E17152315-312330
F1124172831-1315
G121317112313-23
H1071518301523-
The table represents a network that shows the time taken, in minutes, to travel by car between eight villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H .
  1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form your tree in the order in which you select them.
  2. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree.
  3. State whether your minimum spanning tree is unique. Justify your answer.
Edexcel D1 2015 January Q2
2. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{00abfcc0-63b3-4784-a4b5-06aba234068c-3_616_561_278_356} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{00abfcc0-63b3-4784-a4b5-06aba234068c-3_606_552_285_1146} \captionsetup{labelformat=empty} \caption{Figure 2}
\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)
Edexcel D1 2015 January Q3
3. $$\begin{array} { l l l l l l l l l l } 1.1 & 0.7 & 1.9 & 0.9 & 2.1 & 0.2 & 2.3 & 0.4 & 0.5 & 1.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 3 The list is to be sorted into descending order.
    1. Starting at the left-hand end of the list, perform one pass through the list using a bubble sort. Write down the list that results at the end of your first pass.
    2. Write down the number of comparisons and the number of swaps performed during your first pass. After a second pass using this bubble sort, the updated list is $$\begin{array} { l l l l l l l l l l } 1.9 & 1.1 & 2.1 & 0.9 & 2.3 & 0.7 & 0.5 & 1.7 & 0.4 & 0.2 \end{array}$$
  2. Use a quick sort on this updated list to obtain the fully sorted list. You must make your pivots clear.
  3. Apply the first-fit decreasing bin packing algorithm to your fully sorted list to pack the numbers into bins of size 3
Edexcel D1 2015 January Q4
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{00abfcc0-63b3-4784-a4b5-06aba234068c-5_889_1591_258_239} \captionsetup{labelformat=empty} \caption{Figure 3
[0pt] [The total weight of the network is 100]}
\end{figure} Figure 3 represents a network of pipes in a building. The number on each arc represents the length, in metres, of the corresponding pipe.
  1. Use Dijkstra's algorithm to find the shortest path from A to J . State your path and its length. On a particular day Kim needs to check each pipe. A route of minimum length, which traverses each pipe at least once and starts and finishes at A, needs to be found.
  2. Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.
  3. Write down a possible route, giving its length. All the pipes directly attached to B are removed. Kim needs to check all the remaining pipes and may now start at any vertex and finish at any vertex. A route is required that excludes all those pipes directly attached to B .
  4. State all possible combinations of starting and finishing points so that the length of Kim's route is minimised. State the length of Kim's route.
Edexcel D1 2015 January Q5
5.
ActivityImmediately preceding activities
A-
B-
CA
DA
EA, B
FC
GC, D
HE
IE
JH, I
KF, G
  1. Draw the activity network described in the precedence table, using activity on arc. Your activity network must contain only the minimum number of dummies.
    (5)
  2. Explain why, in general, dummies may be required in an activity network.
Edexcel D1 2015 January Q6
6. Jonathan is going to make hats to sell at a fete. He can make red hats and green hats. Jonathan can use linear programming to determine the number of each colour of hat that he should make. Let \(x\) be the number of red hats he makes and \(y\) be the number of green hats he makes.
One of the constraints is that there must be at least 30 hats.
  1. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint. Two further constraints are $$\begin{aligned} & 2 y + x \geqslant 40
    & 2 y - x \geqslant - 30 \end{aligned}$$
  2. Write down two more constraints which apply.
  3. Represent all these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region R . The cost of making a green hat is three times the cost of making a red hat. Jonathan wishes to minimise the total cost.
  4. Use the objective line (ruler) method to determine the number of red hats and number of green hats that Jonathan should make. You must clearly draw and label your objective line. Given that the minimum total cost of making the hats is \(\pounds 107.50\)
  5. determine the cost of making one green hat and the cost of making one red hat. You must make your method clear.
Edexcel D1 2015 January Q7
7. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{00abfcc0-63b3-4784-a4b5-06aba234068c-8_980_1577_229_268} \captionsetup{labelformat=empty} \caption{Figure 4
[0pt] [The sum of all the activity durations is 99 days]}
\end{figure} The network in Figure 4 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration of the activity, in days, is shown in brackets. The early event times and late event times are to be shown at each vertex and some have been completed for you. Given that activity F is a critical activity and that the total float on activity G is 2 days,
  1. write down the value of \(x\) and the value of \(y\),
  2. calculate the missing early event times and late event times and hence complete Diagram 1 in your answer book. Each activity requires one worker and the project must be completed in the shortest possible time.
  3. Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time.
  4. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
  5. Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to times and activities. (You do not need to provide a schedule of the activities.)
Edexcel D1 2016 January Q1
1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a3ca2743-2311-4225-8b78-dcd5eb592704-2_741_558_370_372} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a3ca2743-2311-4225-8b78-dcd5eb592704-2_734_561_374_1114} \captionsetup{labelformat=empty} \caption{Figure 2}
\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.
Edexcel D1 2016 January Q2
2. Kruskal's algorithm finds a minimum spanning tree for a connected graph with \(n\) vertices.
  1. Explain the terms
    1. connected graph,
    2. tree,
    3. spanning tree.
  2. Write down, in terms of \(n\), the number of arcs in the minimum spanning tree. The table below shows the lengths, in km, of a network of roads between seven villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G .
    ABCDEFG
    A-17-1930--
    B17-2123---
    C-21-27293122
    D192327--40-
    E30-29--3325
    F--314033-39
    G--22-2539-
  3. Complete the drawing of the network on Diagram 1 in the answer book by adding the necessary arcs from vertex C together with their weights.
  4. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
  5. State the weight of the minimum spanning tree.
Edexcel D1 2016 January Q3
3.
6.4
7.9
8.1
12.19 .3
14.0
15.7
17.4
20.1
  1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 33 The list is to be sorted into descending order.
    1. 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.
    2. Write down the total number of comparisons and the total number of swaps performed during your two passes.
  2. Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear.
  3. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33
  4. Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer.
Edexcel D1 2016 January Q4
4. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a3ca2743-2311-4225-8b78-dcd5eb592704-5_926_1479_219_296} \captionsetup{labelformat=empty} \caption{Figure 3}
\end{figure} [The total weight of the network is 196]
Figure 3 models a network of roads. The number on each edge gives the time, in minutes, taken to travel along that road. Oliver wishes to travel by road from A to K as quickly as possible.
  1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to K . State the quickest route.
    (6) On a particular day Oliver must travel from B to K via A.
  2. Find a route of minimal time from B to K that includes A , and state its length.
    (2) Oliver needs to travel along each road to check that it is in good repair. He wishes to minimise the total time required to traverse the network.
  3. Use the route inspection algorithm to find the shortest time needed. You must state all combinations of edges that Oliver could repeat, making your method and working clear.
Edexcel D1 2016 January Q5
5. A linear programming problem in \(x\) and \(y\) is described as follows. $$\begin{array} { l l } \text { Maximise } & \mathrm { P } = 5 x + 3 y
\text { subject to: } & x \geqslant 3
& x + y \leqslant 9
& 15 x + 22 y \leqslant 165
& 26 x - 50 y \leqslant 325 \end{array}$$
  1. Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence determine the feasible region and label it R .
  2. Use the objective line method to find the optimal vertex, V, of the feasible region. You must draw and label your objective line and label vertex V clearly.
  3. Calculate the exact coordinates of vertex V and hence calculate the corresponding value of P at V . The objective is now to minimise \(5 x + 3 y\), where \(x\) and \(y\) are integers.
  4. Write down the minimum value of \(5 x + 3 y\) and the corresponding value of \(x\) and corresponding value of \(y\).
Edexcel D1 2016 January Q6
6. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a3ca2743-2311-4225-8b78-dcd5eb592704-7_664_1520_239_276} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} A project is modelled by the activity network shown in Figure 4. The activities are represented by the arcs. The number in brackets on each arc gives the time required, in hours, to complete the activity. The numbers in circles are the event numbers. Each activity requires one worker.
  1. Explain the significance of the dummy activity
    1. from event 5 to event 6
    2. from event 7 to event 9
  2. Complete Diagram 1 in the answer book to show the early event times and the late event times.
  3. State the minimum project completion time.
  4. Calculate a lower bound for the minimum number of workers required to complete the project in the minimum time. You must show your working.
  5. On Grid 1 in your answer book, draw a cascade (Gantt) chart for this project.
  6. On Grid 2 in your answer book, construct a scheduling diagram to show that this project can be completed with three workers in just one more hour than the minimum project completion time.
    (3)