Algorithm Design &

Problem Solving
[Link]
Program Development Life Cycle (PDLC)

• Analysis

• Design

• Coding

• Testing

• Maintenance
Analysis

• Before solving a problem, it is essential to define and document the problem clearly,
known as the "requirements specification" for the program.

• The analysis stage involves using tools like abstraction and decomposition to identify the
specific requirements for the program.

• Abstraction focuses on the essential elements needed for the solution while eliminating
unnecessary details and information.

• Decomposition involves breaking down complex problems into smaller, more manageable
parts that can be solved individually.

• Daily tasks can be decomposed into constituent parts for easier understanding and
solving.
Design

• The program specification derived from the analysis stage is used as a guide for
program development.

• During the design stage, the programmer should clearly understand the tasks to
be completed, the methods for performing each task, and how the tasks will
work together.

• Documentation methods such as structure charts, flowcharts, and pseudocode

can be used to document the program's design formally.
Coding and iterative testing

• The program or set of programs is developed based on the design.

• Each module of the program is written using a suitable programming language.

• Testing is conducted to ensure that each module functions correctly.

• Iterative testing is performed, which involves conducting modular tests, making code
amendments if necessary, and repeating tests until the module meets the required
functionality.
Testing

• The completed program or set of programs is executed multiple times using

various test data sets.

• This testing process ensures that all the tasks within the program work together
as specified in the program design.

• Running the program with different test data can identify and address potential
issues and errors.

• The testing phase aims to verify the overall functionality and performance of the
program by evaluating its behaviour with various inputs.
Structure Diagrams

• Every computer system is made up of sub-systems, which are in turn made up of further
sub-systems.

Structure Diagrams

• The breaking down of a computer system into sub-systems, then breaking each sub-
system into smaller sub-systems until each one only performs a single action.

• A structure diagram diagrammatically represents a top-down design. Example below.

Pseudocode & Flowcharts

• Pseudocode - Verbal representation of an

algorithm (a process or set of steps) and
flowcharts are a diagrammatic
representation.

• Flowcharts: A flowchart shows

diagrammatically the steps required to
complete a task and the order that they are
to be performed

• Algorithm: These steps, together with the

order, are called an algorithm
Pseudocode & Flowcharts (cont)

 An example of a flowchart is given below from a past paper

question in which all of the functions of a flowchart are shown:
 This flowchart’s task is to check if a rider’s height is more the
requirement (1.2) in this case. It then counts until the accepted
riders are 8. After they are 8, it outputs the number of rejected
riders and tells the rest that they are ready to go!
Pseudocode
• Declaration & Usage of Variables & Constants

o Variable – Store of data which changes during execution of the program (due to user input)

o Constant – Store of data that remains the same during the execution of the program

Basic Data Types

 Integer – Whole Number e.g. 2; 8; 100

o Real – Decimal Number e.g. 7.00; 5.64

o Char – Single Character e.g. a; Y

o String – Multiple Characters (Text) e.g. ZNotes; COOL

o Boolean – Only 2 Values e.g. True/False; Yes/No; 0/1

• Input & Output (READ & PRINT) – Used to receive and display data to the user respectively.

• (It is recommended to use input and output commands)

Pseudocode (cont)

 INPUT Name

 OUTPUT "Hello Mr." , Name

 // Alternatively //

 READ Name

PRINT "Hello Mr," , Name

• Declaration of variable - A variable/constant can be declared by the following manner

 DECLARE [Variable Name] : [DATATYPE OF VARIABLE]

• Array: Array is similar to variable but it can store multiple values of same datatype under single name

 DECLARE [ARRAYNAME] : ARRAY [Lower Limit : Upper Limit ] OF [DATATYPE]

• Assignment - Each variable is assigned using a left arrow.

 [VARIABLE NAME] <---- [Value to be assigned]

 ArrayName [IndexValue] <---- [Value to be assigned]

• Conditional Statements:

 IF…THEN…ELSE…ENDIF
Loop Structures:

• FOR…TO…NEXT : Will run for a determined/known amount of times

• REPEAT… UNTIL – Will run at least once till condition is satisfied; Verification is done after
running code

• WHILE…DO…ENDWHILE – May not ever run; Verification is done before running code
 Note: When using conditions in these loop structures and conditional statement, it has to be kept in mind that it can be done
in two ways.

1. use of a Boolean variable that can have the value TRUE or FALSE

2. comparisons made by using coparison operators, where comparisons are made from left to right

IF [BOOLEAN VARIABLE]

THEN

OUTCOME

ELSE

OUTCOME

ENDIF

IF ((CONDITION 1) OR ( CONDITION 2)) AND (CONDITION 3) AND (CONDITION 4)

THEN

OUTCOME

ELSE

OUTCOME

