Algorithms (Edexcel A Level Further Maths: Decision Maths 1)

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

The list of numbers is now to be sorted into descending order.

Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.

For a list of numbers, the quick sort algorithm has, on average, order .

Given that it takes 2.32 seconds to run the algorithm when = 450

Calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when = 11 250. You should make your method and working clear.

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

The first‐fit bin packing algorithm is to be used to pack numbers into bins. The number of comparisons is used to measure the order of the first‐fit bin packing algorithm.

By considering the worst case, determine the order of the first‐fit bin packing algorithm in terms of . You must make your method and working clear.

The nine distinct numbers in the following list are to be packed into bins of size 50

23         17         19                  24         8         18         10         21

When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation.

Bin 1:     23       17        8

Bin 2:     19               10

Bin 3:     24       18

Bin 4:     21

Explain why 

The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is

23        19         17         24                  18         10         21         8

Using this information, write down the smallest interval that must contain , giving your answer as an inequality.

When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation.

Bin 1:    24        23

Bin 2:    21        19         10

Bin 3:    18        17         

Bin 4:     8

Given that only one of the bins is full and that  is an integer,

calculate the value of . You must give reasons for your answer.

The numbers listed above are to be sorted into descending order.

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

Use a quick sort on this updated list to obtain the fully sorted list. You should show the result of each pass and identify your pivots clearly.

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

Determine whether your answer to part (c) uses the minimum number of bins. You must justify your answer.

Figure 1

A Hamiltonian cycle for the graph in Figure 1 begins C, V, E, X, A, W, ….

Complete the Hamiltonian cycle.

Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer.

The list of ten numbers above is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.

The ten numbers are to be packed into bins of size , where  is a positive integer.

When the first-fit bin packing algorithm is applied to the original list of ten numbers, the following allocation is obtained.

Bin 1:      30        12        2
Bin 2:      5          23        10
Bin 3:     18         15
Bin 4:     36
Bin 5:     24

Explain why the value of the integer  must be either 44 or 45

Use the first-fit decreasing bin packing algorithm to determine how the numbers can be packed into bins of size 45

A list of  numbers needs to be sorted into descending order starting at the left-hand end of the list.

Describe how to carry out the first pass of a bubble sort on the numbers in the list.

Bubble sort is a quadratic order algorithm.

A computer takes approximately 0.021 seconds to apply a bubble sort to a list of 2000 numbers.

Estimate the time it would take the computer to apply a bubble sort to a list of 50 000 numbers. Make your method clear.