Algorithm Design and Problem-Solving
Time: 50 minutes Total Marks: 55
1 The Modulo-11 method of calculating a check digit for a sequence of nine digits is as follows:
each digit is given a weight depending on its position — the left-most digit has weight 10, the
next has weight 9, and so on down to weight 2. Each digit is multiplied by its weight and the
results are summed. The sum is divided by 11, and the remainder is subtracted from 11 to give
the check digit. If this value is 10, the check digit is the letter X.
The flowchart for this algorithm carries out the following steps in order: initialize Weighting to
10 and Total to 0; repeat nine times — input a digit, multiply it by the current weighting, add the
result to Total, and reduce the weighting by 1; then calculate the remainder of Total MOD 11;
calculate the check digit as 11 minus the remainder; and finally, if the check digit equals 10,
replace it with the letter X before the algorithm ends.
Write pseudocode for this algorithm. [9]
2 A problem is described in structured English as follows: [6]
REPEAT the following UNTIL the number input is zero
INPUT a number
Check whether the number is positive or negative
Increment the positive number count if the number is positive
Increment the negative number count if the number is negative
Write pseudocode for this algorithm.
3 A flowchart calculates the average of a list of numbers entered by the user. A rogue value of –
1 is used to stop input, and the flowchart carries out these steps: set RogueValue to –1, Total to
0 and Count to 0; input a number; while the number entered is not equal to the rogue value,
add 1 to Count, add the number to Total, and input the next number; once the rogue value is
entered, check whether Count is greater than 0, and if so calculate and output the Average as
Total divided by Count. [7]
Write pseudocode for this algorithm. You must use a WHILE loop.
4 Explain the difference between abstraction and decomposition as used in algorithm design.
Illustrate your answer with an example of each, based on the problem of planning a school
sports day. [4]
5 A program uses the following pseudocode to process five numbers entered by a user: [6]
Total ← 0
Count ← 0
FOR Index ← 1 TO 5
INPUT Number
IF Number > 10
THEN
Total ← Total + Number
Count ← Count + 1
ENDIF
NEXT Index
OUTPUT Total, Count
The five numbers entered, in order, are: 5, 12, 8, 15, 20
Complete the trace table below to show the values of Index, Number, Total and Count as the
algorithm executes.
Index Number Total Count
0 0
State the final values output for Total and Count.
6 A student has written the following pseudocode, which is intended to input 10 numbers and
output their total. The algorithm contains three errors. [3]
Total = 0
FOR Number ← 1 TO 10
INPUT Number
Total ← Total + Number
OUTPUT Total
Identify the three errors in this pseudocode.
7 The following algorithm uses a REPEAT...UNTIL loop to output the squares of the numbers 1
to 10: [3]
Count ← 1
REPEAT
OUTPUT Count * Count
Count ← Count + 1
UNTIL Count > 10
Rewrite this algorithm using a FOR loop so that it produces exactly the same output.
8 Write an algorithm, in pseudocode, that inputs an integer representing a student's
percentage mark. The algorithm must repeatedly ask the user to re-enter the value if it is not in
the range 0 to 100 inclusive, displaying a suitable error message each time, and must only
accept and output the mark once a valid value has been entered. [6]
9 An array Names[1:20] holds the names of 20 students. Write an algorithm, in pseudocode,
that performs a linear search for a name entered by the user (stored in Target), and outputs
either the position of the name in the array, or a message stating that the name was not found.
[7]
10 State the four basic constructs used to design algorithms. For each construct, give one line of
pseudocode as an example. [4]
Mark Scheme
Question 1 [9 marks]
Weighting ← 10
Total ← 0
Count ← 1
REPEAT
INPUT Digit
Value ← Digit * Weighting
Total ← Total + Value
Weighting ← Weighting - 1
Count ← Count + 1
UNTIL Count = 9
Remainder ← Total MOD 11
CheckDigit ← 11 - Remainder
IF CheckDigit = 10
THEN
CheckDigit ← "X"
ENDIF
OUTPUT CheckDigit
● 1 mark: Weighting, Total, Count initialised correctly
● 1 mark: correct loop construct that runs exactly 9 times
● 1 mark: INPUT Digit inside the loop
● 1 mark: Value ← Digit * Weighting
● 1 mark: Total ← Total + Value
● 1 mark: Weighting decremented each iteration
● 1 mark: Remainder ← Total MOD 11
● 1 mark: CheckDigit ← 11 - Remainder
● 1 mark: IF construct correctly converts a CheckDigit of 10 to "X"
Question 2 [6 marks]
PositiveCount ← 0
NegativeCount ← 0
INPUT Number
WHILE Number <> 0
IF Number > 0
THEN
PositiveCount ← PositiveCount + 1
ELSE
NegativeCount ← NegativeCount + 1
ENDIF
INPUT Number
ENDWHILE
● 1 mark: two counters initialised to zero
● 1 mark: INPUT before the loop and again inside the loop (or equivalent REPEAT structure)
● 1 mark: correct loop condition, terminating when Number = 0
● 1 mark: IF/ELSE/ENDIF construct testing Number > 0
● 1 mark: PositiveCount incremented correctly
● 1 mark: NegativeCount incremented correctly
● Accept an equivalent REPEAT...UNTIL Number = 0 structure with input inside the loop.
Question 3 [7 marks]
RogueValue ← -1
Total ← 0
Count ← 0
INPUT Number
WHILE Number <> RogueValue
Count ← Count + 1
Total ← Total + Number
INPUT Number
ENDWHILE
IF Count > 0
THEN
Average ← Total / Count
OUTPUT Average
ENDIF
● 1 mark: RogueValue, Total, Count initialised
● 1 mark: INPUT Number before the loop
● 1 mark: WHILE loop with condition Number <> RogueValue
● 1 mark: Count and Total updated inside the loop
● 1 mark: second INPUT Number inside the loop (to allow the loop to end)
● 1 mark: IF Count > 0 guard before calculating the average
● 1 mark: Average correctly calculated and output
Question 4 [4 marks]
● 1 mark: abstraction is filtering out/removing unnecessary detail, keeping only what is
relevant to solving the problem
● 1 mark: valid sports-day example of abstraction, e.g. ignoring weather-forecast detail and
focusing only on event timings and lane numbers
● 1 mark: decomposition is breaking a large problem down into smaller
sub-problems/modules
● 1 mark: valid sports-day example of decomposition, e.g. splitting the task into 'register
competitors', 'schedule events', 'record results'
Question 5 [6 marks]
Index Number Total Count
1 5 0 0
2 12 12 1
3 8 12 1
4 15 27 2
5 20 47 3
● Up to 4 marks for the completed table (allow 1 mark per correct row for the first four rows)
● 1 mark: final output stated correctly as Total = 47, Count = 3
● 1 mark: correct identification that 5 is not added to Total because it is not greater than 10
Question 6 [3 marks]
● Error 1: 'Total = 0' should be 'Total ← 0' (assignment operator, not '=')
● Error 2: the FOR loop variable is reused as the input variable (FOR Number ← 1 TO 10 ...
INPUT Number) — the loop counter is overwritten by the input, so it never reaches 10; a
separate loop variable (e.g. Count) is needed
● Error 3: missing 'NEXT Number' (or NEXT Count) to close the FOR loop
Question 7 [3 marks]
FOR Count ← 1 TO 10
OUTPUT Count * Count
NEXT Count
● 1 mark: FOR loop with correct start and end values (1 TO 10)
● 1 mark: OUTPUT Count * Count retained inside the loop
● 1 mark: NEXT Count included, producing identical output to the original algorithm
Question 8 [6 marks]
REPEAT
INPUT Mark
IF Mark < 0 OR Mark > 100
THEN
OUTPUT "Invalid mark, please re-enter"
ENDIF
UNTIL Mark >= 0 AND Mark <= 100
OUTPUT Mark
● 1 mark: REPEAT...UNTIL (or WHILE loop with pre-input) used so that input happens at least
once
● 1 mark: INPUT Mark inside the loop
● 1 mark: correct validation condition (Mark < 0 OR Mark > 100 / Mark >= 0 AND Mark <= 100)
● 1 mark: suitable error message output when the value is invalid
● 1 mark: UNTIL/WHILE condition correctly causes the loop to repeat until a valid value is
entered
● 1 mark: valid Mark output once outside the loop
Question 9 [7 marks]
Found ← FALSE
Index ← 1
WHILE Index <= 20 AND Found = FALSE
IF Names[Index] = Target
THEN
Found ← TRUE
ELSE
Index ← Index + 1
ENDIF
ENDWHILE
IF Found = TRUE
THEN
OUTPUT "Found at position ", Index
ELSE
OUTPUT "Not found"
ENDIF
● 1 mark: Found flag and Index initialised correctly
● 1 mark: loop condition checks both that Index is in range and that the item has not yet been
found
● 1 mark: correct comparison Names[Index] = Target
● 1 mark: Found set to TRUE when a match is located
● 1 mark: Index incremented only when no match is found on that iteration
● 1 mark: IF/ELSE construct after the loop to decide which message to output
● 1 mark: correct output of position when found, and 'not found' message when the target is
absent
Question 10 [4 marks]
● Sequence — instructions carried out one after another in order, e.g. Total ← Total + Number
● Selection — a choice is made between one or more paths, e.g. IF Age >= 18 THEN OUTPUT
"Adult" ENDIF
● Iteration (repetition) — a set of instructions repeated, e.g. FOR Count ← 1 TO 10 ... NEXT
Count
● Assignment — a value is stored in a variable, e.g. Total ← 0
● 1 mark for each construct correctly named with a valid pseudocode example (accept
alternative correct examples)