ENDIF
Standard methods used in algorithm:

Totalling Counting:

• Keeping a count of the number of times an action is

• Totalling means keeping a total that values performed is another standard method.
are added to
PassCount ← 0
Total ← 0 FOR Counter ← 1 TO LoopLimit

FOR Counter ← 1 TO LoopLimit INPUT Value

IF Value > Range

Total ← Total + ValueToBeTotalled
THEN
NEXT Counter
PassCount ← PassCount + 1

ENDIF

NEXT Counter
Standard methods used in algorithm: (cont)

• Maximum, minimum and average : Finding the IF Array[Counter] < MinimumValue

largest and smallest values in a list are two
standard methods that are frequently found in THEN
algorithms MinimumValue ← Array[Counter]
MaxiumumValue <--- Array[1] MinimumValue <--- ENDIF
Array[1]
NEXT Counter
FOR Counter ← 2 TO LoopLimit
IF Array[Counter] > MaximumValue // Average//
THEN Total ← 0

MaximumValue ← Array[Counter] FOR Counter ← 1 TO NumberOfValues

ENDIF Total ← Total + StudentMark[Counter]

NEXT Counter

Average ← Total / NumberOfValues

Linear Search

• Linear Search: In a linear search, each item in the Counter ← Counter + 1

list is inspected sequentially until a match is found
or the entire list is traversed. ENDIF

INPUT Value UNTIL Found OR Counter > NumberOfValues

Found ← FALSE IF Found
Counter ← 0 THEN
REPEAT OUTPUT Value , " found at position " , Counter, "
in the list."
IF Value = Array[Counter]

THEN
ELSE

Found ← TRUE OUTPUT Value , " not found."

ELSE ENDIF
Bubble Sort
• Bubble Sort: Iteratively compare and swap adjacent Temp ← Array[Index]
elements in a list to sort them. Start from the first element
and continue until the second-to-last element.
Array[Index] ← Array[Index + 1]
• After each pass, the last element is in its correct place.
However, other elements may still be unsorted. Array[Index + 1] ← Temp
• Repeat the process, excluding the last element, until only
one element remains or no swaps are needed. Swap ← TRUE
First ← 1 ENDIF
Last ← 10
NEXT Index
REPEAT
Last ← Last - 1
Swap ← FALSE

FOR Index ← First TO Last - 1 UNTIL (NOT Swap) OR Last = 1

IF Array[Index] > Array[Index + 1]

THEN
Test Data
• Test data refers to input values used to evaluate and assess the functionality and performance of a computer program or
system.

• It helps identify errors and assess how the program handles different scenarios

Normal Data

• Normal data is the test data which accepts values in acceptible range of values of the program

• Normal data should be used to work through the solution to find the actual result(s) and see if they are the same as the
expected result(s)

• e.g. in a program where only whole number values ranging from 0 to 100 (inclusive) are accepted, normal test data will
be : 23, 54, 64 , 2 and 100

Abnormal Data

• Test data that would be rejected by the solution as not suitable, if the solution is working properly is called abnormal
test data / erroneous test data.

• e.g. in a program where only whole number values ranging from 0 to 100 (inclusive) are accepted, abnormal data will
be: -1, 151, 200, 67.2, “Sixty-Two” and -520
Test Data (cont)

 Extreme Data

• Extreme data are the largest and smallest values that normal data can take

• e.g. in a program where only whole number values ranging from 0 to 100 (inclusive) are
accepted, extreme data will be: 0 and 100

 Boundary Data

• This is used to establish where the largest and smallest values occur

• At each boundary two values are required: one value is accepted and the other value is
rejected.

• e.g. in a program where only whole number values ranging from 0 to 100 (inclusive) are
accepted, one example of boundary data will be: 100 and 101. 100 will be accepted and 101 will
not be accepted
Trace Table
• A trace table is utilized to document the outcomes of every step in an algorithm. It is employed to record the
variable's value each time it undergoes a change.

• A dry run refers to the manual process of systematically executing an algorithm by following each step in
sequence.

• A trace table is set up with a column for each variable and a column for any output e.g.

• Test data is employed to execute a dry run of the flowchart and document the outcomes in a trace table.
During the dry run:

• • Whenever a variable's value changes, the new value is recorded in the respective column of the trace table.

• • Each time a value is outputted, it is displayed in the output column.

Trace table (example)
• An example of trace table is given below using a past paper question:

• Q: The flowchart below inputs the height of children who want to ride on a rollercoaster. Children
under 1.2 metres are rejected. The ride starts when eight children have been accepted.

• Complete the trace table for the input data: 1.4, 1.3, 1.1, 1.3, 1.0, 1.5, 1.2, 1.3, 1.4, 1.3, 0.9, 1.5, 1.6, 1.0
Trace table (example)
Riders Reject Height OUTPUT

