Algorithm Design and Standard Methods: Question 8

Worked solution

Part (a): Writing the maximum-value algorithm

The largest value found “so far” is tracked in MaxTemp, alongside MaxIndex recording where it was found, starting from the first element and comparing every element after it:

DECLARE Temp : ARRAY[1:6] OF INTEGER
DECLARE Index : INTEGER
DECLARE MaxTemp : INTEGER
DECLARE MaxIndex : INTEGER

MaxTemp ← Temp[1]
MaxIndex ← 1
FOR Index ← 2 TO 6
    IF Temp[Index] > MaxTemp THEN
        MaxTemp ← Temp[Index]
        MaxIndex ← Index
    ENDIF
NEXT Index
OUTPUT MaxTemp
OUTPUT MaxIndex

Mark-earning features: [1] MaxTemp initialised to Temp[1] and MaxIndex initialised to 1 before the loop; [1] the FOR loop correctly starting at Index ← 2 (not 1, since Temp[1] is already stored) and ending at 6; [1] the comparison IF Temp[Index] > MaxTemp THEN; [1] both MaxTemp and MaxIndex updated together inside that IF; [1] both MaxTemp and MaxIndex output once the loop ends.

Part (b): Tracing the algorithm

Starting values before the loop: MaxTemp ← Temp[1] = 14, MaxIndex ← 1.

MaxTemp and MaxIndex only change on Index 2 and Index 3, since no later value exceeds 23. The loop ends after Index 6, outputting MaxTemp = 23 and MaxIndex = 3.

Part (c): Number of comparisons and why it never varies

The FOR Index ← 2 TO 6 loop runs the IF Temp[Index] > MaxTemp comparison exactly once for each of Index 2, 3, 4, 5 and 6. 5 comparisons in total (one less than the 6 elements in the array, since Temp[1] is the starting value rather than a comparison).

This count is fixed and does not depend on where the maximum value happens to sit in the array. Unlike a linear search, which can stop the moment it finds the value it is looking for, a maximum-finding algorithm can never stop early: even after finding a large value at Index 3, it still has no way of knowing whether an even larger value is waiting later in the array, so it must compare every remaining element before it can be certain the true maximum has been found. If the maximum temperature had instead been at Index 6 (or even Index 2), the algorithm would still make exactly 5 comparisons, one for every element after the first.

Final answers

• (a) See the pseudocode algorithm above.
• (b) MaxTemp reaches 23 (at Index 3, on the temperature array given) and stays there; final output MaxTemp = 23, MaxIndex = 3.
• (c) 5 comparisons; the count is always n − 1 because the algorithm must check every remaining element and cannot stop early like a linear search can.