CourseCourseConceptConceptDocsDocuments

Edexcel A-Level Mathematics AS D1.1.2 Bin Packing Sorting and Binary Search Questions

Practise list algorithms by tracing sorting passes, bin-packing allocations and binary-search pivots with visible intermediate steps.

Syllabus
First assessment 2019
Course
Mathematics YMA01
Level
AS

Exam points

  • Show quick sort or bubble sort passes, including pivots, comparisons and swaps.
  • Apply first-fit or first-fit decreasing and record the item contents of each bin.
  • Trace binary search by naming the pivot and the rejected part of the sorted list.

Edexcel A-Level Mathematics AS D1.1.2 Bin Packing Sorting and Binary Search Questions question 1

[Maximum number: 13]

1.81.42.61.62.80.93.10.81.22.40.6\begin{array}{lllllllllll}1.8 & 1.4 & 2.6 & 1.6 & 2.8 & 0.9 & 3.1 & 0.8 & 1.2 & 2.4 & 0.6\end{array}

Question (a)

(a)

Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5

[ 3 ]

Question (b)

(b)

The list is to be sorted into descending order.

[ 3 ]

Question (i)

(i)

Perform one pass of a bubble sort, starting at the left-hand end of the list. You must write down the list that results at the end of the first pass.

[ 1 ]

Question (ii)

(ii)

Write down the number of comparisons and the number of swaps performed during the first pass.

[ 2 ]

Question (c)

(c)

After a second pass using this bubble sort, the updated list is

2.61.82.81.63.11.41.22.40.90.80.6\begin{array}{lllllllllll} 2.6 & 1.8 & 2.8 & 1.6 & 3.1 & 1.4 & 1.2 & 2.4 & 0.9 & 0.8 & 0.6 \end{array}

Use a quick sort on this updated list to obtain the fully sorted list in descending order. You must make your pivots clear.

[ 4 ]

Question (d)

(d)

Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 5

[ 3 ]
All question bank results loaded