Studied by 6 people
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
Note
Flashcard