A Level OCR Computer Science 2.3 - Algorithms

What are the characteristics of a good algorithm

Clear and precisely stated steps, allows for invalid inputs, terminates at some point, efficient, understandable

What is complexity

The order with which time and space grows

What does time complexity scale within an algorithm

The number of individual steps taken

How do we write big O notation

O(n^x) where x is the highest power of n the algorithm reaches

What is constant complexity

No matter how large n gets the complexity stays the same

What is the big O for constant complexity

O(1)

What is a quick way of recognising constant complexity

Has no loops

What is linear complexity

Complexity increases by a set amount for each increase in n

What is the big O for linear complexity

O(n)

What is a quick way of recognizing linear complexity

One loop that executes n times

What is quadratic complexity

Complexity scales with the square of n as n increases

What is the big O for quadratic complexity

O(n^2)

What is a quick way of recognising quadratic complexity

A loop with a loop nested in it that both execute n times

What is logarithmic complexity

Complexity increases at an exponentially decreasing rate as n increases

What is the big O of logarithmic complexity

O(log n)

What is a quick way of recognising logarithmic complexity

Look for the halving of the data set

What is exponential complexity

Complexity increases exponentially as n increases

What is the big O of exponential complexity

O(2^n)

What is the quick way of recognising exponential complexity

Recursive function that calls itself twice

What is big O notation

A measure of the space or time complexity of an algorithm

What is a permutation

A possible configuration of something, e.g. the order items are in

What is the time complexity of an algorithm

The order by which the time taken for an algorithm to be completed grows

What is the space complexity of an algorithm

The order by which the space taken up by an algorithm grows

Why it the big O a measure of interest to computer scientists

Big O is a way of comparing algorithms so that the most efficient one can be chosen. A bad time complexity can make a problem involving vast amounts of data infeasible to solve

How does linear search work

Can work on both ordered and un-ordered data sets

Gets first elements

If equal then report is found

If not equal then move to next element

Repeat for all elements, until found/ end of list reached

When is linear search used

When items are not ordered

When list is very small

What is the worst case big O time of linear search

O(n)

What is the average case big O time of linear search

O(n)

What is the best case big O time of linear search

O(1)

What is the big O space of linear search

O(1)

How does binary search work on an array

Works on an ordered set of data

Find mid-point

If equal to midpoint item is found

If less than mid-point make sub- list from left

If greater than mid-point make sub-list from right

Repeat with sub-list until found/sub-list is empty

What is the algorithm for binary search

function binary_search(array, target, left, right)

>while left <= right

>>midPoint = (left + right) DIV 2

>>if array[midPoint] == target

>>>return True

>>elif array[midPoint] < target

>>>left = midPoint + 1

>>else

>>>right = midPoint -1

>endwhile

>return False

endfunction

What is the worst case big O time of a binary search on an array

O(log n)

What is the average case big O time of a binary search on an array

O(log n)

What is the best case big O time of a binary search on an array

O(1)

What is the big O space of a binary search on an array

O(1)

What is the worst case big O time of a binary search on a binary tree

O(n)

What is the average case big O time of a binary search on a binary tree

O(log n)

What is the best case big O time of a binary search on a binary tree

O(1)

What is the big O space of a binary search on a binary tree

O(1)

Under what circumstance can we not use a binary search

On an unsorted list

Where might we use a linear search instead of a binary search

On an unsorted list, on a small list, on a linked list

How does a bubble sort work

>Starting at the beginning of the list

Items are swapped with their

neighbour if they are out of order.

>Each pair of neighbours is checked in

order.

>When a swap is made a flag is set.

>If at the end of the list the flag has

been set the flag is unset and the

algorithm starts from the beginning of

the list again.

>When the algorithm gets to the end

of the list and the flag is unset the list

is sorted and the algorithm finishes.

How can bubble sort be improved

Checking one less item per iteration

Alternating sorting directions

What is the worst case big O time of bubble sort

O(n^2)

What is the average case big O time of bubble sort

O(n^2)

What is the best case big O time of bubble sort

O(n)

What is the big O space of bubble sort

O(1)

How does an insertion sort work

