Component 19 - Key Definitions

Question 1

Big O notation

Answer 1

A mathematical representation of the best or worst case time and space complexity of a problem. Translated – how long will this take to execute and how much memory will it require?

Question 2

Constant

Answer 2

The time taken will be the same regardless of the size of the problem/data set

Question 3

linear

Answer 3

The time/space requirements will grow directly in proportion with the size of the data set.

Question 4

polynomial

Answer 4

The time/space requirements will grow as some form of function of n (the size of the data set)

Question 5

Exponential

Answer 5

The time/space requirements will grow at an exponential rate as the data set grows (as the data set increases, time/space doubles for each increase of n)

Question 6

logarithmic

Answer 6

Usually a best case scenario, the time/space requirements will grow rapidly at first as data set size increased, however this will then “level out” and increasing the size of a data set will have less and less of an effect

Question 7

Stacks – algorithm

Answer 7

You need to be able to recognise/create the code which will implement a stack. Stacks are LIFO data structures which can only be accessed from the top by “Popping” data off the top of the stack.

Question 8

Queues - algorithm

Answer 8

You need to be able to recognise/create the code which will implement a queue using either an array or a list. A queue is a FIFO data structure which can only be accessed at the “head” and “tail.”

Question 9

Tree

Answer 9

See Unit 1 notes.

Question 10

Linked list

Answer 10

See Unit 1 notes

Question 11

Depth first traversal

Answer 11

A method of searching a tree data structure by following the left most nodes until the bottom of the tree is reached and then backtracking up to each level and traversing the right hand nodes

Question 12

Breadth first traversal

Answer 12

A method of searching a tree by systematically accessing all nodes on the same level before then visiting nodes of a lower level

Question 13

bubble sort

Answer 13

A method of sorting data by comparing pairs of numbers in a list and swapping when one is bigger than the other. Continues until no swaps are made. Computationally very expensive due to the number of iterations and comparisons made, grows exponentially in complexity/time requirements

Question 14

Insertion sort

Answer 14

A method of sorting data by creating two lists – sorted and unsorted. Each iteration sees one value taken from the unsorted list and then “inserted” in the correct place using one of the following rules:
If the element is smaller than the first element of the sorted list – place at the start. If the element is bigger, then compare to the next element in the list. If bigger, move to the next element, if smaller, place in the list before this element.
If the end of the list is reached, place at the end

Question 15

Merge sort

Answer 15

Splits numbers to be sorted into lists and then merges pairs of lists:
Take the first number from each list. Compare. Place the smallest in the new list. Repeat until both lists are empty

Question 16

Quick sort

Answer 16

A “divide and conquer” algorithm which splits a data set up into two arrays around a “pivot” in the data set. All numbers bigger than the pivot are stored in one array, all smaller ones in the other array. This method is applied recursively, meaning it splits the data until each array holds only one element and then winds back up the call stack, placing elements in the correct positions.

Question 17

Binary search

Answer 17

A method of searching a data set, which must be sorted first. Finds the median value and compares to the target. If they are equal then the value is found. If not, the median is compared to the target again. If the target is larger than the median, then all smaller numbers are discarded. If the target is smaller than the median then all larger numbers are discarded. The algorithm then repeats until a match is found. Can be implemented recursively. Has logarithmic complexity, meaning it is extremely good for large data sets

Question 18

Linear search

Answer 18

The most trivial of searching algorithms, each element in a list is systematically compared to a target until it is found or the list exhausted. Has the advantage that the list does not have to be sorted, has the obvious disadvantage that it generally slows down as the size of the data set increases