Define a linear search

Finds an item in a list by checking each item in turn

What are the key points of a linear search?

###
- Starts at the first item
- Searches in sequence
- Can be represented in an array or binary tree

What are the advantages of a linear search?

Easy to implement

Works on ordered or unordered lists

Easy to add items

What are the disadvantages of a linear search?

Usually most inefficient on longer lists

Define a binary search

An algorithm for finding an item in a sorted list.

Starts at the middle and repeatedly divides the list containing the item in half

What are the key points of a binary search?

###
- Starts at the middle item
- Halves the items needed to search after each check
- Can be represented by an array or linked list

What are the advantages of a binary search?

Efficient

Suitable for large data sets

What are the disadvantages of a binary search?

Only works on ordered lists

Slow to add items, as they must be placed in the right place

Define a bubble sort

Orders a list of items by comparing and swapping pairs of items.

It 'bubbles' the smallest/largest number to the ends

How does a bubble sort work?

###
- Starts at the first item
- Compares with the adjacent item, swapping if necessary
- Moves on until all pairs have been compared
- If any were swapped then a new pass will start

What are the advantages and disadvantages of a bubble sort?

Advantage: works well on small lists

Disadvantage: slow to work

Define an insertion sort

Slots each item into the correct position in a data set

How does an insertion sort work?

###
- Compares the second item to the one before
- Will continue along until the current item is less than the one before
- Compares the current item with all before to find the correct location
- Moves the items to their new positon
- Repeats until everything is in position

What are the advantages and disadvantages of an insertion sort?

Advantage: works well on small lists

Disadvantage: slow to work

Define a merge sort

Uses 'divide and conquer' to quickly sort data.

Creates multiple sub-problems, which are each solved individually before being re-joined.

How does a merge sort work?

###
- Repeatedly divides the list in half until each item has its own list
- Compares adjacent lists to order them into a new list
- Removes old lists
- Repeats with adjacent lists until one list formed

Define a quick sort

Sorts a set of data at a high speed using 'divide and conquer'.

It creates sub-programs which are solved individually then combined.

A pivot value will be chosen to compare the items to when dividing the list.

How does a quick sort work?

###
- Sets a pivot value
- Compares each item to the pivot value, adding those less than to one list and greater than to another
- A pivot is chosen for the new lists
- Repeats until each item has its own list
- Conjugates the lists from left to right

Define the 'Dijkstra's Shortest Path algorithm'

Finds the shortest distance between the starting node and target node using a weighted tree

Define the 'A* algorithm'

Finds the shortest path between two vertices on a weighted tree using heuristics. Won't consider every vertex

What are the advantages and disadvantages of Dijkstra's Shortest Path?

Advantage:

Finds the shortest time to a location

Disadvantage:

Every vertex must be investigated

What are the advantages and disadvantages of the A* algorithm?

Advantages:

Optimal in regards to efficiency

Works well for complex problems

Disadvantages:

The speed of execution is dependant on the heuristic accuracy

Can have complexity problems

How is the Dijkstra's Shortest Path algorithm carried out?

###
- Two lists are formed: visited and unvisited nodes
- Node distances are infinity, other than the starting node, all fill the unvisited list

- For the current node: neighbouring unvisited nodes are examined by calculating the total distance to them from the start
- If the new distance is less than the known distance, the distance and previous node information is updated
- Add the current node to the visited list and move to the next shortest-distance-away node
- Repeat until all nodes have been visited

How is the A* algorithm carried out?

###
- Fundamentally the same as Dijkstra's
- Each node has a heuristic value, e.g. the distance or time to the final node
- The nodes are ordered by heuristic + weight
- Once the final node has been reached and expanded, unvisited nodes are ignored as the shortest path is found

- The nodes are ordered by heuristic + weight
- Once the final node has been reached and expanded, unvisited nodes are ignored as the shortest path is found

What are the 5 main Big O notations?

Constant: O(1)

Logarithmic: O(log n)

Linear: O(n)

Polynomial: O(n^{2})

Exponential: O(n^{n})

Explain constant Big O notation and state its time and space efficiency

###
- Takes the same time to run regardless of the size of inputted data
- Time: good
- Space: good

Explain logarithmic Big O notation and state its time and space efficiency

###
- As the data set size increases, the time execution's rate of decrease will increase
- Time: good
- Space: good

Explain linear Big O notation and state its time and space efficiency

###
- Time will increase directly proportionally to the size of inputted data
- Time: average
- Space: average

Explain polynomial Big O notation and state its time and space efficiency

###
- Will match every item in the list with every other item: finds all possible combinations. Time execution's rate of increase will increase with data set size
- Time: average
- Space: average

Explain exponential Big O notation and state its time and space efficiency