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
🤔
It is possible to swap items in an array of numbers without using a temporary variable.

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
🤔
Websites often use double-entry to confirm passwords.

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
NormalData that should be accepted10
AbnormalData that should be rejectedten
ExtremeLowest or highest acceptable values1
BoundaryLowest or highest acceptable and unacceptable values0, 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
🤔
It is recommended to use python when given the choice to use program code!