2.3.1 Algorithms Flashcards
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
What are the 5 main Big O notations?
Constant: O(1)
Logarithmic: O(log n)
Linear: O(n)
Polynomial: O(n2)
Exponential: O(nn)
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
- The time to complete doubles with each new data item. Works quickly with small data sets, and much longer with larger ones
- Time: bad
- Space: average
