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

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.

(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 this first pass.

(ii) Write down the number of comparisons and the number of swaps performed during this first pass.

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.

A gardener needs the following lengths of string. All lengths are in metres.

She cuts the lengths from balls of string. Each ball contains 10m of string.

Calculate a lower bound for the number of balls of string the gardener needs. You must make your method clear.

Use the first‑fit bin packing algorithm to determine how the lengths could be cut from the balls of string.

The following algorithm determines the number of comparisons made when Prim's algorithm is applied to

Step 1 Start

Step 2 Input the value of

Step 3 Let

Step 4 Let

Step 5 Let

Step 6 Let

Step 7 Let

Step 8 Let

Step 9 If go to Step 6

Step 10 Output

Step 11 Stop

For , complete the table below to show the results obtained at each step of the algorithm.

The weights of the ten arcs in Figure 4 are

(i) Starting at the left‑hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass.

(ii) Find the total number of comparisons performed during the sort.

Find the maximum total number of comparisons required to sort the weights of the 10 arcs of into ascending order using bubble sort.

It is given that the maximum total number of comparisons required to sort the weights of the arcs of into ascending order using bubble sort is

where is a constant.

Determine the maximum total number of comparisons required to sort the weights of the arcs of into ascending order using bubble sort. You must make your method and working clear.

Figure 4 represents a network with nodes, A, B, C, D, E, F, G, H and J. The number on each edge gives the length of the corresponding edge.

(i) Use Dijkstra’s algorithm to find the shortest path from A to J.

(ii) State the length of the shortest path from A to J.

One application of Dijkstra’s algorithm has order , where is the number of nodes in the network.

It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes.

Calculate approximately how long it would take, in minutes, for the computer to find the shortest path from a given start node to a given end node for a network of 9000 nodes.

The eleven distinct numbers listed below are to be packed into bins of size 40

It is known that

• is an integer less than 40

• is the largest number in the list

Explain why it is not possible to pack the numbers into 3 bins of size 40

Given that it is possible to pack the numbers into 4 bins of size 40

determine the range of values for

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

Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly.

When the first-fit decreasing bin packing algorithm is applied to the list, neither the 15 nor the 13 is placed in the first bin.

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

The eleven numbers listed above are to be packed into bins of size where is a positive integer. When the first-fit bin packing algorithm is applied to the eleven numbers, the bins are packed as shown below.

Bin 1: 17 8 12

Bin 2: 16 24

Bin 3: 19 11 4

Bin 4: 23 13

Bin 5: 20

Explain why this packing means that the value of must be 40

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

Use a quick sort to obtain the fully sorted list. You must make your pivots clear.

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