Deducing Original List Properties

A question is this type if and only if it asks the student to deduce properties of an original list based on the state after one or more passes of a sorting algorithm.

9 questions · Moderate -0.3

Sort by: Default | Easiest first | Hardest first
AQA D1 2012 January Q8
10 marks Standard +0.8
8 Four distinct positive integers are \(( 3 x - 5 ) , ( 2 x + 3 ) , ( x + 1 )\) and \(( 4 x - 13 )\).
  1. Explain why \(x \geqslant 4\).
  2. The four integers are to be sorted into ascending order using a bubble sort. The original list is \(\begin{array} { c c c c } ( 3 x - 5 ) & ( 2 x + 3 ) & ( x + 1 ) & ( 4 x - 13 ) \end{array}\) After the first pass, the list is \(( 3 x - 5 ) \quad ( x + 1 ) \quad ( 4 x - 13 ) \quad ( 2 x + 3 )\) After the second pass, the list is \(( x + 1 )\) \(( 4 x - 13 )\) \(( 3 x - 5 )\) \(( 2 x + 3 )\) After the third pass, the list is \(( 4 x - 13 ) \quad ( x + 1 )\) \(( 3 x - 5 )\) ( \(2 x + 3\) )
    1. By considering the list after the first pass, write down three inequalities in terms of \(x\).
    2. By considering the list after the second pass, write down two further inequalities in terms of \(x\).
    3. By considering the list after the third pass, write down one further inequality in terms of \(x\).
  3. Hence, by considering the results above, find the value of \(x\).
    \includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-19_2486_1714_221_153}
AQA D1 2011 June Q2
6 marks Easy -1.2
2 Five different integers are to be sorted into ascending order.
  1. A bubble sort is to be used on the list of numbers \(\quad 6 \quad 4 \quad 5 \quad x \quad 2 \quad 11\).
    1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } 4 & x & 2 & 6 & 11 \end{array}$$ Write down an inequality that \(x\) must satisfy.
    2. After the second pass, the list becomes $$\begin{array} { l l l l l } x & 2 & 4 & 6 & 11 \end{array}$$ Write down a new inequality that \(x\) must satisfy.
  2. The five integers are now written in a different order. A shuttle sort is to be used on the list of numbers \(\quad \begin{array} { l l l l l } 11 & x & 2 & 4 & 6 . \end{array}\)
    1. After the first pass, the list of numbers becomes $$\begin{array} { l l l l l } x & 11 & 2 & 4 & 6 \end{array}$$ Write down an inequality that \(x\) must satisfy.
    2. After the second pass, the list becomes $$\begin{array} { l l l l l } 2 & x & 11 & 4 & 6 \end{array}$$ Write down a further inequality that \(x\) must satisfy.
  3. Use your answers from parts (a) and (b) to write down the value of \(x\).
Edexcel D1 2017 June Q3
13 marks Moderate -0.8
3. \(\quad \begin{array} { l l l l l l l l l l } 42 & 21 & 15 & 16 & 35 & 10 & 31 & 11 & 27 & 39 \end{array}\)
  1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 65
  2. 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.
  3. Use the first-fit decreasing bin packing algorithm on your ordered list to pack the numbers into bins of size 65 The nine distinct numbers below are to be sorted into descending order $$\begin{array} { l l l l l l l l l } 23 & 14 & 17 & \boldsymbol { x } & 21 & 18 & 8 & 20 & 11 \end{array}$$ 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 $$\begin{array} { l l l l l l l l l } 23 & 17 & \boldsymbol { x } & 21 & 18 & 14 & 20 & 11 & 8 \end{array}$$ After the second complete pass, the list is $$\begin{array} { l l l l l l l l l } 23 & 17 & 21 & 18 & \boldsymbol { x } & 20 & 14 & 11 & 8 \end{array}$$
  4. Using this information, write down the smallest interval that must contain \(\boldsymbol { x }\). Give your answer as an inequality.
OCR FD1 AS 2017 December Q15
Challenging +1.2
15
4
12
23
14
OCR Further Discrete 2018 September Q2
8 marks Standard +0.8
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 comparisons3456
      Shuttle sortNumber of permutations2688
      Bubble sortNumber of permutations10716
    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.
