Questions D1 (899 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure 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 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 Mechanics 1 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pure 1 S1 S2 S3 S4 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 Stats 1 Unit 1 Unit 2 Unit 3 Unit 4
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
AQA D1 2006 June Q1
1 Five people, \(A , B , C , D\) and \(E\), are to be matched to five tasks, 1, 2, 3, 4 and 5. The table shows which tasks each person can do.
PersonTasks
\(A\)\(1,3,5\)
\(B\)2,4
\(C\)2
\(D\)4,5
\(E\)3,5
  1. Show this information on a bipartite graph.
  2. Initially \(A\) is matched to task 3, \(B\) to task 4, \(C\) to task 2 and \(E\) to task 5 . Use an alternating path from this initial matching to find a complete matching.
AQA D1 2006 June Q2
2
  1. Use a shuttle sort to rearrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 18 & 2 & 12 & 7 & 26 & 19 & 16 & 24 \end{array}$$
  2. State the number of comparisons and swaps (exchanges) for each of the first three passes.
AQA D1 2006 June Q3
3 [Figure 1, printed on the insert, is provided for use in part (b) of this question.]
The diagram shows a network of roads. The number on each edge is the length, in kilometres, of the road.
\includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-03_716_1303_559_388}
    1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
    2. State the length of your minimum spanning tree.
    1. Use Dijkstra's algorithm on Figure 1 to find the shortest distance from \(A\) to \(J\).
    2. A new road, of length \(x \mathrm {~km}\), is built connecting \(I\) to \(J\). The minimum distance from \(A\) to \(J\) is reduced by using this new road. Find, and solve, an inequality for \(x\).
AQA D1 2006 June Q4
4 The diagram shows a network of roads connecting 6 villages. The number on each edge is the length, in miles, of the road.
\includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-04_670_1298_466_356} Total length of the roads \(= 164\) miles
  1. A police patrol car based at village \(A\) has to travel along each road at least once before returning to \(A\). Find the length of an optimal 'Chinese postman' route for the police patrol car.
  2. A council worker starts from \(A\) and travels along each road at least once before finishing at \(C\). Find the length of an optimal route for the council worker.
  3. A politician is to travel along all the roads at least once. He can start his journey at any village and can finish his journey at any village.
    1. Find the length of an optimal route for the politician.
    2. State the vertices from which the politician could start in order to achieve this optimal route.
AQA D1 2006 June Q5
5 [Figure 2, printed on the insert, is provided for use in this question.]
  1. Gill is solving a travelling salesperson problem.
    1. She finds the following upper bounds: 7.5, 8, 7, 7.5, 8.5. Write down the best upper bound.
    2. She finds the following lower bounds: \(6.5,7,6.5,5,7\). Write down the best lower bound.
  2. George is travelling by plane to a number of cities. He is to start at \(F\) and visit each of the other cities at least once before returning to \(F\). The diagram shows the times of flights, in hours, between cities. Where no time is shown, there is no direct flight available.
    \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-05_936_826_1162_589}
    1. Complete Figure 2 to show the minimum times to travel between all pairs of cities.
    2. Find an upper bound for the minimum total flying time by using the route FTPOMF.
    3. Using the nearest neighbour algorithm starting from \(F\), find an upper bound for the minimum total flying time.
    4. By deleting \(F\), find a lower bound for the minimum total flying time.
AQA D1 2006 June Q6
6 [Figure 3, printed on the insert, is provided for use in this question.]
Ernesto is to plant a garden with two types of tree: palms and conifers.
He is to plant at least 10, but not more than 80 palms.
He is to plant at least 5 , but not more than 40 conifers.
He cannot plant more than 100 trees in total. Each palm needs 20 litres of water each day and each conifer needs 60 litres of water each day. There are 3000 litres of water available each day. Ernesto makes a profit of \(\pounds 2\) on each palm and \(\pounds 1\) on each conifer that he plants and he wishes to maximise his profit. Ernesto plants \(x\) palms and \(y\) conifers.
  1. Formulate Ernesto's situation as a linear programming problem.
  2. On Figure 3, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of the objective line.
  3. Find the maximum profit for Ernesto.
  4. Ernesto introduces a new pricing structure in which he makes a profit of \(\pounds 1\) on each palm and \(\pounds 4\) on each conifer. Find Ernesto's new maximum profit and the number of each type of tree that he should plant to obtain this maximum profit.
