Higher Computing - Standard Algorithms

Which of these standard algorithms do you need to be familiar with for Higher Computing Science?

• linear search

• find min/max

• count occurrences

• binary search

• minimax

Answer explanation

There are three standard algorithms you need to know about for Higher Computing Science: find min/max, count occurrences and linear search.

For which of these algorithms would it be best to use a conditional loop?

• linear search

• find min/max

• count occurrences

Answer explanation

A conditional loop woud be best for the linear search algorithm because there is no way of knowing where, or if, the search item will be found in the searched data.

In which of these algorithms is it necessary to process all the items in the data structure?

• linear search

• find min/max

• count occurrences

Answer explanation

In both find min/max and count occurrences algorithms it is necessary to check all the items in the array/list before the alsgorithm can complete.

Match each algorithm to its correct description ...

• looks for the largest or smallest value in the data

• input validation

• checks that input data meets necessary requirements

• find min/max

• looks to see if the search item appears in the data

• count occurrences

• return how many times the search item appears in the data

• linear search

Answer explanation

It's important that you know the purpose of each of these standard algorithms ...

The findMax algorithm is shown.

The findMin algorithm could also be implemented within the same FOR loop.

TRUE or FALSE?

• True

• False

Answer explanation

Yes, the same loop could be used to also find the smallest item.

Which of these algorithms also finds the location of the largest or smallest item of data?

• 
• 
• 

Answer explanation

An extra variable is required to store the index position of the max or min item. If there were several occurrences of the max or min item their index positions could be stored in an array.

What (exact) output will be produced by the procedure call

findMax()

if

numbers = [13, 19, 37, 9, 37, 42, 40, 41, 42, 21]

Answer explanation

42 is the largest value in the array (it doesn't matter that it appears twice in the list of numbers)

Which of the values of the numbers array would produce the output below?

The largest value was 5

• [5]

• [1, 2, 3, 4, 5]

• [45, 35, 25, 15, 5]

• [5, 5, 5, 5, 5]

• [5, 4, 3, 2, 1]

Answer explanation

Any of the arrays where the largest value is 5 (it doesn;t matter if 5 appears more than once in the array.)

What output will be produced by the procedure call

findMin()

if

numbers = [21, 29, 37, 19, 37, 42, 40, 19, 42, 21]

• The smallest value was 19 at position 3 in the list

• The smallest value was 19 at position 7 in the list

• The smallest value was 19 at position 4 in the list

• The smallest value was 19 at position 8 in the list

Answer explanation

This version of the findMin algorithm reports also the position of the smallest item.

Which of the values of the numbers array would produce the output below?

The smallest value was 0 at position 6 in the list

• [3, 3, 2, 2, 1, 1, 0, 0]

• [5, 4, 3, 2, 1, 0]

• [0, 3, 2, 1, 4, -1]

• [4, 7, 3, 2, 1, 6, 1, 0]

Answer explanation

There is only one array where 0 is the smallest item at position 6.