Definitions - Algorithms and Programming

Completed

Abstraction

simplifying a problem by only taking the necessary details into consideration required to obtain a solution

Data abstraction

The storage and representation of data in a computer system along with its logical description and interaction with operators

Graph theory

A branch of mathematics that can be used to abstractly represent problems using a collection of nodes connected by edges

Procedural abstraction

Acheiving a task by relying on a procedure of sequential steps

Components of a problem

The smaller, simpler series of tasks and sub-procedures that a problem can be broken down into to be completed modularly

Concurrent processing

Processing where the system appears to perform multiple tasks simulataneously

Branching

A programming control structure where the code selects one or more alternative paths depending on the evaluation of a boolean expression

Functions

A subroutine that can be called to perform a task or calculation and always return a value. They can be called in expression, or be assigned to a variable

Global variables

A variable declared in the main program which exists outside any of the subroutines, but can be used anywhere in the program

Integrated Development Environment (IDE)

A software package that allow a user to develop and implement code more easily, with features for editing, debugging, version control, testing, and compilation

Iterations

A programming control structure where a set of statements is repeated either a fixed number of times or until a condition is met

Local variables

A variable declared within a subroutine of a program, which only exists and can be used within that subroutine

Modularity

The technique of breaking down a complex problem into simpler, self-contained componnents called modules, where each module is an implementation of a specific subtask required to solve a problem

Object oriented programming

A programming paradigm where the system is viewed as a set of objects, each with their own data and procedures, that can interact with each other. All processing is done by objects

Parameter passing by reference

Passing the adress or pointer of the required value into a procedure

Parameter passing by value

Creating a temporary local copy of the actual value of a variable and pasing it into the procedure

Parameter

The data structures requried to be passed into a subroutine

Procedures

A subroutine that is called by simply writing its name in the code. Procedures do not have to return a value in the program

Recursion

A programming subroutine where a section of code calls itself until a base case is met. The base case must be chosen to avoid any possibility of an infinite loop

Sequences

A programming control structure in which statements are executed one after another as they appear in the script

Subroutines

A uniquely named section of code that is written to perform a specific task within a program

Backtracking

An algorithm that incrementally finds a solution by methodically trying different sequences and abandoning a path when it knows it cannot lead to a valid solution

Computable problems

A problem for which every instance can be solved in a finite number of steps by means of algorithm

Computational methods

A method of solving a problem which by some form of computation in devising and implementing an algorithm

Data mining

An algorithm that finds a solution by analysing a large data sets to uncover trends and relationships between variables

Divide and conquer

An algorithm design technique to decompose and solve problems by reducing the problem size with each iteration, until the sub problem becomes solvable

Heuristics

A rule of thumb algorithm which can produce a valid albeit sub-optimal solution for a hard problem as an approximation

Performance modelling

The process of simulating the behavior of a model under different virtual user and system loads by mathematical approximation

Pipelining

The process of splitting a task into parts and then searching for subtasks that can be processed simultaneously to overlap the processing of each part

Problem decomposition

The process of splitting a given problem into smaller, solvable sub-problems that are easier to conceive, understand, maintain and program

Problem recognition

The ability to recognise the most effective strategy to solve a problem

Visualisation

The use of a visual representation of an algorithm or data structure to translate a problem an its solution to a more human readble form

A\* algorithm

A generalisation of Dijkstra’s algorithm that approximately finds the shortest path between two nodes by keeping track of the distance travelled from the source to the current node and the approximate distance from the next node to the destination

Big O notation

A way of classifying algorithms based on their complexity by setting an upper bound for the worst case space or time complexity as a mathematical function of input size

Binary search

A O(logn) algorithm to search a sorted list for a particular item by repeatedly halving the sublist which could contain them

Breadth-first traversal

A method of traversing a graph by using a queue to visit all the neighbours of the current node before doing the same to each of the neighbours until the entire graph has been explored

Bubble sort

A O(n^2) sorting algorithm that iterates through a list, comparing each element to its sucessor and swapping elements if the sucessor is greater than the current element. This is repeated until no more swaps can be made

Depth-first traversal

A method of traversing a graph by using a stack to travel as far along one route as possible and then backtracking and doing the same for the remaing routes until the entire graph has been explored

Dijkstra’s shortest path algortithm

An algorithm to find the shortest path between two nodes on a graph by using a priority queue to keep track of the shortest distance to each node from the starting node until the destination node is found

Insertion sort

A O(n^2) sorting algorithm that divides a list into sorted and unsorted section. Elements from the unsorted section are compared with and placed in the right position in the sorted section one by one until the sorted section spans the entire list

Linear search

A O(n) algorithm to search a list for a particular item by iterating through the list and checking each element until the required item is located, or the end of the list is reached

Merge sort

A O(logn) divide-and-conquer sorting algorithm that recursively halves the list into sublists until all sublists are of length 1. The sublists are then merged back together in such a way that they are always sorted, until the full single list is obtained

O(1) Constant time/space

An algorithm that always takes a constant amount of time or memory space to execute, regardless of the input size

O(2^n) Exponential time/space

An algorithm whose execution time or required memory space grows exponetially with input size (higher complexity than polynomial)

O(logn) Logarithmic time/space

An algorithm whose execution time or required memory space grows logarithmically with input size (lower complexity than polynomial)

O(n) Linear time/space

An algorithm whose execution time or required memory space is directly proportional to the size of its input

O(n^k) Polynomial time/space

An algorithm whose execution time or required memory space is proportional to the input size raised to the power of a constant

Quick sort

A O(n logn) sorting algorithm similar to merge sort, but relies on choosing a pivot element whenever the list is split. Elements greater than the pivot go into one sub list, while the rest go into the other. All sublists of length 1 will be in a sorted order

Space complexity

A measure of the amount of memory space needed by an algorithm to solve a particular problem of a given input size

Time complexity

A measure of the amount of time needed by an algorithm to solve a particular problem of a given input size

Caching

The temporary storage of data by the system in cache or memory for the benefit of faster retrieval if it is needed again in future

Inputs

Any information relevant to the problem that is required by the system for process according to an algorithm

Outputs

The result returned by a system for a given input after running the entire process or part of a process

Preconditions

A prerequisite or state of a system and its surroundings required to run a use case return a valid solution

Reuseable Program components

Components that have already been written, debugged and tested that can be transplanted into new systems to save development time in project completion

Flowcharts

The diagrammatic representation of the flow of a program that includes all the points where a desicion needs to be taken in order to obtain a solution

Logical conditions

Conditions which may depend on one or more variables used to determine the next step whenever a system has to make a decision. They are typically implemented using control structures such as sequences, selections and iterations