AQA D1 2006 June Q7
7 A connected graph \(\mathbf { G }\) has \(m\) vertices and \(n\) edges.
    1. Write down the number of edges in a minimum spanning tree of \(\mathbf { G }\).
    2. Hence write down an inequality relating \(m\) and \(n\).
  2. The graph \(\mathbf { G }\) contains a Hamiltonian cycle. Write down the number of edges in this cycle.
  3. In the case where \(\mathbf { G }\) is Eulerian, draw a graph of \(\mathbf { G }\) for which \(m = 6\) and \(n = 12\).
AQA D1 2007 June Q1
1 Six people, \(A , B , C , D , E\) and \(F\), are to be matched to six tasks, \(1,2,3,4,5\) and 6 . The following adjacency matrix shows the possible matching of people to tasks.
Task 1Task 2Task 3Task 4Task 5Task 6
A010100
B101010
\(\boldsymbol { C }\)001011
D000100
E010001
\(\boldsymbol { F }\)000110
  1. Show this information on a bipartite graph.
  2. At first \(F\) insists on being matched to task 4. Explain why, in this case, a complete matching is impossible.
  3. To find a complete matching \(F\) agrees to be assigned to either task 4 or task 5. Initially \(B\) is matched to task 3, \(C\) to task 6, \(E\) to task 2 and \(F\) to task 4.
    From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.
AQA D1 2007 June Q2
2
  1. Use a Shell sort to rearrange the following numbers into ascending order, showing the new arrangement after each pass. $$\begin{array} { l l l l l l l l } 28 & 22 & 20 & 17 & 14 & 11 & 6 & 5 \end{array}$$
    1. Write down the number of comparisons on the first pass.
    2. Write down the number of swaps on the first pass.
  3. Find the total number of comparisons needed to rearrange the original list of 8 numbers into ascending order using a shuttle sort.
    (You do not need to perform a shuttle sort.)
AQA D1 2007 June Q3
3 [Figure 1, printed on the insert, is provided for use in this question.]
The following network represents the footpaths connecting 12 buildings on a university campus. The number on each edge represents the time taken, in minutes, to walk along a footpath.
\includegraphics[max width=\textwidth, alt={}, center]{eb305e75-0e85-4f99-8f04-27046a153532-03_899_1317_589_356}
    1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from \(A\) to \(L\).
    2. State the corresponding route.
  2. A new footpath is to be constructed. There are two possibilities:
    from \(A\) to \(D\), with a walking time of 30 minutes; or from \(A\) to \(I\), with a walking time of 20 minutes. Determine which of the two alternative new footpaths would reduce the walking time from \(A\) to \(L\) by the greater amount.
    (3 marks)
AQA D1 2007 June Q4
4 The diagram shows the various ski-runs at a ski resort. There is a shop at \(S\). The manager of the ski resort intends to install a floodlighting system by placing a floodlight at each of the 12 points \(A , B , \ldots , L\) and at the shop at \(S\). The number on each edge represents the distance, in metres, between two points.
\includegraphics[max width=\textwidth, alt={}, center]{eb305e75-0e85-4f99-8f04-27046a153532-04_842_830_577_607} Total of all edges \(= 1135\)
  1. The manager wishes to use the minimum amount of cabling, which must be laid along the ski-runs, to connect the 12 points \(A , B , \ldots , L\) and the shop at \(S\).
    1. Starting from the shop, and showing your working at each stage, use Prim's algorithm to find the minimum amount of cabling needed to connect the shop and the 12 points.
    2. State the length of your minimum spanning tree.
    3. Draw your minimum spanning tree.
    4. The manager used Kruskal's algorithm to find the same minimum spanning tree. Find the seventh and the eighth edges that the manager added to his spanning tree.
  2. At the end of each day a snow plough has to drive at least once along each edge shown in the diagram in preparation for the following day's skiing. The snow plough must start and finish at the point \(L\). Use the Chinese Postman algorithm to find the minimum distance that the snow plough must travel.
    (6 marks)
