IGCSE CS: 7.4 Standard Methods of Solution

Objectives: Students should be able to —

1 Use the standard method of Counting.
2 Use the standard method of Totalling.
3 Find maximum, minimum and average values.
4 Search using a Linear search.
5 Sort using a Bubble sort.

Counting, Totalling, Maximum, Minimum & Average

The total weight is stored in a variable Total, the number of baskets in BasketCount, the maximum in Max, the minimum in Min and the average in Avg.

(a) Totalling:

Initialize the variable Total with value 0, to start totalling from it (like, Total ← 0).
Totalling is done by adding new weight of the basket to the previous old total weight and storing it in the same variable Total, replacing its previous value, during the process of inputting the weight.

Example: Total ← Total + Weight

Counting:

Initialize the variable BasketCount with value 0, to start counting from it (like, BasketCount ← 0).
Counting is done by adding 1 to the previous number of baskets and storing it in the same variable BasketCount, replacing its previous value, during the process of inputting the weight.

Example: BasketCount ← BasketCount + 1

(b) Maximum:

Initialize the variable Max to the lowest possible value (like, Max ← 0).
Check if the current new weight of the basket is greater than the previous maximum value; if so, store the new weight in the same variable Max, replacing its previous value, during the process of inputting the weight.

Example: IF Weight > Max THEN Max ← Weight

Minimum:

Initialize the variable Min to the highest possible value (like, Min ← 1000).
Check if the current new weight of the basket is less than the previous minimum value; if so, store the new weight in the same variable Min, replacing its previous value, during the process of inputting the weight.

Example: IF Weight < Min THEN Min ← Weight

Calculate the running total of the weight and count the number of baskets during the process of inputting the weight.
To calculate average, divide the total weight by the number of baskets (outside the loop).

Example: Avg ← Total / BasketCount

Given pseudocode:

01 A ← 0 02 B ← 0 03 C ← 0 04 REPEAT 05 REPEAT 06 INPUT D 07 UNTIL D > 0 AND D < 100 AND D = INT(D) 08 IF D > B 09 THEN 10 B ← D 11 ENDIF 12 C ← C + D 13 A ← A + 1 14 UNTIL A >= 25 15 B ← C / A 16 OUTPUT "Largest number is ", B 17 OUTPUT "Average is ", E

Operation	Line No.	Statement
Totalling	Line 12	C ← C + D
Counting	Line 13	A ← A + 1
Range check	Line 07	UNTIL D > 0 AND D < 100
Calculating the average	Line 15	B ← C / A

⚠ Note: Line 17 outputs the variable E for the average, but the average is actually stored in B (line 15). This is a bug — line 17 should read OUTPUT "Average is ", B.

(a) Find highest and lowest mark of 15 students:

Highest ← 0 Lowest ← 100 FOR Count ← 1 TO 15 INPUT "Enter the mark :", Mark IF Mark > Highest THEN Highest ← Mark IF Mark < Lowest THEN Lowest ← Mark NEXT Count OUTPUT "The highest mark scored by students is ", Highest OUTPUT "The lowest mark scored by students is ", Lowest

(b) Count students sharing the highest and lowest marks:

Highest ← 0 Lowest ← 100 HighCount ← 0 LowCount ← 0 FOR Count ← 1 TO 15 INPUT "Enter the mark :", Mark IF Mark = Highest THEN HighCount ← HighCount + 1 IF Mark > Highest THEN Highest ← Mark HighCount ← 1 ENDIF IF Mark = Lowest THEN LowCount ← LowCount + 1 IF Mark < Lowest THEN Lowest ← Mark LowCount ← 1 ENDIF NEXT Count OUTPUT "There are ", HighCount, " students with the highest mark of ", Highest OUTPUT "There are ", LowCount, " students with the lowest mark of ", Lowest

Variables to use:

Temp — to input and store the temperature.
X — counter variable for the loop structure.
MaxTemp, MinTemp and Avg — to find/calculate the maximum, minimum and average temperature.
CountTemp — to count the temperature readings less than or equal to 0.

MaxTemp ← -50 MinTemp ← 50 CountTemp ← 0 Sum ← 0 //' Repeat 8 times to input temperature at an interval of 3 hours //' for the 24-hour day (i.e. 24 / 3 = 8) FOR X ← 1 TO 8 INPUT "Enter the temperature : ", Temp IF Temp > MaxTemp THEN MaxTemp ← Temp IF Temp < MinTemp THEN MinTemp ← Temp IF Temp <= 0 THEN CountTemp ← CountTemp + 1 Sum ← Sum + Temp NEXT X Avg ← Sum / 8 OUTPUT "The maximum temperature of the day is ", MaxTemp OUTPUT "The minimum temperature of the day is ", MinTemp OUTPUT "The average temperature of the day is ", Avg OUTPUT CountTemp, "-times the temperature was less than or equal to 0."

Linear Search

Linear Search: The method of checking each item of the list in turn to see if the item matches the value searched for.

'// Setting a variable as flag, to indicate if the name has been found TRUE or FALSE. Found ← "FALSE" Counter ← 1 INPUT "Please enter the name to find - ", Name REPEAT IF StdName[Counter] = Name THEN Found ← "TRUE" ELSE Counter ← Counter + 1 ENDIF UNTIL Found = "TRUE" OR Counter > ClassSize IF Found = "TRUE" THEN OUTPUT Name, " found at position ", Counter, " in the list." ELSE OUTPUT Name, " not found." ENDIF

How it works: A flag variable Found tracks whether the name has been matched. The loop walks the array one element at a time until either the name is matched or the end of the array is reached.

