CS paper 2 cards

big o notation

A sorting algorithm has a best time complexity of O(n). Describe what is meant by the best time complexity O(n) for a sorting algorithm.

Linear

The time will (increase) in direct proportion to the number of items

As the size of an array increases the average number of checks grows logarithmically. State what is meant by logarithmic growth.

As x (or the size of the array)

increases, the rate at which y (or the

number of checks needed) increases

more slowly (1).

The inverse of exponential growth (1).

The rate of increase is a logarithmic

function of the size of the array (1)

alpha testing

carried out in-house by team

bugs pinpointed and fixed

beta testing

carried out by end-users after alpha testing. feedback from users is used to inform next stage of development

white box testing

using source code

form of testing carried out by software dev team where plan based on structure of program

dry runs / trace tables

all possible routes through program tested

also called structural testing

justification for why and when use whitebox

the complete structure / logic has been tested

system is safety critical

failures could cause loss of life

therefore every path needs to be verified, enure no hidden logic errors

black-box testing

test expected output based on input

does not look at code

testers not aware of internal structure

functional testing

test plan traces through inputs and outputs within the software

Visualisation

Presents data in an easy-to-grasp way

(1)

An array is not actually a grid / table

(1)

Data can be presented in a way that is easier for us to understand using visualisation. This makes it possible to identify trends that were not otherwise obvious, particularly amongst statistical data. Depending on the type of data, data may be represented as graphs, trees, charts and tables. Visualisation is another technique that is used by businesses to pick up on patterns which can be used to inform business decisions.

when does bubble sort continue to next pass or stop

if there has been a swap it does another pass to check

if no swap it does not do any more passes or checks since it is sorted

Best time O(n) — best time

Best time grows at the same rate as the number of elements

This is the case when the data is already in order

Average and worst time O(n2) — bubble sort

Worst and average time is proportional to the square (polynomial)

of the number of elements

Worst case is when the data is initially in the reverse order

Worst space O(1)

Constant

Will always take the same amount of memory (in addition to the

list itself).

Backtracking key words

When it cannot go any further, backtracks to previous nodes

Continues to backtrack until a node is reached with unvisited children … then checks down that branch

Data Mining

Extracting data from databases

Using large data sets

Looking for patterns/specific occurrences of

data

Gathering data that can be analysed and

used to inform decisions

bubble sort

bubble sort issue initially and how solved

If the algorithm goes on until it terminates, it could possibly make many pointless comparisons

The most important modification is the introduction of a flag recording whether a swap has occurred. If a full pass is made without any swaps, then the algorithm terminates earlier than it would have done originally.

insertion sort

Insertion sort has the same time complexity as bubble sort, O(n2

benefit drawback of iteration over recursion

Benefit:

The program can/might run faster

Cannot run out of stack space/memory

Easier to trace/follow

Drawback:

Iteration can lead to lengthier code

Iteration can lead to code that looks more complex / is harder to

understand

some problems are more elegantly coded with a recursive

solution

Paper 2 computer science pipelining definition in context with game

The result from one process / procedure feeds into the next

E.g. the result of detecting a character touching an enemy feeds

into reducing the number of lives

Describe two advantages of splitting the problem into sub-procedures

 Procedures can be re-used

 No need to reprogram/saves time

 Program can be split between programmers

 Can specialise in their area

 Speed up completion time

 As multiple procedures worked on concurrently

 Easy to test/debug

 As each module can be tested on its own then combined.