10
The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .
- Calculate a lower bound for the number of rolls needed.
(2) - Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
- Use full bins to find an optimal solution that uses the minimum number of rolls.
3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-415_755_627_283_285}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-415_748_618_287_1153}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Figure 1 shows the possible allocations of six workers, Charlotte (C), Eleanor (E), Harry (H), Matt (M), Rachel (R) and Simon (S) to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 2 shows an initial matching. - List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
- Explain why it is not possible to find a complete matching.
Simon (S) now has task 3 added to his possible allocation.
- Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating path you use and your complete matching.
(3)
4.
Miri
Jessie
Edward
Katie
Hegg
Beth
Louis
Philip
Natsuko
Dylan - Use the quick sort algorithm to sort the above list into alphabetical order.
(5) - Use the binary search algorithm to locate the name Louis.
5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-417_938_1408_264_324}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
[The total weight of the network is 625 m ]
Figure 3 models a network of paths in a park. The number on each arc represents the length, in m , of that path.
Rob needs to travel along each path to inspect the surface. He wants to minimise the length of his route. - Use the route inspection algorithm to find the length of his route. State the arcs that should be repeated. You should make your method and working clear.
(6)
The surface on each path is to be renewed. A machine will be hired to do this task and driven along each path.
The machine will be delivered to point G and will start from there, but it may be collected from any point once the task is complete. - Given that each path must be traversed at least once, determine the finishing point so that the length of the route is minimised. Give a reason for your answer and state the length of your route.
(3)
6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-418_903_1493_260_278}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
Figure 4 represents a network of roads. The number on each arc gives the length, in km, of that road. - Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
(6) - State the shortest distance from A to G.
(1)
7. Rose makes hanging baskets which she sells at her local market. She makes two types, large and small. Rose makes \(x\) large baskets and \(y\) small baskets.
Each large basket costs \(\pounds 7\) to make and each small basket costs \(\pounds 5\) to make. Rose has \(\pounds 350\) she can spend on making the baskets. - Write down an inequality, in terms of \(x\) and \(y\), to model this constraint.
(2)
Two further constraints are
$$\begin{aligned}
& y \leqslant 20 \text { and }
& y \leqslant 4 x
\end{aligned}$$ - Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
- On the grid provided, show these three constraints and \(x \geqslant 0 , y \geqslant 0\). Hence label the feasible region, R.
Rose makes a profit of \(\pounds 2\) on each large basket and \(\pounds 3\) on each small basket. Rose wishes to maximise her profit, £P.
- Write down the objective function.
- Use your graph to determine the optimal numbers of large and small baskets Rose should make, and state the optimal profit.
8.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-420_812_1541_278_262}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{figure}
A construction project is modelled by the activity network shown in Figure 5. 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 Diagram 2 in the answer book, showing the early and late event times.
- State the critical activities.
- Find the total float for activities M and H . You must make the numbers you use in your calculations clear.
- On the grid provided, draw a cascade (Gantt) chart for this project.
An inspector visits the project at 1 pm on days 16 and 31 to check the progress of the work.
- Given that the project is on schedule, which activities must be happening on each of these days?
- \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-422_632_896_1742_523}
\captionsetup{labelformat=empty}
\caption{Diagram 1}
\end{figure} - Total weight of tree \(\_\_\_\_\)
2. \(\_\_\_\_\)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-423_108_61_2627_1884}
3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-424_746_601_255_242}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-424_739_599_260_1103}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
(Question 3 continued)
C
E • • 2
H • • 3
M • • 4
R • • 5
S • • 6
4. \(\_\_\_\_\)
(Question 4 continued)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-427_133_40_2622_1877}
5. \(\_\_\_\_\)
(Question 5 continued)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-430_2633_1831_118_118}
7. \(\_\_\_\_\)
\section*{(Question 7 continued)}
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-432_1616_1637_278_148}
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-433_2296_1347_435_182}
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-434_2382_1559_127_194}
(Total 15 marks)
\section*{Decision Mathematics D1
Advanced/Advanced Subsidiary }
Candidates may use any calculator allowed by the regulations of the Joint Council for Qualifications. Calculators must not have the facility for symbolic algebra manipulation, differentiation and integration, or have retrievable mathematical formulae stored in them.
Write your answers for this paper in the D1 answer book provided.
In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
When a calculator is used, the answer should be given to an appropriate degree of accuracy.
Complete your answers in blue or black ink or pencil.
Do not return the question paper with the answer book.
Full marks may be obtained for answers to ALL questions.
The marks for individual questions and the parts of questions are shown in round brackets: e.g. (2). There are 7 questions in this question paper. The total mark for this paper is 75.
There are 8 pages in this question paper. The answer book has 16 pages. Any blank pages are indicated.
You must ensure that your answers to parts of questions are clearly labelled.
You should show sufficient working to make your methods clear to the Examiner.
Answers without working may not gain full credit.
\section*{Write your answers in the D1 answer book for this paper.}
1.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-436_611_636_356_719}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Figure 1 shows the possible allocation of six people, Alice (A), Brian (B), Christine (C), David (D), Elizabeth (E) and Freddy (F), to six tasks, 1, 2, 3, 4, 5 and 6.
An initial matching is Alice to task 1, Christine to task 3, David to task 4 and Elizabeth to task 5. - Show this initial matching on Diagram 1 in the answer book.
(1) - Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths that you use, and give your final matching.
(5)
2. Prim's algorithm finds a minimum spanning tree for a connected graph. - Explain the terms
- connected graph,
- tree,
- spanning tree.
- Name an alternative algorithm for finding a minimum spanning tree.
\begin{table}[h]
- \(\_\_\_\_\)
- \(\_\_\_\_\)
6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-453_614_1315_255_374}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{figure} - \(\_\_\_\_\)
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{(b)}
| Event | Immediately preceding activity |
| A | - |
| B | - |
| C | |
| D | |
| E | |
| F | |
| G | |
| H | |
\captionsetup{labelformat=empty}
\caption{(c)}
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-454_2222_1161_356_330}
\end{figure}
7.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{(Question 7 continued)}
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-457_927_1315_365_315}
\end{figure}
\section*{6689/01 Edexcel GCE}
\section*{Decision Mathematics D1 Advanced/Advanced Subsidiary}
\section*{Thursday 27 May 2010 - Morning}
Materials required for examination
Nil
Items included with question papers
D1 Answer Book
Candidates may use any calculator allowed by the regulations of the Joint Council for Qualifications. Calculators must not have the facility for symbolic algebra manipulation, differentiation and integration, or have retrievable mathematical formulae stored in them.
Write your answers for this paper in the D1 answer book provided.
In the boxes on the answer book, write your centre number, candidate number, your surname, initials and signature.
Check that you have the correct question paper.
Answer ALL the questions.
When a calculator is used, the answer should be given to an appropriate degree of accuracy.
Do not return the question paper with the answer book.
Full marks may be obtained for answers to ALL questions.
The marks for individual questions and the parts of questions are shown in round brackets: e.g. (2). There are 8 questions in this question paper. The total mark for this paper is 75 .
There are 12 pages in this question paper. The answer book has 20 pages. Any blank pages are indicated.
You must ensure that your answers to parts of questions are clearly labelled.
You should show sufficient working to make your methods clear to the Examiner.
Answers without working may not gain full credit.
1.
\section*{-}
\section*{Q}
LO
2.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-471_753_1216_223_361}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure} - Paper Reference(s)
6689/01
Edexcel GCE
Decision Mathematics D1
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-493_130_311_471_1641}
\(\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}\)
\(\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}\)
3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-498_993_1262_262_331}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure} - \(\_\_\_\_\)
D
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{B}
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-499_204_435_1567_961}
\end{figure}
\begin{verbatim}
G
\end{verbatim}
A •
\section*{Diagram 1}
Weight of minimum spanning tree: \(\_\_\_\_\)- \(\_\_\_\_\)
4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-500_742_604_296_223}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-500_734_590_301_1096}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-501_744_604_294_221}
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-501_739_592_296_1094}
5.
6.
\includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-504_1226_1591_278_178}
\section*{Graph 1}
- (a)
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.
- Use the binary search algorithm to locate the name Kim in the list you obtained in (b). You must make your method clear.
2.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-510_858_1169_244_447}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure} - Define the terms
- tree,
- minimum spanning tree.
(3)
- 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.
(3) - 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.
(1)
3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-511_1492_1298_210_379}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
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\).
4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-512_623_577_287_383}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-512_620_582_287_1098}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
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 \(\mathrm { A } - 3 = \mathrm { R } - 4 = \mathrm { 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.
5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-513_835_913_219_575}
\captionsetup{labelformat=empty}
\caption{Figure 5
[0pt]
[The total weight of the network is 98 km ]}
\end{figure}
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.
6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-514_825_1379_226_342}
\captionsetup{labelformat=empty}
\caption{Figure 6}
\end{figure}
Figure 6 shows a network of cycle tracks. The number on each arc gives the length, in km, of that track. - 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.
(2)
7.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-515_798_1497_258_283}
\captionsetup{labelformat=empty}
\caption{Figure 7}
\end{figure}
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.
(3) - 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.
8. 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 \(\pounds 15\).
The profit on each type B radio is \(\pounds 12\).
The firm wishes to maximise its weekly profit.
Formulate this situation as a linear programming problem, defining your variables.
(Total 7 marks)