paper 1 definitions

Algorithm

A sequence of steps that can be followed to complete a task.

Decomposition

Breaking a problem into a number of sub-problems, so that each sub- problem accomplishes an identifiable task, which might itself be further subdivided.

Abstraction

The process of removing unnecessary detail from a problem.

Pseudo-code

Precise, English-like description of an algorithm. It has no specific syntax, so input name and if name is bob are valid instructions.

Flowchart

A visual representation of an algorithm using specific shapes including rectangle, diamond and parallelogram.

IPO

Where inputs, processing and outputs are taking place within an algorithm.

Linear search

A searching algorithm which looks at every element in turn until it finds the target, it is slow but works even on unsorted data

Binary search

A searching algorithm that divides the search space in half each time until it finds the target, faster than linear but requires the array to be sorted

Merge sort

A very efficient sorting algorithm that repeatedly breaks down a list into smaller lists, then repeatedly merges them back together in order

Bubble sort

A sorting algorithm that passes over the list many times, swapping adjacent items if they are in the wrong order. Not very efficient.

Integer

The data type of a whole number e.g. 5, 999 or -4

Real

A data type also called floating point numbers, they have a decimal part, for example 1.5, 0.935 or the value of Pi

Boolean

This data type has only two values, TRUE and FALSE

Character

The data type of a single character e.g. "A" or "$"

String

This data type stores a series of characters, e.g. "Zak", "MK44 5AB" or "123456789"

Variable

A named memory location holding a single value that can change during the program, e.g. name, age, x, y

Constant

It cannot change. A named memory location for something that stays the same. Examples are PI, NumberofLevels, MAXHEALTH

Assignment

A statement that assigns a value to a variable. The right side of the equals sign can be any expression. These are valid: health ← 100 fare ← 5 + 0.5 * miles

Sequence

A programming construct where instructions follow, one after the other

Iteration

A code construct where the instructions repeat. Can be definite/count-controlled or indefinite/condition-controlled.

Selection

A programming construct where the code makes a decision, and takes one of several branches, usually coded with IF-THEN-ELSE

Subroutine

A small set of instructions that completes a specific task, sometimes called a subprogram. It can be a function or procedure

Procedure

A subroutine which does not return a value. For example it might redraw the screen or write a record to a file

Function

A subroutine which returns a value. It might return a random dice roll, calculate a ticket price or determine your exam grade

Definite iteration

Repeats instructions a set number of times, also called "count-controlled". Uses a FOR loop in most high-level languages

Indefinite iteration

Repeats instructions a until a condition is met, also called "condition-controlled". Uses WHILE or REPEAT… UNTIL in high-level languages

For loop

This statement starts a definite iteration with the amount of iterations at the start, it will run a set number of times.

While loop

This statement starts a condition-controlled loop with the condition at the start, so the loop will only begin if the condition is true

Repeat until

A statement that starts a condition-controlled loop with the condition at the end in an UNTIL statement, it will run once even if the condition is false

Nesting

Coding a second programming construct inside the first. You can do this with selection and iteration

Identifier names

The name we give to variables, constants and subroutines, it should be meaningful

Real division

The arithmetic operator that divides one operand by another e.g. total / 7

Integer division

Or floor division, the quotient arithmetic operator divides operands giving only the whole number result. E.g. 9 DIV 4 = 2. Python uses // for this.

Remainders

The amount left over when one number is divided by another. Calculated with the MOD operator. Python uses % for this.

NOT

Boolean operator that negates its operand, meaning True becomes False and vice versa

AND

Boolean operator that returns a true value only if both operands are true

OR

Boolean operator that returns a true value if either operand is true

Array

A data structure that stores many data items of the same data type, can be one-dimensional, two-dimensional or more. (In Python we use a list for this)

Record

A collection of related data items called fields, often stored as a row in a database, it represents something in the real world like a person or product

String length

A function that determines how long a string is, i.e. the character count

Character position

A function that returns the numeric location of a character within a larger string (counting from 0)

Substring

A function in pseudo-code that returns part of a string when we pass it a starting position and length

Concatenation

Joining two strings together, usually uses the + operator, for example fullname = firstname + lastname

Character code

The numeric value of a character in a the character set. In ASCII, "A" is 65

Parameters

A variable declared in a subroutine definition, a and b are parameters in this code: SUBROUTINE add(a, b) result ← a + b RETURN result ENDSUBROUTINE

Return

A value which is given back to the section of code that calls a function.

Local

Variables with limited scope, they are usually deleted when the subroutine ends, thus saving memory and preventing errors

Global

Variables of this type remain in memory even when a subroutine ends, their scope is the whole program

Syntax error

An error because the rules of the language have been broken, such as forgetting a bracket or mis-spelling a keyword

Logic error

An error that occurs when code runs but produces unexpected results. E.g. adding instead of subtracting or stopping a loop too soon. It is detected by systematic testing with a trace table

Run-time error

An error that occurs when the code runs but fails during the operation. Usually caused by file handling problems or data types being incorrect.

Testing

The systematic process of running a program repeatedly with different input data and checking the output is as expected, revealing errors

Normal data

Test data that is expected or typical, e.g. the code if age < 18 then might be tested with data of 14

Boundary data

Extreme test data at the edges of the valid range. Phone battery percentage must be between 0 and 100, so these test data values would be -1, 0, 100 and 101

Erroneous data

Data of the wrong type or outside the expected range. For example a string where a number is expected, or an angle of 400 degrees. The program should reject this but not fail

Low-level language

Programming languages which are a much closer representation to the instruction set of the processor. These include assembly language and machine code.

High-level language

Programing languages designed to make it easier for humans to understand and write computer programs, than using low-level languages. Examples include Python and C#.

Machine code

A low-level language which the CPU can process directly, and consists of only binary codes which are very hard to write directly, to change and to debug

Assembly

A low-level language which uses mnemonics such as LDA, ADD to represent machine code instructions

Translator

A program which converts source code into code which the processor can execute, this can be a compiler, interpreter or assembler

Interpreter

This translator converts a high-level language into machine code one line at a time and then executes it, it's slower but interpreted code is quicker to write and easier to update

Compiler

A type of translator which converts a high-level language in to machine code all at once

Assembler

A type of translator which translates assembly language in to machine code