Gallery

csH2019paper

about this doc

section 1

section 2

Explore

section 1

q-10 software development

2019 computing science higher

about this question

This question features some code for a search algorithm. Here is what you need to do:

read a standard algorithm: linear search and predict the output

look for inefficient code and improve it

predict the output for using a test value which causes an error, identify the error and explain it

There are additional notes at the end of this page which are not part of the question but will help to develop your understanding.

local variables and scope of a variable, including code efficiency

how a function is defined and called

choosing to use a function or a procedure

You can also run and edit code in the replit project included on this page to explore the question and better understand the concepts

⁠

intro to question

A shop has a unique product code for each item it sells, for example X756.

The linear search algorithm shown below is used to find the position of a product code in an array.

01 FUNCTION linearSearch (ARRAY OF STRING list) RETURNS INTEGER

02 DECLARE position INITIALLY 0

03 DECLARE target INITIALLY ""

04 SEND "Enter target value" TO DISPLAY

05 RECEIVE target FROM KEYBOARD

06 FOR index FROM 0 TO length(list)-1 DO

07 IF target=list[index] THEN

08 SET position TO index

09 END IF

10 END FOR

11 RETURN position

12 END FUNCTION

The array of unique product codes is shown below.

| C232 | T546 | X756 | W482 | B629 | ... |

⁠

part a

State the value that will be returned by the function if target is X756.

(you can run the code to test this)

// state the value here

answer (part a)

the value would be 2

reading the code we can see that it searches each index position of the product list starting at 0

the value matching the target is at index 2, the third value as the array starts at 0

this position is the value the function returns

⁠

part b

This linear search algorithm is inefficient. (Why might it be inefficient?)

Describe how the algorithm could be made more efficient.

(you can edit the code to improve the efficiency, add comments to your code to explain)

// explain your improvement here

answer part b

the algorithm is not efficient since the search continues even after the target is found, any searching done after the target is found is a waste of processor time

it would be better if the search stopped as soon as the target is found

this could be done by replacing the for loop with a conditional loop which checks a found flag and stops if it is true

⁠

part c i

The product code ‘F333’ is entered. It is not in the array.

State the value returned by the function.

// state the value here

answer part ci

0 is returned

since the target is never matched in the array then position will never be changed from 0

part c ii

State the type of error. Explain your answer.

// name and describe the error here

(you can run the code to test this, and then explore a remedy to the bug, comment your code to explain)

answer part c ii

this is a logic error since the program produces a result but it is the wrong value

it is not a syntax error or the program could not compile, it is not a run time error or the program would crash

0 is incorrect since that would mean the target is found at the first value in the array which is incorrect

part c fix

the exam question does not ask for a fix but it is worth considering

// describe your fix here

answer part c fix

set the initial value of position to a dummy or sentinel value such as -1

-1 is not a real position so if the value of position is still -1 at then end then the value is not present

alternatively use a boolean variable as a found flag

⁠

project code

run the programs (expand for details)

enter X756, should be fine

then F333, will give found at 0 which is wrong

then C232, will also give 0 but would be correct

(You will need to fork the project to your own replit account to edit the code)

edit initial listPosition on line 18 to -1 and retest

⁠

Loading…⁠

⁠

additional notes

local variables and scope

position and target are local variables

they are declared within the function

the scope of the variables is within the function only, they cannot be accessed in other parts of the program

local variables in a function (or a procedure) is efficient, the variable do not use memory until the function is called

(a global variable can be accessed from anywhere in the program and uses memory at all times the program is running).

calling a function

the linearSearch function would be called like this

foundPosition = linearSeach(productCodeList)

the variable foundPosition will store the result of the function

the function name is on the right along with an actual parameter that matches the formal parameter on line 01.

function or procedure?

the data flow for this module is IN: list( ), OUT: position

the data flow matches the parameters and also the result when a function is involved

a module which has a single OUT value in dataflow is suitable to implement as a function since a function will return one result

the result could be a number or text but also a record or an array.

procedures handle dataflow IN/OUT via the parameters,

the data flow that is possible using parameters depends on the rules for each programming language