AQA D1 2007 June Q5
5 [Figure 2, printed on the insert, is provided for use in this question.]
The Jolly Company sells two types of party pack: excellent and luxury.
Each excellent pack has five balloons and each luxury pack has ten balloons.
Each excellent pack has 32 sweets and each luxury pack has 8 sweets.
The company has 1500 balloons and 4000 sweets available.
The company sells at least 50 of each type of pack and at least 140 packs in total.
The company sells \(x\) excellent packs and \(y\) luxury packs.
  1. Show that the above information can be modelled by the following inequalities. $$x + 2 y \leqslant 300 , \quad 4 x + y \leqslant 500 , \quad x \geqslant 50 , \quad y \geqslant 50 , \quad x + y \geqslant 140$$ (4 marks)
  2. The company sells each excellent pack for 80 p and each luxury pack for \(\pounds 1.20\). The company needs to find its minimum and maximum total income.
    1. On Figure 2, draw a suitable diagram to enable this linear programming problem to be solved graphically, indicating the feasible region and an objective line.
    2. Find the company's maximum total income and state the corresponding number of each type of pack that needs to be sold.
    3. Find the company's minimum total income and state the corresponding number of each type of pack that needs to be sold.
AQA D1 2007 June Q6
6
  1. Mark is staying at the Grand Hotel ( \(G\) ) in Oslo. He is going to visit four famous places in Oslo: Aker Brygge ( \(A\) ), the National Theatre ( \(N\) ), Parliament House ( \(P\) ) and the Royal Palace ( \(R\) ). The figures in the table represent the walking times, in seconds, between the places.
    Grand Hotel ( \(G\) )Aker Brygge (A)National Theatre ( \(N\) )Parliament House (P)Royal Palace (R)
    Grand Hotel ( \(G\) )-16518565160
    Aker Brygge (A)165-155115275
    National Theatre ( \(N\) )185155-205125
    Parliament House (P)65115205-225
    Royal Palace (R)160275125225-
    Mark is to start his tour from the Grand Hotel, visiting each place once before returning to the Grand Hotel. Mark wishes to keep his walking time to a minimum.
    1. Use the nearest neighbour algorithm, starting from the Grand Hotel, to find an upper bound for the walking time for Mark's tour.
    2. By deleting the Grand Hotel, find a lower bound for the walking time for Mark's tour.
    3. The walking time for an optimal tour is \(T\) seconds. Use your answers to parts (a)(i) and (a)(ii) to write down a conclusion about \(T\).
  2. Mark then intends to start from the Grand Hotel ( \(G\) ), visit three museums, Ibsen ( \(I\) ), Munch ( \(M\) ) and Viking ( \(V\) ), and return to the Grand Hotel. He uses public transport. The table shows the minimum travelling times, in minutes, between the places.
    \backslashbox{From}{To}Grand Hotel ( \(G\) )Ibsen (I)Munch ( \(M\) )Viking ( \(\boldsymbol { V }\) )
    Grand Hotel ( \(\boldsymbol { G }\) )-201730
    Ibsen (I)15-3216
    Munch (M)2618-21
    Viking ( \(\boldsymbol { V }\) )192724-
    1. Find the length of the tour \(G I M V G\).
    2. Find the length of the tour GVMIG.
    3. Find the number of different possible tours for Mark.
    4. Write down the number of different possible tours for Mark if he were to visit \(n\) museums, starting and finishing at the Grand Hotel.
AQA D1 2014 June Q1
1 Five people, \(A , B , C , D\) and \(E\), are to be allocated to five tasks, 1, 2, 3, 4 and 5 . The following bipartite graph shows the tasks that each person is able to undertake.
\includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-02_441_437_699_797}
  1. Represent this information in an adjacency matrix.
  2. Initially, \(A\) is allocated to task 3, \(B\) to task 2 and \(C\) to task 4.
    1. Demonstrate, by using an alternating-path algorithm from this initial matching, how each person can be allocated to a different task.
    2. Find a different allocation of people to tasks.
AQA D1 2014 June Q2
2 A document which is currently written in English is to be translated into six other European Union languages. The cost of translating a document varies, as it is harder to find translators for some languages. The costs, in euros, are shown in the table below.
    1. On the table below, showing the order in which you select the edges, use Prim's algorithm, starting from \(E\), to find a minimum spanning tree for the graph connecting \(D , E , F , G , H , I\) and \(S\).
    2. Find the length of your minimum spanning tree.
    3. Draw your minimum spanning tree.
  2. It is given that the graph has a unique minimum spanning tree. State the final two edges that would be added to complete the minimum spanning tree in the case where:
    1. Prim's algorithm starting from \(H\) is used;
    2. Kruskal's algorithm is used. \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Answer space for question 2}
      Danish ( \(\boldsymbol { D }\) )English ( \(\boldsymbol { E }\) )French (F)German ( \(G\) )Hungarian (H)Italian (I)Spanish \(\boldsymbol { ( } \boldsymbol { S } \boldsymbol { ) }\)
      Danish (D)-12014080170140140
      English ( \(\boldsymbol { E }\) )120-7080130130110
      French (F)14070-901908590
      German ( \(G\) )808090-110100100
      Hungarian (H)170130190110-140150
      Italian (I)14013085100140-60
      Spanish ( \(\boldsymbol { S }\) )1401109010015060-
      \end{table}