NumOfPass ← 0 FOR Counter ← 1 TO ClassSize IF StdMark[Counter] >= 60 THEN NumOfPass ← NumOfPass + 1 ENDIF NEXT Counter OUTPUT NumOfPass, " students have passed in their exam."

This uses a linear traversal of the array with a counter that increments only when each mark satisfies the pass condition (StdMark[Counter] >= 60).

Highest ← 0 Lowest ← 100 FOR Counter ← 1 TO 25 '// Find and store the highest mark and its position '// in the array (i.e. the index value of the array) IF StdMark[Counter] > Highest THEN Highest ← StdMark[Counter] HighIndex ← Counter ENDIF '// Find and store the lowest mark and its position '// in the array (i.e. the index value of the array) IF StdMark[Counter] < Lowest THEN Lowest ← StdMark[Counter] LowIndex ← Counter ENDIF NEXT Counter OUTPUT StdName[HighIndex], " scored the highest mark of ", Highest OUTPUT StdName[LowIndex], " scored the lowest mark of ", Lowest

By storing the index (position) of the highest and lowest marks in HighIndex and LowIndex, we can later look up the matching name in the parallel StdName[] array.

Bubble Sort

Bubble Sort is an algorithm for arranging a series of numbers or other elements in the correct order.
The method works by comparing each set of adjacent elements of the entire list, from left to right, swapping their positions if they are out of order.
The algorithm then repeats this process until it can run through the entire list without swapping any elements.

(a) Sort 25 integers in ascending order:

DECLARE Num : ARRAY[1:25] OF Integer '' Input and store 25 integers in an array. FOR X ← 1 TO 25 INPUT Num[X] NEXT X '' Sort the numbers by swapping the integers between the '' elements of the array, if the value of the next element '' is less than the current element. REPEAT '' Setting a variable "Swap" as a flag, to indicate '' whether swapping of elements is made or not. '' Swap = 0 means, no numbers swapped, Swap = 1 means swapped. Swap ← 0 '' Repeat one time less than the size of the array '' (i.e. 25 - 1 = 24), as we compare the current value '' with the next value of the array element. FOR Y ← 1 TO 24 IF Num[Y+1] < Num[Y] THEN Temp ← Num[Y] Num[Y] ← Num[Y+1] Num[Y+1] ← Temp Swap ← 1 ENDIF NEXT Y UNTIL Swap = 0 '' Output the numbers in ascending order from the sorted array. FOR Z ← 1 TO 25 OUTPUT Num[Z] NEXT Z

(b) Changes to sort in descending order:

Change the conditional statement —

IF Num[Y+1] < Num[Y]

IF Num[Y+1] > Num[Y]

which will swap the numbers only if the next number is greater than the present number.

This swapping of numbers has to be done repeatedly until no further swapping is needed, to sort it in descending order.

(a) Sort names in ascending order:

REPEAT Swap ← 0 FOR X ← 1 TO 4 IF PeopleName[X+1] < PeopleName[X] THEN Temp ← PeopleName[X] PeopleName[X] ← PeopleName[X+1] PeopleName[X+1] ← Temp Swap ← 1 ENDIF NEXT X UNTIL Swap = 0 FOR Y ← 1 TO 5 OUTPUT PeopleName[Y] NEXT Y

(b) Initial contents of PeopleName[]:

Index	[1]	[2]	[3]	[4]	[5]
Value	Daniel	Alex	Jose	Bob	Monty

Trace table (each pass through the inner loop):

(" means the value is unchanged from the previous row.)

Loop Counter	[1]	[2]	[3]	[4]	[5]	Temp	Swap
	Daniel	Alex	Jose	Bob	Monty	—	0
1	Alex	Daniel	"	"	"	Daniel	1
2	"	"	"	"	"	"	"
3	"	"	Bob	Jose	"	Jose	1
4	"	"	"	"	"	"	"
	Alex	Daniel	Bob	Jose	Monty	"	0
1	"	"	"	"	"	"	"
2	"	Bob	Daniel	"	"	Daniel	1
3	"	"	"	"	"	"	"
4	"	"	"	"	"	"	"
	Alex	Bob	Daniel	Jose	Monty	"	0
1	"	"	"	"	"	"	"
2	"	"	"	"	"	"	"
3	"	"	"	"	"	"	"
4	"	"	"	"	"	"	"

Content of array PeopleName[] after sorting:

Index	[1]	[2]	[3]	[4]	[5]
Value	Alex	Bob	Daniel	Jose	Monty

Change the conditional statement —

IF PeopleName[X+1] < PeopleName[X]

IF PeopleName[X+1] > PeopleName[X]

which will swap the names only if the next name is greater than the present name.

This swapping of names has to be done repeatedly until no further swapping is needed, to sort it in descending order.

Revision: Statements and Key Computing Terms

Statement	Key Term
The method of keeping a running sum of values as they are entered.	Totalling
The method of keeping a running count of how many items have been entered.	Counting
The process of finding the largest value in a list of values.	Finding Maximum
The process of finding the smallest value in a list of values.	Finding Minimum
The sum of all values divided by the number of values.	Average (Mean)
A variable used to signal whether a condition (e.g. "found") is TRUE or FALSE.	Flag
A method of checking each item of a list in turn to see if it matches the value searched for.	Linear Search
An algorithm that arranges elements by comparing adjacent pairs and swapping them if they are out of order.	Bubble Sort
The act of exchanging the values of two variables (often using a temporary variable).	Swapping
The position number of an element within an array.	Index
A single run through a loop's body.	Iteration (Pass)