Algorithms
Program Development Life Cycle
The development of a program involves multiple stages.
- Analysis: abstraction, decomposition of the problem, identification of the problem and requirements
- Design: decomposition, structure diagrams, flowcharts, pseudocode
- Coding: writing program code and iterative testing
- Testing: testing program code with the use of test data
Problem Solving
Every computer system made up of sub-systems which are made up of further sub-systems.
Analysis
Problems can be decomposed into 4 parts:
- inputs
- outputs
- processes
- storage
Design
Different methods can be used to contruct a solution to a problem such as:
- structure diagrams
- flowcharts
- pseudocode
Solution Methods
There are different methods that can be used to solve a problem such as:
- totalling
- counting
- linear search
- bubble sort
- finding the:
- minimum
- maximum
- average
Totalling
Totalling is done inside a loop. It is often used to calculate averages.
Total ← Total + Value
Counting
Counting is often done inside while loops and used to iterate through an array.
Counter ← Counter + 1
Linear Search
DECLARE Items : ARRAY Items[1] ← "alpha" Items[2] ← "bravo" Items[3] ← "charlie" Query ← "bravo" Found ← FALSE Index ← 1 REPEAT IF Items[Index] = Query THEN Found ← TRUE ELSE Index ← Index + 1 ENDIF UNTIL Found OR Index > 3 IF Found THEN OUTPUT Query, " found at index ", Index ENDIF
Bubble Sort
Bubble sort is used to sort an array in ascending or descending order. However, it can also sort an array of strings alphabetically. Some bubble sort algorithms may differ, but the core idea of swapping items is the same.
DECLARE Items : ARRAY Items[1] ← 6 Items[2] ← 9 Items[3] ← 4 Items[4] ← 2 Swapped ← TRUE N ← 4 WHILE N > 1 AND Swapped DO Swapped ← FALSE N ← N - 1 FOR Index ← 1 TO N IF Items[Index] > Items[Index + 1] THEN Temp ← Items[Index] Items[Index] ← Items[Index + 1] Items[Index + 1] ← Temp Swapped ← TRUE ENDIF NEXT ENDWHILE FOR Index ← 1 TO 4 OUTPUT Items[Index] NEXT
Statistics
DECLARE Numbers : ARRAY Numbers[1] ← 1 Numbers[2] ← 2 Numbers[3] ← 3 Numbers[4] ← 10 DECLARE Max ← -INFINITY DECLARE Min ← INFINITY DECLARE Avg Total ← 0 FOR Index ← 1 TO 4 IF Numbers[Index] > Max THEN Max ← Numbers[Index] ENDIF IF Numbers[Index] < Min THEN Min ← Numbers[Index] ENDIF Total ← Total + Numbers[Index] NEXT Avg ← Total / 4 OUTPUT Max OUTPUT Min OUTPUT Avg
Data Checks
Validation
Validation is an automated check carried out by a computer to make sure that data entered is acceptable. These checks include:
- range
- length
- type
- presence
- format
A check digit is also a form of validation.
Verification
Verification can be an automated or manual check carried out by a computer or a human to make sure that data entered is the same as the data that was intended to be input. These checks include:
- double-entry
- visual
Test Data
There are 4 different types of test data. Test data is used to check whether a program is working according to plan.
The table below shows the testing data for a program that only accepts positive numbers.
Type | Description | Example |
---|---|---|
Normal | Data that should be accepted | 10 |
Abnormal | Data that should be rejected | ten |
Extreme | Lowest or highest acceptable values | 1 |
Boundary | Lowest or highest acceptable and unacceptable values | 0, 1 |
Trace Table
A trace table shows the state of an algorithm throughout a dry-run. It displays information such as:
- variables
- outputs
- user prompts
Error Identification
Algorithms written by other people may have errors present. Common errors include:
- syntax errors
- spelling mistakes
- typos that may crash the algorithm
- logic errors
- endless loops
- mistakes in boolean expressions
Writing Algorithms
Algorithms can be written using:
- pseudocode
- program code
- flowchart symbols
Aside from pseudocode, only 3 programming languages are allowed to be used in the unseen scenario question.
- Python
- Java
- Visual Basic