13
16
5
8
2
15
12
10
6.
\includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-558_2226_1632_322_157}
\section*{Diagram 1}
- (a) (i) \(\_\_\_\_\)
(ii) \(\_\_\_\_\)
(b)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-562_1214_1239_753_349}
(c) \(\_\_\_\_\)
(d) \(\_\_\_\_\)
The table 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.
(a) Complete the drawing of the network in Diagram 1 of the answer book by adding the necessary arcs from vertex D together with their weights.
(b) 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.
(c) Draw the minimum spanning tree using the vertices provided in Diagram 2 in the answer book.
(d) State the weight of the minimum spanning tree.
4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-569_661_1525_292_269}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
\section*{[The total weight of the network is 1436 m ]}
(a) Explain the term valency.
Figure 3 models a system of underground pipes. The number on each arc represents the length, in metres, of that pipe.
Pressure readings indicate that there is a leak in the system and an electronic device is to be used to inspect the system to locate the leak. The device will start and finish at A and travel along each pipe at least once. The length of this inspection route needs to be minimised.
(b) Use the route inspection algorithm to find the pipes that will need to be traversed twice. You should make your method and working clear.
(c) Find the length of the inspection route.
Pipe HI is now found to be blocked; it is sealed and will not be replaced. An inspection route is now required that excludes pipe HI . The length of the inspection route must be minimised.
(d) Find the length of the minimum inspection route excluding HI. Justify your answer.
(e) Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI.
5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-570_785_1463_191_301}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
Figure 4 shows a network of roads. The number on each arc represents the length, in miles, of the corresponding road.
(a) Use Dijkstra's algorithm to find the shortest route from S to T . State your shortest route and its length.
(6)
(b) Explain how you determined your shortest route from your labelled diagram.
(2)
Due to flooding, the roads in and out of D are closed.
(c) Find the shortest route from S to T avoiding D . State your shortest route and its length.
(2)
6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-571_624_1461_194_301}
\captionsetup{labelformat=empty}
\caption{Figure 5}
\end{figure}
Figure 5 is the activity network relating to a development project. 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.
(a) Complete the precedence table in the answer book.
(2)
(b) Complete Diagram 1 in the answer book to show the early event times and late event times.
(4)
(c) Calculate the total float for activity E. You must make the numbers you use in your calculation clear.
(2)
(d) Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
(2)
(e) Schedule the activities using the minimum number of workers so that the project is completed in the minimum time.
7.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-572_2491_1570_175_299}
\captionsetup{labelformat=empty}
\caption{Figure 6}
\end{figure}
A company is going to hire out two types of car, standard and luxury.
Let \(x\) be the number of standard cars it should buy.
Let \(y\) be the number of luxury cars it should buy.
Figure 6 shows three constraints, other than \(x , y \geqslant 0\)
Two of these are \(x \geqslant 20\) and \(y \geqslant 8\)
(a) Write, as an inequality, the third constraint shown in Figure 6.
The company decides that at least \(\frac { 1 } { 6 }\) of the cars must be luxury cars.
(b) Express this information as an inequality and show that it simplifies to
$$5 y \geqslant x$$
You must make the steps in your working clear.
Each time the cars are hired they need to be prepared. It takes 5 hours to prepare a standard car and it takes 6 hours to prepare a luxury car. There are 300 hours available each week to prepare the cars.
(c) Express this information as an inequality.
(d) Add two lines and shading to Diagram 1 in the answer book to illustrate the constraints found in parts (b) and (c).
(e) Hence determine the feasible region and label it R .
The company expects to make \(\pounds 80\) profit per week on each car.
It therefore wishes to maximise \(\mathrm { P } = 80 x + 80 y\), where P is the profit per week.
(f) Use the objective line (ruler) method to find the optimal vertex, V, of the feasible region. You must clearly draw and label your objective line and the vertex V.
(g) Given that P is the expected profit, in pounds, per week, find the number of each type of car that the company should buy and the maximum expected profit.
(a)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-579_545_1422_890_258}
\section*{Diagram 1}
(b)
(c)
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-580_561_1431_1201_255}
\captionsetup{labelformat=empty}
\caption{Diagram 2}
\end{figure}
(d) Weight of minimum spanning tree
4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-581_672_1520_219_212}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
5.
\includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-583_878_1602_230_173}
Key:
Paper Reference(s)
6689/01
Edexcel GCE
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-598_130_311_471_1641}
\(\stackrel { A } { \bullet } \stackrel { \text { B } } { \bullet }\)
F•
$$\mathrm { C }$$
\(\stackrel { \mathrm { E } } { \ominus } \stackrel { \text { D } } { \bullet }\)
\section*{Diagram 1}
3.
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-628_1302_1579_293_184}
\section*{Diagram 1}
\includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-629_1027_1600_1539_169}
Diagram 2
(Total 12 marks)
4.
S J H A C K P L T L
5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-632_693_1497_292_233}
\captionsetup{labelformat=empty}
\caption{Figure 4
[0pt]
[The total weight of the network is 181 miles]}
\end{figure}
6.
Leave blank
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-636_2368_1301_294_440}
8.
\includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-639_1116_1123_317_447}
\section*{Diagram 1}
\section*{Decision Mathematics D1
Advanced/Advanced Subsidiary }
\section*{Friday 17 May 2013 - Morning
Time: 1 hour 30 minutes}
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 or symbolic differentiation/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 7 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 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-641_766_570_324_342}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-641_755_570_331_1146}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Figure 1 shows the possible allocations of six people, Alex (A), Ben (B), Harriet (H), Izzy (I), Leo (L) and Rowan (R), to six tasks, \(1,2,3,4,5\) and 6.
(a) Write down the technical name given to the type of diagram shown in Figure 1.
Figure 2 shows an initial matching.
(b) Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use, and state your improved matching after each iteration.
(6)
2.
0.6
0.2
0.4
0.5
0.7
0.1
0.9
0.3
1.5
1.6
(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 2.
(3)
(b) The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You must make your pivots clear.
(c) Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 2 .
(d) Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.
3.
Order of arcs:
(b)
A
D
C
Diagram 1
(c)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-655_652_536_415_230}
D
\section*{Diagram 2}
(d) \(\_\_\_\_\)
(e) Minimum time needed: \(\_\_\_\_\)
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-656_2632_1829_121_118}
(b)
Shortest path from S to T:
Length of shortest path from S to T:
Shortest path from S to T via \(\mathbf { F }\) :
Length of shortest path from S to T via \(\mathbf { F }\) :
5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-658_823_1541_283_205}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
[The total weight of the network is 344 miles]
6.
\includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-661_1493_1294_319_328}
\section*{Diagram 1}
\includegraphics[max width=\textwidth, alt={}, center]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-662_1271_1549_223_201}
\section*{Diagram 1}
(b) \(\_\_\_\_\)
(c) \(\_\_\_\_\)
(d) \(\_\_\_\_\)
\includegraphics[max width=\textwidth, alt={}]{12f9ae59-b2ff-4a03-9ac9-c61dbaf8c9f5-663_2632_1830_121_121}
\section*{Pearson Edexcel International Advanced Level Decision Mathematics D1}
Advanced/Advanced Subsidiary
\section*{You must have:}
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.
\section*{Instructions}
- Use black ink or ball-point pen.
- If pencil is used for diagrams/sketches/graphs it must be dark (HB or B). Coloured pencils and highlighter pens must not be used.
- Fill in the boxes on the top of the answer book with your name, centre number and candidate number.
- Answer all questions and ensure that your answers to parts of questions are clearly labelled.
- Answer the questions in the D1 answer book provided - there may be more space than you need.
- You should show sufficient working to make your methods clear. Answers without working may not gain full credit.
- 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.
\section*{Information}
- The total mark for this paper is 75.
- The marks for each question are shown in brackets
- use this as a guide as to how much time to spend on each question.
\section*{Advice}
- Read each question carefully before you start to answer it.
- Try to answer every question.
- Check your answers if you have time at the end.
\section*{Write your answers in the D1 answer book for this paper.}
1.
11
17
10