0 0

1 1.4

2 1.3

1 1.1

3 1.3

2 1.0

4 1.5

3 1.2

5 1.3

6 1.4

7 1.3

4 0.9

8 1.5 Ready to go 4

• Trace tables can be used to trace errors in a program. For example, if the requirement for the previous
question would be to accept riders that are of height 1.2 too, rather than rejecting them, then the error
would have been caught in the trace table as when 1.2 is entered, it would increment rejected which it
shouldn’t in our example
How to write an algorithm?
 The ability to write an algorithm is very important for this syllabus and paper. Some key steps/points to be
known in-order to write the perfect algorithm are as follows:
1. Make sure that the problem is clearly understood which includes knowing the purpose of the algorithm and
the tasks to be completed by the algorithm.
2. Break the problem into smaller problems (e.g. in a program which outputs average values, divide the
problem into multiple ones i.e. how to count the number of iterations and how to count the total of all
values)
3. Identify the data that is needed to be saved into variables/constants/arrays and what datatype it is, and
declare all the variables/constants/arrays accordingly, with meaningfull names
4. Decide on how you are going to construct your algorithm, either using a flowchart or pseudocode. If you are
told how to construct your algorithm, then follow the guidance.
5. Construct your algorithm, making sure that it can be easily read and understood by someone else. Take
particular care with syntax e.g. when conditions are used for loops and selection.
6. Use several sets of test data (Normal, Abnormal and Boundary) to dry run your algorithm and check if the
expected results are achieved (a trace table can be used for this purpose) . If error is found, find the point of
error in the trace table and fix it in the code.
Note: The algorithms that you have looked at so far in these notes were not designed with readability in mind
because you needed to work out what the problem being solved was.
Validation and Verification

 To ensure the acceptance of reasonable and accurate data inputs, computer systems must
thoroughly examine each data item before accepting it, and this is where Validation and
Verification come into play!

Validation

 Validation in computer systems involves automated checks to ensure the reasonableness

of data before accepting it.

 If the data is invalid, the system should provide an explanatory message for rejection and
allow another chance to enter the data.
Validation (cont)

Length check
Range check
 This can either ensure that data consists of a precise number of characters.
 A range check verifies that a numerical value falls within specified upper and
lower limits. OUTPUT "Please enter your value of ", Limit , " characters "

REPEAT REPEAT
INPUT Value
INPUT Value
IF Value < MinimumValue OR Value > MaximumValue
IF LENGTH(Value) <> Limit
THEN
THEN
OUTPUT "The student's mark should be in the range", MinimumValue ," to ",
MaximumValue OUTPUT "Your value must be exactly" , Limit ," characters, please re-enter "
ENDIF
ENDIF
UNTIL Value >= MinimumValue AND Value <= MaximumValue
UNTIL LENGTH(Value) = Limit

It can also check if the data entered is a reasonable number of characters or not

OUTPUT "Please enter your value "

REPEAT

INPUT Value

IF LENGTH(Value) > UpperLimit OR LENGTH(Value) < LowerLimit

THEN

OUTPUT "Too short or too long, please re-enter "

ENDIF

UNTIL LENGTH(Value) <= UpperLimit AND LENGTH(Value) >= LowerLimit

Validation (cont)

Type check Presence check

 A type check verifies that the entered data
corresponds to a specific data type.  A presence check checks to ensure that some data has
been entered and the value has not been left blank
OUTPUT "Enter the value "
REPEAT OUTPUT "Please enter the value "
INPUT Value REPEAT
IF Value <> DIV(Value, 1)
INPUT Value
THEN
OUTPUT "This must be a whole number, please re- IF Value = ""
enter"
ENDIF THEN
UNTIL Value = DIV(Value, 1)
OUTPUT "*=Required "

ENDIF

UNTIL Value <> ""

Validation(cont)

Format Check
 A format check checks that the characters entered conform to a
pre-defined pattern.
Check Digit
 A check digit is the final digit included in a code; it is calculated
from all the other digits.
 Check digits are used for barcodes, product codes, International
Standard Book Numbers (ISBN), and Vehicle Identification Numbers
(VIN).
Verification
 Verification is checking that data has been accurately copied from one source to another

 There are 2 methods to verify data during entry ( there are other methods during data transfer, but they are in
paper 1)

1. Double Entry

• Data is inputted twice, potentially by different operators.

• The computer system compares both entries and if they differ, an error message is displayed, prompting the data to
be reentered.

2. Screen/Visual check

• A screen/visual check involves the user manually reviewing the entered data.

• After data entry, the system displays the data on the screen and prompts the user to confirm its accuracy before
proceeding.

• The user can compare the displayed data against a paper document used as an input form or rely on their own
knowledge to verify correctness.