9.2 Algorithms (AS)
AS Level · 3 questions found
What this topic covers
Section titled “What this topic covers”- An algorithm is a solution expressed as defined steps
- Identifier tables; write pseudocode with input, process, output
- Three basic constructs: sequence, selection, iteration
- Document using structured English, flowcharts or pseudocode; convert between them
- Stepwise refinement; logic statements in algorithm design
Past paper questions
Section titled “Past paper questions” Q2
2
An algorithm has three steps. It will:
1.
repeatedly input a pair of numeric values A and B
2.
count the number of pairs that are input until A has been greater than B 10 times
3.
output the number of pairs that were input.
(a) Complete the program flowchart.
START
END
INPUT A, B
Yes
No
[5]
(b) Step 1 of the algorithm is changed.
A variable ThisSequence is used to enter a sequence of 10 pairs of numeric values, using
a single input statement.
Following the input of ThisSequence the revised algorithm will extract the pairs of numbers.
Describe the variable ThisSequence and how the numbers are extracted.
............................................................................................................................................. [2]
Show mark scheme
2(a) [2 marks]
One mark per outlined region:
1
Initialise both counts
2
Increment
every time a pair is input
Tries
3
Compare A > B
and
increment
if TRUE
Count
4
Test for Count = 10 (10
time A > B) – MUST include Yes / No labels
th
5
If so output
, otherwise loop
Tries
1
Initialise both counts
2
Increment
every time a pair is input
Tries
3
Compare A > B
and
increment
if TRUE
Count
4
Test for Count = 10 (10
time A > B) – MUST include Yes / No labels
th
5
If so output
, otherwise loop
Tries
2(b) [3 marks]
One mark per point:
1
A (variable of type) string will be input // by example e.g. “67,72”
2
A special / identified character would need to be used to separate each
numeric value // all numbers are fixed length
1
A (variable of type) string will be input // by example e.g. “67,72”
2
A special / identified character would need to be used to separate each
numeric value // all numbers are fixed length
Q6
6
Three points on a grid form a triangle with sides of length A, B and C as shown in the example:
y
Show mark scheme
6(a)
BOOLEAN
DECLARE Len1, Len2, Len3 : INTEGER
Len1
(x1 - x2) ^ 2 + (y1 - y2) ^ 2
Len2
(x1 - x3) ^ 2 + (y1 - y3) ^ 2
Len3
(x2 - x3) ^ 2 + (y2 - y3) ^ 2
IF (Len1 = Len2 + Len3) OR__
(Len2 = Len1 + Len3) OR__
(Len3 = Len1 + Len2) THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
Mark as follows:
1
Calculate the square of the length of at least one side
2
Calculation of all three lengths squared correctly
3
One
correct comparison of square of three lengths
4
All three
comparisons…
5
combined using logical operators / nested
// completely correct
IF
selection
6
Return result correctly in both cases
DECLARE Len1, Len2, Len3 : INTEGER
Len1
(x1 - x2) ^ 2 + (y1 - y2) ^ 2
Len2
(x1 - x3) ^ 2 + (y1 - y3) ^ 2
Len3
(x2 - x3) ^ 2 + (y2 - y3) ^ 2
IF (Len1 = Len2 + Len3) OR__
(Len2 = Len1 + Len3) OR__
(Len3 = Len1 + Len2) THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
Mark as follows:
1
Calculate the square of the length of at least one side
2
Calculation of all three lengths squared correctly
3
One
correct comparison of square of three lengths
4
All three
comparisons…
5
combined using logical operators / nested
// completely correct
IF
selection
6
Return result correctly in both cases
6(b) [2 marks]
1 mark for statement of problem:
Problem:
The function will return an incorrect value // the test will fail
1 mark for solution:
Solution:
Round the calculated values (to a known number of decimal places)
Define a threshold below which any difference can be ignored
Problem:
The function will return an incorrect value // the test will fail
1 mark for solution:
Solution:
Round the calculated values (to a known number of decimal places)
Define a threshold below which any difference can be ignored
Q2
2
A program is being developed.
(a) An algorithm for part of the program will:
•
input three numeric values and assign them to identifiers Num1, Num2 and Num3
•
assign the largest value to variable Ans
•
output a message giving the largest value and the average of the three numeric values.
Assume the values are all different and are input in no particular order.
Complete the program flowchart on page 5 to represent the algorithm.
START
END
INPUT Numl, Num2, Num3
Yes
No
[5]
(b) A different part of the program contains an algorithm represented by the following program
flowchart:
START
END
Set Flag to GetStat()
Set Port to 1
Is Flag =
TRUE ?
Is Port = 4 ?
Yes
No
No
Yes
CALL Reset(Port)
Set Port to Port + 1
Write pseudocode for the algorithm.
............................................................................................................................................. [5]
Show mark scheme
2(a) [5 marks]
Mark points
1
Condition for selecting one of the input numbers as largest value
2
… and assign to
Ans
3
Condition for selecting largest number for all three number input and
assigning to
Ans
4
Average calculated using
,
and
and stored in a variable.
Num1
Num2
Num3
Reject use of DIV
5
Output of
and average in output symbol / parallelogram
Ans
1
Condition for selecting one of the input numbers as largest value
2
… and assign to
Ans
3
Condition for selecting largest number for all three number input and
assigning to
Ans
4
Average calculated using
,
and
and stored in a variable.
Num1
Num2
Num3
Reject use of DIV
5
Output of
and average in output symbol / parallelogram
Ans
2(b) [4 marks]
Example solutions:
Flag
GetStat()
WHILE Flag <> TRUE
FOR Port
1 TO 3
CALL Reset(Port)
NEXT Port
Flag
GetStat()
ENDWHILE
Alternative:
REPEAT
Flag
GetStat()
IF Flag <> TRUE THEN
FOR Port
1 TO 3
CALL Reset(Port)
NEXT Port
ENDIF
UNTIL Flag = TRUE
One mark per point:
1
(Outer) conditional loop testing
Flag
2
Correct assignment of
from
in a loop
Flag
GetStat()
3
(Inner) loop checking / counting port // Check if
is different to 4
Port
4
… loop for 3 iterations
5
a call to
in a loop
Reset()
Flag
GetStat()
WHILE Flag <> TRUE
FOR Port
1 TO 3
CALL Reset(Port)
NEXT Port
Flag
GetStat()
ENDWHILE
Alternative:
REPEAT
Flag
GetStat()
IF Flag <> TRUE THEN
FOR Port
1 TO 3
CALL Reset(Port)
NEXT Port
ENDIF
UNTIL Flag = TRUE
One mark per point:
1
(Outer) conditional loop testing
Flag
2
Correct assignment of
from
in a loop
Flag
GetStat()
3
(Inner) loop checking / counting port // Check if
is different to 4
Port
4
… loop for 3 iterations
5
a call to
in a loop
Reset()