7.03g Order notation: O(n^k) for k = 0,1,2,3,4

1

1. 1. Use the first-fit decreasing method to pack these weights, in kg, into bags that can each hold a maximum of 10 kg . $$\begin{array} { l l l l l l l l l l } 2 & 7 & 5 & 3 & 3 & 4 & 3 & 2 & 8 & 3 \end{array}$$
   2. Find a packing that uses fewer bags.
2. The order of a particular algorithm is a cubic function of the number of input values. It takes 4 seconds for the algorithm to process 100 input values. Approximately how many seconds will it take the algorithm to process 500 input values?

5 Consider the following algorithm which is to be applied to a list of numbers.

1. Apply the algorithm to this list. $$\begin{array} { l l l l l } 3 & 6 & 5 & 7 & 3 \end{array}$$ Record in a table the values of \(X , N , T\) and \(S\) at each pass through Step 3 and give the output values.
2. Write down the number of additions and the number of multiplications that are done in Step 3 for a list of five numbers. Hence find the total number of arithmetic operations (additions, multiplications, divisions, subtractions and square roots) that are done in Step 3 and Step 5 when applying the algorithm to a list of five numbers.
3. Find an expression for the total number of arithmetic operations that are done in applying the algorithm to a list of \(n\) numbers.
4. The total number of arithmetic operations can be used as a measure of the run-time for the algorithm. If it takes approximately 2 seconds to apply the algorithm to a list of 1000 numbers, approximately how long will it take to apply the algorithm to a list of 5000 numbers?

1

1. Use the first-fit method to pack the following weights in kg into boxes that can hold 8 kg each. $$\begin{array} { l l l l l l l } 2 & 4 & 3 & 3 & 2 & 5 & 4 \end{array}$$ Show clearly which weights are packed into which boxes.
2. Use the first-fit decreasing method to pack the same weights into boxes that can hold 8 kg each. You do not need to use an algorithm to sort the list into decreasing order.
3. First-fit decreasing is a quadratic order method. A computer takes 15 seconds to apply the first-fit decreasing method to a list of 1000 items; approximately how long will it take to apply the first-fit decreasing method to a list of 2000 items?

1 Owen and Hari each want to sort the following list of marks into decreasing order. $$\begin{array} { l l l l l l l l l l } 31 & 28 & 75 & 87 & 42 & 43 & 70 & 56 & 61 & 95 \end{array}$$

1. Owen uses bubble sort, starting from the left-hand end of the list.
   1. Show the result of the first pass through the list. Record the number of comparisons and the number of swaps used in this first pass. Which marks, if any, are guaranteed to be in their correct final positions after the first pass?
   2. Write down the list at the end of the second pass of bubble sort.
   3. How many more passes are needed to get the value 95 to the start of the list?
   4. Hari uses shuttle sort, starting from the left-hand end of the list. Show the results of the first and the second pass through the list. Record the number of comparisons and the number of swaps used in each of these passes.
   5. Explain why, for this particular list, the total number of comparisons will be greater using bubble sort than using shuttle sort. Shuttle sort is a quadratic order algorithm.
   6. If it takes Hari 20 seconds to sort a list of ten marks using shuttle sort, approximately how long will it take Hari to sort a list of fifty marks?

1 Satellite navigation systems (sat navs) use a version of Dijkstra's algorithm to find the shortest route between two places. A simplified map is shown below. The values marked represent road distances, in km , for that section of road (from a place to a road junction, or between two places). \begin{figure}[h] \end{figure}

1. Use the map to construct a network with exactly 10 arcs to show the direct distances between these places, with no road junctions shown. For example, there will need to be an arc connecting \(A\) to \(B\) of weight 22, and also arcs connecting \(A\) to \(C , D\), and \(E\). There is no arc connecting \(A\) to \(F\) (because there is no route from \(A\) to \(F\) that does not pass through another place).
2. Apply Dijkstra's algorithm, starting at \(A\), to find the shortest route from \(A\) to \(F\). Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ).
3. If it takes 3 seconds for a certain sat nav to find the shortest route between two places when it has to process 200 places, calculate approximately how many minutes it will take when it has to process 4000 places.

5 This question uses the same network as question 4. The total weight of the arcs in the network is 224. \includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-5_618_1415_310_319}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(G\).
2. Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ). It takes 2.25 seconds for a certain computer to apply Dijkstra's algorithm to a network with 7 vertices. Calculate approximately how many hours it will take to apply Dijkstra's algorithm to a network with 1400 vertices.
3. How much shorter would the path \(C E\) need to be for it to become part of a shortest path from \(A\) to \(G\) ? Following a landslip, the paths \(A C\) and \(C E\) become blocked and cannot be used. A warden needs to travel along all the remaining paths to check that there are no more landslips.
4. Find the shortest distance that the warden must travel, assuming that she starts and ends at vertex \(C\). Show your working.

3 The following algorithm finds two positive integers for which the sum of their squares equals a given input, when this is possible. The function \(\operatorname { INT } ( X )\) gives the largest integer that is less than or equal to \(X\). For example: \(\operatorname { INT } ( 6.9 ) = 6\), \(\operatorname { INT } ( 7 ) = 7 , \operatorname { INT } ( 7.1 ) = 7\).