Edexcel D1 2014 January Q11
Moderate -0.5
11
17
10
14
8
Edexcel D1 2014 January Q14
Moderate -0.5
14
8
13
6
4
Edexcel D1 2011 June Q1
9 marks Moderate -0.5
1.
1.Jenny
Edexcel D1 2011 June Q10
Easy -1.8
10. & Freya
A binary search is to be performed on the names in the list above to locate the name Kim.
  1. Explain why a binary search cannot be performed with the list in its present form.
  2. Using an appropriate algorithm, alter the list so that a binary search can be performed, showing the state of the list after each complete iteration. State the name of the algorithm you have used.
  3. Use the binary search algorithm to locate the name Kim in the list you obtained in (b). You must make your method clear.
    2. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-3_858_1169_244_447} \captionsetup{labelformat=empty} \caption{Figure 1}
    \end{figure}
    1. Define the terms
      1. tree,
      2. minimum spanning tree.
        (3)
      3. Use Kruskal's algorithm to find a minimum spanning tree for the network shown in Figure 1. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
        (3)
      4. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book.
    2. State whether your minimum spanning tree is unique. Justify your answer.
      (1)
      3. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-4_1492_1298_210_379} \captionsetup{labelformat=empty} \caption{Figure 2}
      \end{figure} Figure 2 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.
    3. Write down the inequalities that form region \(R\). The objective is to maximise \(3 x + y\).
    4. Find the optimal values of \(x\) and \(y\). You must make your method clear.
    5. Obtain the optimal value of the objective function. Given that integer values of \(x\) and \(y\) are now required,
    6. write down the optimal values of \(x\) and \(y\).
      4. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-5_623_577_287_383} \captionsetup{labelformat=empty} \caption{Figure 3}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-5_620_582_287_1098} \captionsetup{labelformat=empty} \caption{Figure 4}
      \end{figure} Figure 3 shows the possible allocations of five workers, Adam (A), Catherine (C), Harriet (H), Josh (J) and Richard (R) to five tasks, 1, 2, 3, 4 and 5. Figure 4 shows an initial matching.
      There are three possible alternating paths that start at A .
      One of them is $$A - 3 = R - 4 = C - 5$$
    7. Find the other two alternating paths that start at A .
    8. List the improved matching generated by using the alternating path \(\mathrm { A } - 3 = \mathrm { R } - 4 = \mathrm { C } - 5\).
    9. Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path used and your final matching.
      5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-6_835_913_219_575} \captionsetup{labelformat=empty} \caption{Figure 5
      [0pt] [The total weight of the network is 98 km ]}
      \end{figure} Figure 5 models a network of gas pipes that have to be inspected. The number on each arc represents the length, in km, of that pipe. A route of minimum length that traverses each pipe at least once and starts and finishes at A needs to be found.
    10. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
    11. Write down a possible shortest inspection route, giving its length. It is now decided to start the inspection route at D . The route must still traverse each pipe at least once but may finish at any node.
    12. Determine the finishing point so that the length of the route is minimised. You must give reasons for your answer and state the length of your route.
      6. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-7_823_1374_226_347} \captionsetup{labelformat=empty} \caption{Figure 6}
      \end{figure} Figure 6 shows a network of cycle tracks. The number on each arc gives the length, in km, of that track.
    13. Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.
    14. Explain how you determined your shortest route from your labelled diagram. The track between E and F is now closed for resurfacing and cannot be used.
    15. Find the shortest route from A to H and state its length.
      (2)
      7. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{f7a968b0-18dd-44cf-b934-4beb8f2290ac-8_798_1497_258_283} \captionsetup{labelformat=empty} \caption{Figure 7}
      \end{figure} A project is modelled by the activity network shown in Figure 7. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
    16. Complete the precedence table in the answer book.
      (3)
    17. Complete Diagram 1 in the answer book, to show the early event times and late event times.
    18. State the critical activities.
    19. On the grid in your answer book, draw a cascade (Gantt) chart for this project.
    20. By considering the activities that must take place between time 7 and time 16, explain why it is not possible to complete this project with just 3 workers in the minimum time.
      8. A firm is planning to produce two types of radio, type A and type B. Market research suggests that, each week:
      Each type A radio requires 3 switches and each type B radio requires 2 switches. The firm can only buy 200 switches each week. The profit on each type A radio is \(\pounds 15\).
      The profit on each type B radio is \(\pounds 12\).
      The firm wishes to maximise its weekly profit.
      Formulate this situation as a linear programming problem, defining your variables.
      (Total 7 marks)