Breaks list into a sorted list (initially empty) and an unsorted list. One item taken from the unsorted list at a time and inserted into the sorted list in the correct place

What is the algorithm for insertion sort

def ins(list, lastindex)

>for x = 1 to last index:

>>currentdata = list[x]

>>position = x

>>while (position > 0 AND list[x-1] > currentdata)

>>>list[position] = list[position -1]

>>>position = position - 1

>>list[position] = currentdata

What is the worst case big O time of insertion sort

O(n^2)

What is the average case big O time of insertion sort

O(n^2)

What is the best case big O time of insertion sort

O(n)

What is the big O space of insertion sort

O(1)

Why is bubble sort inefficient

Requires significantly more swaps than other sorting algorithms, meaning it takes up more CPU cycles to solve the same problem

What kind of data structure is a stack

A LIFO - Last in first out + dynamic

What can a stack be thought of as

A stack of books where you can only remove the top one

What commands are used to add and remove items in a stack and what do they do

Push - Add item to the top, Pop - remove the top item

How are pointers used in stacks

Pointer to top of the stack, tells which item is to be removed or where an item is to be added

What kind of data structure is a queue

A FIFO - First in First out

Dynamic - list length and content can change

What can a queue be thought of as

A queue of people for a shop

What commands are used to add and remove items in a queue and what do they do

Enqueue - add an item to back, Dequeue remove the item from the front

How are pointers used in queues

The pointer at both front and back of the list, these shows where items are added and removed from and move when an item is added or removed

How does merge sort work

Divides the unsorted list into n sublists each containing one element, repeatedly merge sublists to produce newly sorted sublists until there is only one sublist remaining. This is the sorted list

What is the worst case big O time of merge sort

O(nlog n)

What is the average case big O time of merge sort

O(nlog n)

What is the best case big O time of merge sort

O(nlog n)

What is the big O space of merge sort

O(n)

How does quick sort work

Finds a split point which divides the list into two sublists, one containing items more than the split point, the other less. This is done repeatedly till the split points have nothing to compare to.

What is the worst case big O time of quick sort

O(n^2)

What is the average case big O time of quick sort

O(nlog n)

What is the best case big O time of quick sort

O(nlog n)

What is the big O space of quick sort

O(log n)

When might a bubble or insertion sort be better than quick or insertions sort

Easier to implement, quicker on nearly sorted lists

What is meant by logarithmic growth

As the size of the array

increases, the rate at which the

number of checks needed increases

more slowly

The inverse of exponential growth

The rate of increase is a logarithmic

function of the size of the array

When is quick and merge sort better than insertion and bubble sort

On large sets of data

Which is faster, insertion sort or bubble sort

Insertion sort is generally faster

Why do insertion sort and bubble sort have space complexity of O(1)

They are inplace (all sorting takes place within the data itself)

Why do insertion sort and bubble sort have time complexity of O(n^2)

They have a nested loop

Define a tree

A data structure that represents a hierarchical nature made up of nodes called roots(parents) and leaves(children) connected by branches

What is a binary tree

A tree that has at most two children for each parent node

How does a depth-first traversal work

Goes to the left child when it can.

When there are no left children it goes to the right child

When there are no children left it visits the node and back tracks to the parent node

Uses a stack

What is a depth first search used for

Job-scheduling, where some jobs have to be completed before others can begin

Finding a path between two vertices

Solving puzzles such as navigating a maze

How does a breadth-first traversal work

Visits all nodes connected directly to the current node

Then visits all nodes directly connected to each of those nodes(etc)

Uses a queue

What is a breadth first used for

Finding the shortest path between two points

A Web crawler uses a breadth-first search to analyse sites that you can reach by following links randomly

Facebook uses a breadth-first search to find all the friends of a given individual

How does a pre-order traversal work

Explores the root, then the left subtrees, then the right subtrees: olr

How does an in-order traversal work

Explores the left subtree, then the root, then the right subtree: lor

How does a post order traversal work

Explores the left subtree, then the right subtree, then the root: lro

Why are trees traversed

To get the information stored in them

What is an intractable problem

One that cannot be solved efficiently e.g. in polynomial time

What is an insoluble problem

One that has no solution at all other than heuristics