2.3.1. Algorithms exam questions

Describe the purpose of this algorithm.(2)

Answer explanation

Answer:

• To locate an item (1) in a list (1). The list is in some order (1).

Tags

Algorithms

binary search

Parameters are passed to this function. Complete the following table to identify these parameters and the purpose of each. (8)

Answer explanation

Answer:

• A (1 AO – 1.2) the list to be searched (1 – AO 2.1).

• Value (1 – AO 1.2) the item being searched for (1 – AO 2.1).

• Low (1 AO – 1.2) the lower end of the list / sublist (1 – AO 2.1).

• High (1 AO – 1.2) the upper end of the list / sublist (1 – AO 2.1).

Tags

Algorithms

binary search

Describe what is meant by recursion. (2)

Answer explanation

• The function calls itself (1) from within the function.

Tags

Algorithms

binary search

Explain how the algorithm in Fig.2 is an example of a divide and conquer approach. (3)

Answer explanation

• Answer:

  • Divide and conquer splits a big problem into smaller parts (1). This algorithm repeatedly splits the list (1) in half (1) which reduces the amount of searching (1).

Tags

Algorithms

binary search

divide and conquer

Rewrite the algorithm in Fig.2 without using recursion. Annotate your pseudocode with comments to show how it solves the problem. (8)

Answer explanation

• Answer: Individual steps in pseudocode:
  

  • Function declaration

  • Parameters all given correctly

  • Found flag used

  • Mid-point found

  • Check if value found is greater than looked for value

  • Check if value found is less than mid value

  • Mid-point adjusted

  Programming marks to be awarded as follows:
  

  • Function declaration with parameters all given correctly (1 – AO 3.2)

  • Found flag and midpoint (1 – AO 3.2)

  • Checks if value found is greater or less than looked for value (1 – AO 3.2)

  • Mid-point adjusted within a loop (1 – AO 3.2)

  Possible annotated comments:
  

  • An If is used to catch an unordered list (1 – AO 2.2).

  • A WHILE loop deals with the logic that tests the binary search conditions without needing to use recursion (1 – AO 2.2) by reiterating through the conditions (1 – AO 2.2).

  • A found flag is used as the exit condition of the loop so that when the number is found the loop ends (1 – AO 2.2).

  Accept other valid annotations.

Tags

Algorithms

binary search

re-writing algorithm

Explain two reasons why they might use the new flight path in the simulation before implementing it in the real world. (4)

Answer explanation

Answer: 1 mark per bullet
e.g.

• It is safer… (1)

• …Real planes / lives are not put at risk by testing it in reality (1)

• Time can be sped up / decreased … (1)

• … do not need to wait to see what happens, can view changes immediately (1)

• It will cost less… (1)

• …Can make multiple changes / test all possibilities (1)

Tags

performance modelling

The board shown in Fig 2.1 is a visualisation of the problem. Explain what visualisation means in this example. (2)

Answer explanation

Answer: 2 marks, 1 for defining visualisation, 1 for application to the 2-d array and gridd

• Presents data in an easy-to-grasp way (1)

• An array is not actually a grid / table (1)

Tags

Visualisation

State the purpose of Big O notation.(1)

Answer explanation

Answer: i)1 from

• Evaluate the complexity of the algorithm (1)

• Show how the time / memory / resources increase as the data size increases (1)

• Evaluate worst case scenario for the algorithm (1)

Tags

Big O notation

State whether a binary search or a linear search would be the most appropriate method to search for a specific card, and justify your answer. (3)

Answer explanation

Answer: 1 mark for linear search, 2 for justification
Justification:

• The array is not sorted (1)

• Linear does not need ordered / linear goes through all elements from beginning / binary needs a sorted array (1)

Tags

Linear search

binary search

Show how an insertion sort would sort the array in Fig 4.1 into the correct order. Draw the array after each move. (3)

Answer explanation

Answer: i) 1 mark for each set of 2 moves

• 02174356
  01274356 (1)

• 01247356
  01234756 (1)

• 01234576

• 01234567 (1)

Tags

insertion sort