- temporary storage of program instructions or data - already used once and may be needed again - held within processor, fetched quicker, increasing processing speed

- refined brute force algorithm - methodically visits each paths and builds a solution based on the found to be correct - if path found to be invalid, algorithm backtracks to previous stage and visits alternative path

- 'rule of thumb' algorithm - produces a valid, albeit suboptimal solution for a problem as an approximation

- testing by third party or end users to ensure it meets requirements and is functional - helps test usability

Paper 2 Flashcards by Natalie Burns

Caching (3)

temporary storage of program instructions or data
already used once and may be needed again
held within processor, fetched quicker, increasing processing speed

How well did you know this?

Not at all

Perfectly

Concurrent Processing

When more than one process is running from a program at once, with each process in turn being given a slice of the processor time

How well did you know this?

Not at all

Perfectly

Parallel processing

When more than one processor is executing separate instructions at once

How well did you know this?

Not at all

Perfectly

Thinking concurrently

Identifying the parts of the problem that can be tackled at the same time

How well did you know this?

Not at all

Perfectly

Thinking procedurally (3)

Breaking down a problem
identifying a number of smaller sub problems
determining the order of events in a solution

How well did you know this?

Not at all

Perfectly

Thinking logically (3)

identify points where decision needed
determining conditions of those decisions
determining next step depending on outcomes

How well did you know this?

Not at all

Perfectly

Thinking ahead

Identifying the preconditions of a system- the inputs, outputs and reusable components

How well did you know this?

Not at all

Perfectly

Precondition

A requirement that must be met for a process to run

How well did you know this?

Not at all

Perfectly

Abstraction

Representing essential features without including unnecessary details

How well did you know this?

Not at all

Perfectly

Data mining

Analysing large amounts of data to extract information not offered by the raw data alone

How well did you know this?

Not at all

Perfectly

Input

Any info(rmation) or data that is sent to a computer for processing

How well did you know this?

Not at all

Perfectly

Output

Any info(rmation) or data that is processed and sent out by a computer

How well did you know this?

Not at all

Perfectly

Backtracking (3)

refined brute force algorithm
methodically visits each paths and builds a solution based on the found to be correct
if path found to be invalid, algorithm backtracks to previous stage and visits alternative path

How well did you know this?

Not at all

Perfectly

Heuristics (2)

‘rule of thumb’ algorithm
produces a valid, albeit suboptimal solution for a problem as an approximation

How well did you know this?

Not at all

Perfectly

Branching

code selects one or more alternate paths based on the evaluation of a boolean expression

How well did you know this?

Not at all

Perfectly

Iteration

where a set of structures is repeated either a fixed number of times or until a condition is met

How well did you know this?

Not at all

Perfectly

Black box testing

used to test functionality without knowledge of the inner working of the system

How well did you know this?

Not at all

Perfectly

White box testing

tests internal structures or workings of an application, as opposed to its functionality

How well did you know this?

Not at all

Perfectly

Alpha testing

in-house testing by the developer before beta testing

How well did you know this?

Not at all

Perfectly

Beta testing (2)

testing by third party or end users to ensure it meets requirements and is functional
helps test usability

How well did you know this?

Not at all

Perfectly

Decomposition

Breaking down a problem into smaller sub problems

How well did you know this?

Not at all

Perfectly

Problem recognition

identifying the most effective strategy to solve a problem

How well did you know this?

Not at all

Perfectly

Performance modelling

simulating the behaviour of the system under different virtual users and system loads by mathematical approximation

How well did you know this?

Not at all

Perfectly

Example of performance modelling

Stress testing

How well did you know this?

Not at all

Perfectly

Passing a parameter by value (2)

- local copy of the data is used - does not change the original data

Passing a parameter by reference (2)

- memory location of data is sent - changes remain after the sub program exits

Record structure (2)

- store multiple values under one identifier - data can be of different data types

Depth-first Traversal (2)

- traverses a tree or graph from the parent node down to its left child node or right child node when left is unavailable - when there are no child nodes the algorithm 'visits' the node and backtracks to the parent node

Depth-first Traversal uses...

a stack

Breadth-first Traversal

visits all nodes directly connected to the root node then visits all nodes directly connected to each of those nodes and so on

Breadth-first Traversal uses...

a queue

Parameter

an item of data that is passed to a subroutine when called and is used as a variable within a subroutine

Procedural programming language

high-level language that gives a series of instructions in a logical order

Breakpoints (3)

- used to test that it works up to/at specific points - checks variable contents at specific points - can set a points where the program stops running

Stepping (2)

- sets the program to run line by line - can slow down the watch execution and find the point where an error occurs

Visualisation

using a visual representation of an algorithm or data structure to translate a problem and its soliton to human readable form

Problem reduction

generalising a problem to one that has already been solved

Divide and conquer (2)

- recursion used to repeatedly divide a task into subtasks of a similar type until an easy to solve subtask is reached - the individual subtasks are combined to provide solution to main task

Example of divide and conquer:

Merge sort, binary search

Reusable program components (2)

- components that have already been written, debugged and tested - save development time

What always returns a value?

(a) function(s)

Recursion

a programming subroutine where a section of code calls itself until a base case is met

Array (2)

- a static data structure that has a singular identifier - elements are accessed by an index and holds data of the same data type

Linked list (3)

- dynamic data structure that stores the item and a pointer for each item - the pointer gives the next location of the next node - nodes are not stores contiguously

Class

a template defining methods and attributes used to make objects

Quick sort (4)

- choose a pivot - compare each element in the pivot - put items less then pivot in the left sublist and larger then pivot in the right sublist - choose a pivot in each sublist and repeat the process until each item becomes a pivot

Best case time complexity of a search algorithm

Best case time complexity of bubble sort

Best case time complexity of insertion sort

Best case time complexity of merge sort

n logn

Best case time complexity of quick sort

n logn

Average case time complexity of linear search

Average case time complexity of binary search array

log n

Average case time complexity of binary search tree

log n

Average case time complexity of hashing

Average case time complexity of breadth/depth first traversal of graph

Vertices + Edges

Average case time complexity of bubble sort

n^2

Average case time complexity of insertion sort

n^2

Average case time complexity of merge sort

n logn

Average case time complexity of quick sort

n logn

Worst case time complexity of linear search

Worst case time complexity of binary search array

logn

Worst case time complexity of binary search tree

Worst case time complexity of hashing

Worst case time complexity of breadth/depth first traversal of graph

Worst case time complexity of bubble sort

n^2

Worst case time complexity of insertion sort

n^2

Worst case time complexity of merge sort

n logn

Worst case time complexity of quick sort

n^2

Space complexity of bubble sort

Space complexity of insertion sort

Space complexity of merge sort

Space complexity of quick sort

logn

Global Variable

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

Local variable

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

OOP advantages

abstraction of real world problems, classes for each type of thing modelled and objects for each instance of these

Inheritence advantages

one class coded and code used as base for similar objects, PP doesn't support this

Encapsulation advantages

prevents unexpected changes to attributes, data security

Polymorphism advantages

reduce volume of code

Procedural Programming advantages

divided between team with each team tackling a different subroutine

OOP

involves solutions being constructed by means of objects that interact with each other (modular)

Object

has methods and attributes (instantiated from a class)

Inheritence

a class takes on the methods and attributes from a parent class while also having its own

Polymorphism

a method where variables behave differently according to the context where they are used

Procedural Programming

breaks a solution into subroutines, which are rebuilt and combined to form a program