7.03d Order of algorithm: dominant term and scaling run-times

7 Mr Rank and Miss File need to sort a pile of examination scripts into increasing order of mark. Mr Rank first goes through the pile of scripts and puts each script into one of two piles, depending on whether the mark is below 50 or not. He then sorts the scripts in the 'below 50 ' pile and Miss File sorts the scripts in the '50 and above' pile. At the end they put the two sorted piles together again.

1. The scripts in the 'below 50' pile have the following marks, starting from the top of the pile. $$\begin{array} { l l l l l l l l } 34 & 42 & 27 & 31 & 12 & 48 & 24 & 37 \end{array}$$ Use bubble sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. Give the number of swaps and the number of comparisons that were used in sorting this list.
2. The scripts in the '50 and above' pile have the following marks, starting from the top of the pile. $$\begin{array} { l l l l l l l l } 95 & 74 & 61 & 87 & 71 & 82 & 53 & 57 \end{array}$$ Use shuttle sort to sort this list into increasing order. Clearly indicate the list that results at the end of each pass through the algorithm. List the number of swaps and number of comparisons that were used in sorting this list.
3. Explain why splitting the original list into two piles is a linear order algorithm.
4. Both bubble sort and shuttle sort are quadratic order algorithms. Mr Rank and Miss File use their method to sort a pile of 100 scripts. It takes about 50 seconds to split the pile and about 250 seconds to do each sort. As the sorts are done at the same time, this gives a total time taken of about 300 seconds, or 6 minutes. Approximately how long would Mr Rank and Miss File take to split a pile of 500 scripts into two roughly equal piles and sort the piles? Show all your working.
   [0pt] [4]

2 The following algorithm acts on a list of three or more numbers.
Step 1: Set both X and Y equal to the first number on the list.
Step 2: If there is no next number then go to Step 5.
Step 3: If the next number on the list is bigger than X then set X equal to it. If it is less than Y then set Y equal to it. Step 4: Go to Step 2.
Step 5: Delete a number equal to X from the list and delete a number equal to Y from the list.
Step 6: If there is one number left then record it as the answer and stop.
Step 7: If there are two numbers left then record their mean as the answer and stop.
Step 8: Go to Step 1.

1. Apply the algorithm to the list \(5,14,153,6,24,2,14,15\), counting the number of comparisons which you have to make.
2. Apply the algorithm to the list \(5,14,153,6,24,2,14\), counting the number of comparisons which you have to make.
3. Say what the algorithm is finding.
4. The order of the algorithm is quadratic. Explain what this means when it is applied to long lists.

2. In a television gameshow the names of 100 celebrities are listed in alphabetical order. A name is chosen at random from the list and a contestant has to guess which celebrity has been chosen. If the contestant is not correct, the host indicates whether the chosen name comes before or after the contestant's answer in the list and the contestant makes another guess. Each contestant knows all the names on the list and has to find the chosen name in as few guesses as possible.

1. Describe a strategy which would enable the contestant to find the chosen name in as few guesses as possible.
2. A large database with up to one million ordered entries is to be interrogated in the same way using appropriate software. Find the maximum number of interrogations that would be required for the software to find a particular entry and explain your answer.

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 .

2 A list is used to demonstrate how different sorting algorithms work.
After two passes through shuttle sort the resulting list is $$\begin{array} { l l l l l l l } 17 & 23 & 84 & 21 & 66 & 35 & 12 \end{array}$$

1. How many different possibilities are there for the original list? Suppose, instead, that the same sort was carried out using bubble sort on the original list.
2. Write down the list after two passes through bubble sort. The number of comparisons made is used as a measure of the run-time for a sorting algorithm.
3. For a list of six values, what is the maximum total number of comparisons made in the first two passes of
   1. shuttle sort
   2. bubble sort? Steve used both shuttle sort and bubble sort on a list of five values. He says that shuttle sort is more efficient than bubble sort because it made fewer comparisons in the first two passes.
   3. Comment on what Steve said. The number of comparisons made when shuttle sort and bubble sort are used to sort every permutation of a list of four values is shown in the table below.

      	Number of comparisons	3	4	5	6
      Shuttle sort	Number of permutations	2	6	8	8
      Bubble sort	Number of permutations	1	0	7	16

   4. Use the information in the table to decide which algorithm you would expect to have the quicker run-time. Justify your answer with calculations.

The memory requirements, in KB, for eight computer files are given below. 43 \quad 172 \quad 536 \quad 17 \quad 314 \quad 462 \quad 220 \quad 231 The files are to be grouped into folders. No folder is to contain more than 1000 KB, so that the folders are small enough to transfer easily between machines.

1. Use the first-fit method to group the files into folders. [3]
2. Use the first-fit decreasing method to group the files into folders. [3]

First-fit decreasing is a quadratic order algorithm.

1. A computer takes 1.3 seconds to apply first-fit decreasing to a list of 500 numbers. Approximately how long will it take to apply first-fit decreasing to a list of 5000 numbers? [2]

The following algorithm is a version of bubble sort. Step 1 \quad Store the values to be sorted in locations L(1), L(2), \(\ldots\) , L(n) and set i to be the number, n, of values to be sorted. Step 2 \quad Set j = 1. Step 3 \quad Compare the values in locations L(j) and L(j+1) and swap them if that in L(j) is larger than that in L(j+1). Step 4 \quad Add 1 to j. Step 5 \quad If j is less than i then go to step 3. Step 5 \quad Write out the current list, L(1), L(2), \(\ldots\) , L(n). Step 6 \quad Subtract 1 from i. Step 7 \quad If i is larger than 1 then go to step 2. Step 8 \quad Stop.

1. Apply this algorithm to sort the following list. 109 \quad 32 \quad 3 \quad 523 \quad 58. Count the number of comparisons and the number of swaps which you make in applying the algorithm. [4]
2. Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number. [2]
3. Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100 000 values? (Give your answer in hours and minutes.) [2]