AQA D1 2014 June Q3
2 marks
3 The network below shows 11 towns, \(A , B , \ldots , K\). The number on each edge shows the time, in minutes, to travel between a pair of towns.
    1. Use Dijkstra's algorithm on the diagram below to find the minimum time to travel from \(A\) to \(K\).
    2. State the corresponding route.
  2. On a particular day, Jenny travels from \(A\) to \(K\) but visits her friend at \(D\) on her way. Find Jenny's minimum travelling time.
  3. On a different day, all roads connected to \(I\) are closed due to flooding. Jenny does not visit her friend at \(D\). Find her minimum time to travel from \(A\) to \(K\). State the route corresponding to this minimum time.
    [0pt] [2 marks] \section*{Answer space for question 3}
    \includegraphics[max width=\textwidth, alt={}]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-06_1478_1548_1213_239}
AQA D1 2014 June Q4
3 marks
4 Paulo sells vegetables from his van. He drives around the streets of a small village. The network shows the streets in the village. The number on each edge shows the time, in minutes, to drive along that street. Paulo starts from his house located at vertex \(A\) and drives along all the streets at least once before returning to his house.
\includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-10_1518_1605_598_198} The total of all the times in the diagram is 79.5 minutes.
  1. Find the length of an optimal Chinese postman route around the village, starting and finishing at \(A\). (Shortest routes between vertices may be found by inspection.)
  2. For an optimal Chinese postman route, state:
    1. the number of times the vertex \(F\) would occur;
    2. the number of times the vertex \(D\) would occur.
  3. Toto is standing for the position of Mayor in the local elections. He intends to travel along all the roads at least once. He can start his journey at any vertex and can finish his journey at any vertex.
    1. Find the length of an optimal route for Toto.
      [0pt]
    2. State the vertices from which Toto could start in order to achieve this optimal route. [3 marks]
AQA D1 2014 June Q5
6 marks
5 The feasible region of a linear programming problem is determined by the following: $$\begin{aligned} x & \geqslant 1
y & \geqslant 3
x + y & \geqslant 5
x + y & \leqslant 12
3 x + 8 y & \leqslant 64 \end{aligned}$$
  1. On the grid below, draw a suitable diagram to represent the inequalities and indicate the feasible region.
  2. Use your diagram to find, on the feasible region:
    1. the maximum value of \(3 x + y\);
    2. the maximum value of \(2 x + 3 y\);
    3. the minimum value of \(- 2 x + y\). In each case, state the coordinates of the point corresponding to your answer.
      [0pt] [6 marks]
AQA D1 2014 June Q6
4 marks
6
  1. Sarah is solving a travelling-salesman problem.
    1. She finds the following upper bounds: \(32,33,32,32,30,32,32\). Write down the best upper bound.
    2. She finds the following lower bounds: 17, 18, 17, 20, 18, 17, 20. Write down the best lower bound.
  2. Rob is travelling by train to a number of cities. He is to start at \(M\) and visit each other city at least once before returning to \(M\). The diagram shows the travelling times, in minutes, between cities. Where no time is shown, there is no direct journey available.
    \includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-16_959_1122_1059_443} The table below shows the minimum travelling times between all pairs of cities.
    \cline { 2 - 6 } \multicolumn{1}{c|}{}\(\boldsymbol { B }\)\(\boldsymbol { E }\)\(\boldsymbol { L }\)\(\boldsymbol { M }\)\(\boldsymbol { N }\)
    \(\boldsymbol { B }\)-23082102192
    \(\boldsymbol { E }\)230-148244258
    \(\boldsymbol { L }\)82148-126110
    \(\boldsymbol { M }\)102244126-236
    \(\boldsymbol { N }\)192258110236-
    1. Explain why the minimum travelling time from \(M\) to \(N\) is not 283 .
    2. Find an upper bound for the minimum travelling time by using the tour \(M N B E L M\).
    3. Write down the actual route corresponding to the tour \(M N B E L M\).
    4. Use the nearest-neighbour algorithm, starting from \(M\), to find another upper bound for the minimum travelling time of Rob's tour.
      [0pt] [4 marks] QUESTION
    1. The best upper bound is \(\_\_\_\_\)
    2. The best lower bound is \(\_\_\_\_\)
