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.

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