Practise implementing algorithms on flow charts and lists, including sorting traces, bin allocations, searches and justified bounds from algorithm steps.
Figure 2
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 a=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 a is a non-negative real number,
determine the set of values for a that cannot be used to find the positive real root of using this flow chart.
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.
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.
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
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
The numbers in the list represent the weights, in kilograms, of twelve parcels. The parcels ar\& to be transported in containers that will each hold a maximum weight of 45 kg .
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.