2.1 Algorithms

• Abstraction • Decomposition • Algorithmic thinking

The process of removing all unnecessary details and including only the most relevant details.

Breaking down a complex problem into smaller, more manageable parts.

A way of getting to a solution by identifying the individual steps needed.

Anything that needs to be supplied to the program to meet its goals.

Which calculations must be performed while the program is running.

What your program needs to output.

• Syntax errors • Logic errors

Errors that break the grammatical rules of a programming language and stop it from running.

Errors that produce an unexpected output, however the program still runs.

Help to illustrate problem decomposition. They use ‘Step Wise Refinement’ Each node should achieve a single task which can then be coded as a subprogram

Take each line at a time and write out the state of each variable.

A method of representing the sequence of steps in an algorithm in the form of a diagram.

Represents flow from one component to the next.

Process E.g. Input

Input/output

Subroutine

Decision E.g. IF/ELSE

Start/stop. Terminator.

• Binary search • Linear search

• Calculate the midpoint of data set. • Check if that is the desired item IF desired item is lower than midpoint… • Repeat on left half data set IF desired item is higher than midpoint… • Repeat on right side of data set • Repeat until item is found.

• Required data set to be ordered • More efficient than linear search

Starting from the beginning of a data set, each item is checked against to see if it is the desired item.

• Will work on any storage device • Efficient for smaller data sets, not large ones.