Decision Mathematics 1: Algorithms and graph theoryEdexcel A-Level Further Maths: Topic test

1. 1
   A caterer must pack eight containers, of masses 9, 7, 11, 16, 5, 18, 12 and 14 kg, into crates that each hold at most 25 kg. The containers are considered in the order listed.

   (a)

   How many crates are needed when the first-fit algorithm is used?

   [1 mark]

   • A4
   • B5
   • C6
   • D3

   (b)

   What is the lower bound for the number of crates needed?

   [1 mark]

   • A3
   • B5
   • C6
   • D4

   (c)

   Use the first-fit decreasing algorithm to pack the containers. State the contents of each crate.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   The list 17, 4, 12, 9, 20, 6 is to be sorted into ascending order.

   (a)

   What is the list after the first pass of a bubble sort?

   [1 mark]

   • A4, 6, 9, 12, 17, 20
   • B4, 17, 12, 9, 20, 6
   • C4, 12, 9, 17, 6, 20
   • D4, 12, 9, 17, 20, 6

   (b)

   How many comparisons are made in the first pass of a bubble sort on this list?

   [1 mark]

   • A5
   • B6
   • C4
   • D15

   (c)

   Perform the first pass of a quick sort on the list, using the middle item as the pivot. Show the resulting sublists.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Six teams each play every other team exactly once. The fixtures are modelled by the complete graph $K_6$, with a vertex for each team and an edge for each match.

   (a)

   Show that there are 15 matches, and explain why $K_6$ is not Eulerian.

   [3 marks]

   (b)

   Find the least number of edges that must be deleted from $K_6$ so that the remaining graph is Eulerian. Justify your answer and give an example of a suitable set of edges.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Graph $G$ has six vertices $P$, $Q$, $R$, $S$, $T$ and $U$ and nine edges: $PQ$, $QR$, $RS$, $ST$, $TU$, $UP$, $PS$, $QT$ and $RU$.

   (a)

   Use the planarity algorithm to show that $G$ is not planar.

   [6 marks]

   (b)

   The edge $PS$ is deleted from $G$ to give the graph $H$. Show that $H$ is planar, and determine whether $H$ is Eulerian, semi-Eulerian or neither.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   A connected simple graph $G$ has 8 vertices and 11 edges. Two of the vertices have degree 2 and the other six have degree 3.

   (a)

   How many edges does a spanning tree of $G$ have?

   [1 mark]

   • A8
   • B11
   • C7
   • D6

   (b)

   What is the least number of edges that must be deleted from $G$ to form a spanning tree?

   [1 mark]

   • A3
   • B4
   • C7
   • D11

   (c)

   Determine whether $G$ is Eulerian, semi-Eulerian or neither, giving a reason.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   A computer uses a bubble sort to sort lists of $n$ numbers. The time taken is modelled as proportional to the number of comparisons made.

   (a)

   What is the greatest number of comparisons that a bubble sort needs to sort a list of 12 numbers, when each pass compares every adjacent pair that is not yet in its final position?

   [1 mark]

   • A66
   • B132
   • C144
   • D11

   (b)

   What is the order of the bubble sort algorithm?

   [1 mark]

   • A$n$
   • B$n\log n$
   • C$2^n$
   • D$n^2$

   (c)

   A list of 50 numbers takes 3 seconds to sort. Using the order of the algorithm, estimate the time taken to sort a list of 200 numbers.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   Graph $N$ has seven vertices $A$, $B$, $C$, $D$, $E$, $F$ and $G$. A Hamiltonian cycle of $N$ is $ABCDEFGA$. The only other edges of $N$ are $AC$, $BE$, $CF$ and $EG$.

   (a)

   List the pairs of edges that are not on the Hamiltonian cycle and that must be drawn on opposite sides of the cycle when the planarity algorithm is used.

   [3 marks]

   (b)

   Complete the planarity algorithm to show that $N$ is planar. The edge $BF$ is added to $N$ to form $N'$. Show that $N'$ is not planar.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   The degrees of the seven vertices of a connected simple graph $N$, in the order in which the vertices are labelled $A$ to $G$, are 3, 5, 6, 3, 2, 4, 3.

   (a)

   Use a bubble sort to sort the degrees into descending order. Show the list after each pass.

   [6 marks]

   (b)

   Find the number of edges of $N$ and determine whether $N$ is Eulerian, semi-Eulerian or neither. Given that $N$ has a Hamiltonian cycle, find how many edges are not on the cycle, and how many of these are incident with the vertex of degree 6.

   [6 marks]

   Total for question 8: 12 marks

End of questions