1. Apply the algorithm to the input \(N = 500\). You only need to write down values when they change and there is no need to record the use of lines \(30,60,70\) or 90 .
2. Apply the algorithm to the input \(N = 7\).
3. Explain why lines 70 and 110 are needed. The algorithm has order \(\sqrt { N }\).
4. If it takes 0.7 seconds to run the algorithm when \(N = 3000\), roughly how long will it take when \(N = 12000\) ?

3 The list of numbers below is to be sorted into increasing order. \(\begin{array} { l l l l l l l l } 23 & 10 & 18 & 7 & 62 & 54 & 31 & 82 \end{array}\)

1. Sort the list using bubble sort. You do not need to show intermediate working.
   1. Record the list that results at the end of each pass.
   2. Record the number of swaps used in each pass.
2. Now sort the original list using shuttle sort. You do not need to show intermediate working.
   1. Record the list that results at the end of each pass.
   2. Record the number of swaps used in each pass.
3. Using the total number of comparisons plus the total number of swaps as a measure of efficiency, explain why shuttle sort is more efficient than bubble sort for sorting this particular list. Bubble sort and shuttle sort are both \(\mathrm { O } \left( n ^ { 2 } \right)\).
4. Explain what this means for the run-time of the algorithms when the length of the list being sorted changes from 1000 to 3000.

1 Algorithm X is given below: STEP 1: \(\quad\) Let \(A = 0\) STEP 2: Input the value of \(B \quad [ B\) must be a positive integer]
STEP 3: \(\quad C = \operatorname { INT } ( B \div 3 )\) STEP 4: \(D = B + 3 C\) STEP 5: \(\quad\) Replace \(A\) with \(( D - A )\) STEP 6: Decrease \(B\) by 1
STEP 7: If \(B > 0\) go to STEP 3
STEP 8: Display the value of \(\operatorname { ABS } ( A )\) and STOP

1. Trace through algorithm X when the input is \(B = 5\). Only record changes to the values of the variables, \(A , B , C\) and \(D\), using a new column of the table in the Printed Answer Booklet each time one of these variables changes.
2. Explain carefully how you know that algorithm X is finite for all positive integer values of \(B\).
3. Explain what it means to say that an algorithm is deterministic. The run-time of algorithm X is \(k \times\) (number of times that STEP 6 is used), for some positive constant \(k\).
4. Explain, with reference to your answer to part (b), why the order of algorithm X is \(\mathrm { O } ( n )\), where \(n\) is the input value of \(B\). For each input \(B\), algorithm Y achieves the same output as algorithm X , but the run-time of algorithm Y is \(m \times\) (the number of digits in \(B\) ), where \(m\) is a positive constant.
5. Show that algorithm Y is more efficient than algorithm X .

4 An algorithm must have an input, an output, be deterministic and finite.

1. Why is a counter sometimes used in an algorithm? A computer takes 0.2 seconds to sort a list of 500 numbers.
2. How long would you expect the computer to take to sort a list of 5000 numbers? Simon says that he can sort a list of numbers 'just by looking at them'.
3. Explain to Simon why sorting algorithms are needed.
4. Demonstrate how quick sort works by using it to sort the following list into increasing order. You should indicate the pivots used and which values are already known to be in their correct position. \(\begin{array} { l l l l l } 41 & 17 & 8 & 33 & 29 \end{array}\) For an average case the efficiency of quick sort is O (nlogn), where n is the number of items in the list.
5. Explain why quick sort is typically quicker than bubble sort and shuttle sort. When the number of comparisons made is used as a measure of the efficiency, the worst case for quick sort is no more efficient than the worst case for bubble sort. An arrangement of the five numbers from part (d) makes up a new list that is to be sorted using the bubble sort or the quick sort.
6. Without writing out all the passes, determine

5 A list of 8 values is given below. The list is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.

1. Carry out the first two passes of the sort. A different list of 8 values is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
2. 1. State the maximum number of passes that could be required.
   2. Find the minimum number of passes that could be required. The run-time for quick sort could be measured by counting the number of comparisons used. In the worst case, the run time for quick sort is \(\mathrm { O } \left( n ^ { 2 } \right)\). A computer takes at most 0.03 seconds to sort a list of 100 values into increasing order using quick sort.
3. Calculate an estimate for the time taken, in the worst case, to sort a list of 500 values using quick sort. A list of \(n\) values (where \(n > 10\) ) is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
4. Explain why, in the best case, \(n - 3\) comparisons are used in the second pass.

1. \begin{figure}[h] \end{figure} Figure 1 represents a network of roads.
The number on each arc represents the time taken, in minutes, to drive along the corresponding road.

1. 1. Use Dijkstra's algorithm to find the shortest time needed to travel from A to H .
   2. State the quickest route. For a network with \(n\) vertices, Dijkstra's algorithm has order \(n ^ { 2 }\)
2. If it takes 1.5 seconds to run the algorithm when \(n = 250\), calculate approximately how long it will take, in seconds, to run the algorithm when \(n = 9500\). You should make your method and working clear.
3. Explain why your answer to part (b) is only an approximation.

1. 0.2
1.7
1.9
1.2
1.4
1.5
2.1
3.0
3.2
3.3

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.
2. 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 \(n\) numbers, the quick sort algorithm has, on average, order \(n \log n\).
   Given that it takes 2.32 seconds to run the algorithm when \(n = 450\)
3. calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when \(n = 11250\). You should make your method and working clear.