Algorithms (Edexcel International AS Maths: Decision 1): Exam Questions

1.8   1.4   2.6   1.6   2.8   0.9   3.1   0.8   1.2   2.4   0.6

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

The list is 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 the first pass.

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

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

2.6   1.8   2.8   1.6   3.1   1.4   1.2   2.4   0.9   0.8   0.6

Use a quick sort on this updated list to obtain the fully sorted list in descending order. 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 5

175 135 210 105 100 150 60 20 70 125

The numbers in the list above represent the weights, in kilograms, of ten crates. The crates are to be transported in trucks that can each hold a maximum total crate weight of 300kg.

Calculate a lower bound for the number of trucks that will be needed to transport the crates.

Using the list provided, carry out a bubble sort to produce a list of the weights in descending order. You need only give the state of the list after each pass.

Use the first‑fit decreasing bin packing algorithm to allocate the crates to the trucks.

17     9     15     8     20     13     28     4     12     5

The numbers in the list shown above are the weights, in kilograms, of ten boxes. The boxes are to be transported in containers that will each hold a maximum weight of 40 kilograms.

Calculate a lower bound for the number of containers that will be needed to transport the boxes. You must show your working.

Use the first-fit bin packing algorithm to allocate the boxes to the containers.

Using the list provided, carry out a quick sort to produce a list of the weights in ascending order. You must make your pivots clear.

Use the binary search algorithm to try to locate the weight of 9 in the sorted list. Clearly indicate how you choose your pivots and which part of the list is being rejected at each stage.

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

14 20 23 17 15 22 19 25 13 28 32

A lower bound for the number of bins required is 4

Determine the range of possible values of . You must make your method clear.

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 bin packing algorithm is applied to the original list of numbers, the following allocation is achieved.

When the first-fit decreasing bin packing algorithm is applied to the sorted list of numbers, the following allocation is achieved.

Determine the value of . You must explain your reasoning fully

16 23 18 9 4 20 35 5 17 13 6 11

The numbers in the list represent the weights, in kilograms, of twelve parcels. The parcels are to be transported in containers that will each hold a maximum weight of 45kg.

Calculate a lower bound for the number of containers needed. You must make your method clear.

Use the first‑fit bin packing algorithm to allocate the parcels to the containers.

Carry out a bubble sort, starting at the left‑hand end of the list, to produce a list of the weights in descending order. You should only give the state of the list after each pass.

Use the first‑fit decreasing bin packing algorithm to allocate the parcels to the containers.

An algorithm for finding the positive real root of the equation is described by the flow chart shown in Figure 2.

Use the flow chart, with = 1, to complete the table in the answer book, stating values to at least 6 decimal places. Give the final output correct to 5 decimal places.

Given that the value of the input is a non‑negative real number,

determine the set of values for that cannot be used to find the positive real root of using this flow chart.

Use the binary search algorithm to try to locate the word “Parallelogram” in the following alphabetical list. Clearly indicate how you choose your pivots and which part of the list you are rejecting at each stage.

Arc

Centre

Chord

Circle

Circumference

Diameter

Radius

Sector

Segment

Tangent

2.6   0.8   2.1   1.2   0.9   1.7   2.3   0.3   1.8   2.7

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

2.6   0.8   2.1   1.2   0.9   1.7   2.3   0.3   1.8   2.7

The list is to be sorted into descending order.

(i) Starting at the left-hand end of the above list, perform two passes through the list using a bubble sort. Write down the lists that result at the end of the first pass and the second pass.

(ii) Write down, in the table, the number of comparisons and the number of swaps performed during each of these two passes.

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

2.6   2.1   1.7   2.3   1.2   1.8   2.7   0.9   0.8   0.3

Use a quick sort on this updated list 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 5

(i) Describe how to carry out the first pass of a bubble sort when it is used to sort a list of numbers into ascending order.

(ii) Write down the circumstances under which a bubble sort stops.

A bubble sort, starting at the left-hand end of the list, is used to sort a list of ten numbers into ascending order. After a number of passes the list reads

0.9     1.2     1.5     0.5     1.4     1.1     0.7     1.7     2.2     3.2

Determine the maximum number of passes that could have taken place on this list. You must give a reason for your answer.

Complete the bubble sort to produce a list of the numbers in ascending order. You only need to give the state of the list after each complete pass.

0.9     1.2     1.5     0.5     1.4     1.1     0.7     1.7     2.2     3.2

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

35   17   10   7   28   23   41   15   20   29

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

The list of numbers 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.

Use the first-fit decreasing bin packing algorithm on your ordered list to pack the numbers into bins of size 60

The ten distinct numbers below are to be sorted into descending order.

20   24   17   26   8   15       19   12

A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list.

After the second complete pass the list is

24   26   20   17   15     19   12     8

Find the constraints on the values of and .

Pupils from ten schools are visiting a museum on the same day. The museum needs to allocate each school to a tour group. The maximum size of each tour group is 42 pupils. A group may include pupils from more than one school. Pupils from each school must be kept in the same tour group. The numbers of pupils visiting from each school are given below.

8 17 9 14 18 12 22 10 15 7

Calculate a lower bound for the number of tour groups required. You must make your method clear.

8 17 9 14 18 12 22 10 15 7

Using the above list, apply the first-fit bin packing algorithm to allocate the pupils visiting from each school to tour groups.

8 17 9 14 18 12 22 10 15 7

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

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

Using your sorted list from (c), apply the first-fit decreasing bin packing algorithm to obtain a second allocation of pupils to tour groups.

Figure 2 represents the corridors in the museum. The number on each arc is the length, in metres, of the corresponding corridor. Sally is a tour guide in the museum and she must travel along each corridor at least once during each tour. Sally wishes to minimise the length of her route. She must start and finish at the museum’s entrance at A.

Use an appropriate algorithm to find the corridors that Sally will need to traverse twice. You should make your method and working clear.

Write down a possible shortest route, giving its length.

Sally is now allowed to start at H and finish her route at a different vertex. A route of minimum length that includes each corridor at least once needs to be found.

State the finishing vertex of Sally’s new route and calculate the difference in length between this new route and the route found in (f).