8.1 Algorithms (OCR A Level Computer Science)

A second example of a searching algorithm is a linear search.

Describe how a linear search works.

The pseudocode function binarySearch() performs a binary search on the array dataArray that is passed as a parameter. The function returns the array index of searchValue within the array, and -1 if it is not in the array.

Identify one situation where a linear search is more appropriate than a binary search.

Hugh has written a recursive function called thisFunction() using pseudocode.

01 function thisFunction(theArray, num1, num2, num3)

02 result = num1 + ((num2 - num1) DIV 2)

03  if num2 < num1 then

04   return -1

05  else

06   if theArray[result] < num3 then

07    return thisFunction(theArray, result + 1, num2, num3)

08   elseif theArray[result] > num3 then

09    return thisFunction(theArray, num1, result - 1, num3)

10   else

11    return result

12   endif

13  endif

14 endfunction

The function DIV calculates integer division, e.g. 5 DIV 3 = 1

State the name of the standard algorithm thisFunction() performs.

The programmer needs to use a merge sort in one part of the problem to sort items in ascending order.

Give one benefit and one drawback of the programmer using a merge sort instead of a bubble sort.

Explain why a quicksort is known as a divide and conquer algorithm.

The following pseudocode procedure performs an insertion sort on the array parameter.

01 procedure insertionSort(dataArray:byRef)

02  for i = 1 to dataArray.Length - 1

03   temp = dataArray[i]

04   tempPos = i – 1

05   exit = false

06   while tempPos >= 0 and exit == false

07    if dataArray[tempPos] < temp then

08     dataArray[tempPos + 1] = dataArray[tempPos]

09     tempPos = tempPos - 1

10    else

11     exit = true

12    endif

13   endwhile

14   dataArray[tempPos + 1] = temp

15  next i

16 endprocedure

State whether the procedure insertionSort sorts the data into ascending or descending order and explain your choice.

A fourth sorting algorithm is a bubble sort.

Describe how a bubble sort will sort an array of 10 elements.

The programmer needs to use a merge sort in one part of the problem to sort items in ascending order.

Describe how a merge sort works.

A program designer needs to decide on an algorithm to use from a choice of three. The table shows the worst-case Big O complexities for each algorithm.

The program will be used to analyse data that can range from 2 items to 2 billion items.

Compare the use of all three algorithms and suggest which the programmer should use.

You should include the following in your answer:

• the meaning of constant, logarithmic, linear and exponential complexity

• how well each algorithm scales as the amount of data increases

• which algorithm is the most suitable for the given task.

A tree is one example of a data structure.

A graph is another type of data structure.

An example graph is shown in Fig. 1.

Show how Dijkstra’s algorithm can be used on the graph shown in Fig. 1 to find the shortest path from start node A to end node G.

You must state the nodes on the final path and the distance of this path. Show your working.

You may use the table below to give your answer.

Final path: ...............................................

Distance: ................................................

Compare the use of merge sort, quick sort and insertion sort on an array with a small number of elements, and on an array with a very large number of elements.

You should make reference to the time complexities of each algorithm using the Big O notation in your answer.