algorithms

Page 1

algorithms are designed to solve problems. programming languages are used to implement algorithms.

they create the programs (software) that communicate instructions to a computer.

Page 2

they have the ability to :

input data from a device such as a keyboard.

output data to devices like screens.

process calculations like addition and subtraction.

process decisions based on certain conditions being met.

process repetition for a certain number of times, or while a condition is met, or until a condition is met.

Page 3

advantages

different people can work on different sub-problems

disadvantages

the solutions to the sub-problem tasks might not combine to solve the original problems.

poorly understood problems are hard to decompose.

Page 4

Languages are defined as human-readable or machine-readable.

Human-readable instructions are encoded in a language that humans can use and understand, while machine-readable instructions are in a language that computers understand, and are in binary code.

Languages are also described as high level or low level. Low-level languages, such as assembly language, more closely reflect the mechanical workings of the CPU.

High-level languages include Java, JavaScript, C++, Ruby, BASIC or Python, while low-level languages include C, assembly language, and machine code.

A computer's CPU only understands (executes)

series of binary numbers - so all programming languages are converted

into binary code. Low-level instructions can be processed more speedily

than high-level languages, but they are more difficult for people to

read and write.

For major web applications

and powerful games, developers need to know how to code in low-level

languages in order to maximise the speed and efficiency of a program.

Modern games are typically programmed using a variety of languages.

Page 5

Trace tables

When testing more complex examples of software, it is sometimes necessary to test a number of conditions and sub-conditions at the same time.

A trace table, also called a trace matrix,

can be used to record the outcomes of the test. The trace table for a

very simple example, such as x=y+2, would look like this:

y

x

13

15

25

27

1200

1202

A trace table might appear to look very similar to a test plan, but without the other headings like 'expected outcome' and 'actual outcome'.

Syntax, execution and logic errors

There are three types of error that you need to understand.

Syntax error

This is an error in the spelling

or grammar used when coding. Missing a letter, character or forgetting

to include inverted commas/speech marks are common examples of syntax

errors. A syntax error will be identified by the translation software as

it will be unable to convert the source code into machine code.

Execution error

Sometimes called a run time

error. Execution errors only become evident during run time. An

execution error occurs when a program is asked to do something that it

cannot, resulting in a ‘crash’. The widely used example of a run time

error is asking a program to divide by 0.

The code contains no syntax or

logic errors but when it runs it can't perform the task that it has been

programmed to carry out. Another example is where an attempt is made to

access an item in an array which does not exist eg item 11 in an array

size 10.

Logic error

An error in the logic of the code

such as using ˂ instead of ˃ or AND instead of OR. The program will

execute the code but will produce unexpected results. Logic errors are

usually resolved by carrying out a dry run, using a trace table or

setting breakpoints to help identify the section of code that contains

the logic error.

Algorithm specification

Analysis, exemplification and implementation of algorithms including:

input validation

find minimum

find maximum

count occurences

linear search

Analysis of other algorithms of similar complexity.

Standard algorithms

There is always more than one

way to implement a standard algorithm. The examples used have been

designed as revision materials that exemplify some of the ways to

implement these algorithms. In each case, it is presumed that these

algorithms are procedures in their own right.

That is to say that many

languages will contain pre-defined functions to find maximum and minimum

values. It may also be the case that programmers create their own

functions to return the value of a linear search or count occurrence

algorithm.

The purpose of this revision

guide is not to show in depth examples of how to create and call these

functions. This section is for revision purposes and simply exemplifies

the structure of each algorithm.

Examples are presented in the reference language issued by the SQA as well as in the following high level languages:

Visual Studio 2010 (VB 10.0) - o Should be accessible to

users of VB5, VB6, VS2008 and subsequent versions of Visual

Basic.NET/Visual Studio

LiveCode

Python

Java (Using BlueJ)

True Basic

Xojo - Formerly REALbasic

Pascal

Comal

In an exam setting the

reference language examples could be used within questions. It is

crucial that you understand the reference language examples.

Worked examples in high level

languages are designed to aid revision during class work tasks, unit

assessment and coursework tasks. They are not exhaustive as there are

many ways to implement each algorithm.

Meaningful identifiers

It is always important to use

meaningful identifiers within an algorithm. For example, if you wish to

store a minimum value, this would be represented by the identifier

‘minimum’.

This avoids confusion and

uncertainty and allows multiple programmers to make sense of algorithms

that may not have been designed by the programmer creating the code.

Sometimes, high level

languages make use of shorthand identifiers that are regarded as

semi-standards. For example, Java programmers often use ‘i' to represent

an index or counter.

To avoid confusion, counter is used throughout this section to represent an index value when referencing an array within a loop.