AQA D1 2014 June Q7
7 A factory makes batches of three different types of battery: basic, long-life and super.
Each basic batch needs 4 minutes on machine \(A\), 7 minutes on machine \(B\) and 14 minutes on machine \(C\). Each long-life batch needs 10 minutes on machine \(A\), 14 minutes on machine \(B\) and 21 minutes on machine \(C\). Each super batch needs 10 minutes on machine \(A\), 14 minutes on machine \(B\) and 28 minutes on machine \(C\). Machine \(A\) is available for 4 hours a day, machine \(B\) for 3.5 hours a day and machine \(C\) for 7 hours a day. Each day the factory must make:
more basic batches than the total number of long-life and super batches; at least as many long-life batches as super batches. At least 15\% of the production must be long-life batches.
Each day, the factory makes \(x\) basic, \(y\) long-life and \(z\) super batches.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), writing your answers with simplified integer coefficients.
AQA D1 2014 June Q8
8 In this question you may use the fact that any simple graph must have an even number of vertices of odd degree.
  1. A simple graph has five vertices and their degrees are $$x , x + 1 , x + 1 , x + 2 \text { and } x + 3$$
    1. Show that \(x\) must be odd.
    2. Find the value of \(x\) and draw a graph with vertices having the given degrees.
  2. A simple graph has 10 vertices.
    1. State the minimum possible degree and maximum possible degree of a vertex.
    2. Show that the degrees of the vertices cannot all be different.
      □
      □
AQA D1 2015 June Q1
5 marks
1 A quiz team must answer questions from six different topics, numbered 1 to 6. The team has six players, \(A , B , C , D , E\) and \(F\). Each player can only answer questions on one of the topics. The players list their preferred topics. The bipartite graph shows their choices.
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-02_711_499_781_760} Initially, \(A\) is allocated topic 2, \(B\) is allocated topic \(3 , C\) is allocated topic 1 and \(F\) is allocated topic 4. By using an alternating path algorithm from this initial matching, find a complete matching.
[0pt] [5 marks]
AQA D1 2015 June Q2
2 marks
2 The network below shows 8 towns, \(A , B , \ldots , H\). The number on each edge shows the length of the road, in miles, between towns. During the winter, the council treats some of the roads with salt so that each town can be safely reached on treated roads from any other town. It costs \(\pounds 30\) to treat a mile of road.
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-04_876_1611_497_210}
    1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
    2. Draw your minimum spanning tree.
    3. Calculate the minimum cost to the council of making it possible for each town to be safely reached on treated roads from any other town.
  2. On one occasion, the road from \(C\) to \(E\) is impassable because of flooding. Find the minimum cost of treating sufficient roads for safe travel in this case.
    [0pt] [2 marks]
AQA D1 2015 June Q3
3 Four students, \(A , B , C\) and \(D\), are using different algorithms to sort 16 numbers into ascending order.
  1. Student \(A\) uses the quicksort algorithm. State the number of comparisons on the first pass.
  2. Student \(B\) uses the Shell sort algorithm. State the number of comparisons on the first pass.
  3. Student \(C\) uses the shuttle sort algorithm. State the minimum number of comparisons on the final pass.
  4. Student \(D\) uses the bubble sort algorithm. Find the maximum total number of comparisons.
AQA D1 2015 June Q4
2 marks
4 The network opposite shows roads connecting 10 villages, \(A , B , \ldots , J\). The time taken to drive along a road is not proportional to the length of the road. The number on each edge shows the average time, in minutes, to drive along each road.
  1. A commuter wishes to drive from village \(A\) to the railway station at \(J\).
    1. Use Dijkstra's algorithm, on the diagram opposite, to find the shortest driving time from \(A\) to \(J\).
    2. State the corresponding route.
  2. A taxi driver is in village \(D\) at 10.30 am when she receives a radio call asking her to pick up a passenger at village \(A\) and take him to the station at \(J\). Assuming that it takes her 3 minutes to load the passenger and his luggage, at what time should she expect to arrive at the station?
    [0pt] [2 marks]
    \includegraphics[max width=\textwidth, alt={}]{f5890e58-38c3-413c-8762-6f80ce6dcec7-09_2484_1717_223_150}