Designing, Creating and Refining Algorithms

1 State two differences between a function and a procedure. 2

One mark for each of the following, to a maximum of 2.

• A function returns a value to the calling code
• A procedure carries out a task without returning a value

Model answer. A function returns a value to the part of the program that called it, so its result can be assigned to a variable or used in an expression. A procedure performs a task, such as displaying a menu, but does not return any value to the calling code.

2 Complete a trace table for the following algorithm and state the final output. total = 0, then for i = 1 to 5: if i MOD 2 == 0 then total = total + i, next i, then print(total) 4

One mark for each of the following, to a maximum of 4.

• Identifies that the condition selects even values of i
• Shows total updating to 2 when i is 2
• Shows total updating to 6 when i is 4
• States the final output is 6

Model answer. The loop runs with i taking the values 1, 2, 3, 4 and 5. The condition i MOD 2 equals 0 is only true when i is even, so total is only updated on those iterations. When i is 1 the condition is false and total stays 0. When i is 2 the condition is true so total becomes 0 plus 2, which is 2. When i is 3 the condition is false and total stays 2. When i is 4 the condition is true so total becomes 2 plus 4, which is 6. When i is 5 the condition is false and total stays 6. The final output is therefore 6.

3 A student writes an algorithm to find the largest number in an array of 10 values, but it always outputs 0. The line largest = 0 is used before the loop and the array contains negative numbers. Identify the error and describe how to correct it. 3

One mark for each of the following, to a maximum of 3.

• The error is initialising largest to 0
• All the values are negative, so none is greater than 0 and largest is never replaced
• Correct by initialising largest to the first element of the array

Model answer. The error is that largest is initialised to 0 before the loop begins. Because every value in the array is negative, no element is ever greater than 0, so the comparison inside the loop is never true and largest is never updated, which is why 0 is always output. The correction is to initialise largest to the first element of the array, using largest = numbers[0], and then loop from the second element onwards. This guarantees that largest always holds a value that actually appears in the array, so the algorithm works correctly regardless of whether the values are positive or negative.

4 Write an algorithm, using pseudocode, that asks the user for 5 numbers, stores them in an array, and then outputs the average. 6

One mark for each of the following, to a maximum of 6.

• Declares an array to hold 5 values
• Uses a count controlled loop to run 5 times
• Takes input inside the loop and stores it in the array
• Maintains a running total
• Divides the total by 5 to find the average
• Outputs the average

Model answer. array numbers[5] total = 0 for i = 0 to 4 numbers[i] = input("Enter a number") total = total + numbers[i] next i average = total / 5 print("The average is " + average) The array is declared with five elements, which have indexes 0 to 4. A count controlled loop runs five times, taking a number from the user on each pass, storing it at the current index and adding it to a running total. After the loop finishes, the total is divided by 5 to give the average, which is then output.

5 Explain what is meant by making an algorithm more efficient, and give two ways an algorithm could be made more efficient. 4

One mark for each of the following, to a maximum of 4.

• Efficiency means producing the same result using fewer steps or less memory
• First method such as exiting a search early when the item is found
• Second method such as moving a calculation outside a loop when the value does not change
• Or using a more efficient algorithm such as binary search instead of linear search

Model answer. Making an algorithm more efficient means changing it so that it produces exactly the same correct result while using fewer steps, less memory, or both. One way is to exit a loop as soon as the work is complete: a linear search that stops the moment the target value is found avoids checking every remaining element, which on average halves the number of comparisons. A second way is to move any calculation whose result does not change out of a loop and perform it once before the loop starts, since repeating an identical calculation on every iteration is wasted work. A third and often much more significant improvement is to select a fundamentally better algorithm, for example replacing a linear search with a binary search on sorted data, which reduces the number of comparisons on a list of a million items from up to a million down to about twenty.