2.3 Algorithms Flashcards
What are the maximum number of passes in a bubble sort?
n^2
What are the maximum number of passes in an insertion sort?
n^2
What are the maximum number of passes in a linear search?
n
What are the maximum number of passes in a binary search?
log(n)
What is the method of merge sorts?
List is split in half every time until there is only 1 item in a sub list
Individual sub lists are then merged together into order until list is complete again
What is a partition in a quick sort algorithm?
An unsorted section of the list
To sort items, list is repeatedly partitioned
Divide and conquer approach means when each partition only contains one items, list is sorted
What is a pivot value?
Value chosen to partition the list which is being sorted
New value chosen each time list is partitioned
What are the markers of a quick sort?
To keep track of items as they are in order, uses two marks
Lowmark and highmark
What is the method of a quick sort?
- choose value as pivot (usually 1st item in list)
- take two variables to point left and right of list excluding pivot
- left points to low index and right points to high
- while value at left is less than pivot, move right
- while value at right is greater than pivot, move left
- if both step 4 and 5 don’t match, swap left and right values
- if left greater or equal to right, point where they met is new pivot
What is Dijkstra’s algorithm?
Finds the shortest path between a start node and every other node in a weighted graph
What are the uses of Dijkstra’s algorithm?
Scheduling aeroplanes and staff so air crews always have suitable rest time
Finding best move in chess fame
Timetabling classes in a school
Finding shortest path between two points (circuit boards, route planning GPS, communication networks)
What could the weights of a graph represent?
Distances
Time
Cost of travel
How is Dijkstra’s algorithm implemented?
Similar to breadth-first search
Could use different data structures (queue, array)
Starts by assigning temporary distance value to each node
Temporary distance is 0 at start node and ∞ at every other node
How is the distance to a node calculated?
Distanced from connected node + distance from start to connected node
How is the next current node selected?
Unvisited node with shortest distance from the start
What are the column names for the table in Dijkstra’s algorithm?
Node
Visited
Shortest distance from start
Previous node
What is a heuristic approach?
One which tries to find a solution which may not be perfect but which is adequate for its purpose
What is A* algorithm?
Makes use of heuristics as each node has a heuristic value associated to it
Makes an ESTIMATE of the distance from each node to the goal node, which may not be perfect but can be used to determine most probable route and therefore don’t need to check all nodes
What can a GPS app use as a heuristic value?
Expected distance from end
Level of congestion
Speed restrictions
What are the functions of an A* algorithm?
g(x) = distance from start (weight of node + distance to node)
h(x) = the approximate cost from node(x) to goal node
How does the A* algorithm calculate the cost of each node?
f(x) = g(x) + h(x)
h(x) should NEVER be greater than g(x)
What are the column names for the table in an A* algorithm?
Node
Visited
Shortest distance from start
Heuristic (h)
f = g + h
Previous node visited
How are algorithms compared?
Using time or space complexity
To produce an algorithm that can run in the shortest amount of time and take up a minimal amount of memory resources
What is time complexity?
The amount of time they take to solve a problem in relation to the size of the input
How many lines need to be executed when running the algorithm
Need to be able to select the MOST SIGNIFICANT PART OF THE ALGORITHM
What is memory complexity?
The amount of memory resources an algorithm requires, in relation to the size of the input
What is Big O notation?
Way of expressing time and space complexity of an algorithm and therefore being able to compare algorithms
How should time and space complexity be considered?
Default consider WORST-CASE SCENARIO
If worst-case is same, pick either AVERAGE-CASE or BEST-CASE
What are the different types of complexity?
Constant
Logarithmic
Linear
Linearithmetic
Polynomial
Exponential
What is constant complexity?
An algorithm that always executes in the same time regardless of the size of the data set
An algorithm that uses the same amount of memory regardless of the size of the data set
What is the efficiency of constant complexity?
Efficient for any data set
What is the Big O notation for constant complexity?
O(1)
What algorithms have a constant complexity?
Extracting data from any element from an array
Hash tables
What is logarithmic complexity?
An algorithm that halves the data set in each pass
Because the algorithm halves each time from the large data set, it starts off with a really large search time then flattens out over time
Opposite to exponential
What is the efficiency of logarithmic complexity?
Efficient for large data sets
What is the Big O notation of a logarithmic complexity?
O(logn)
What algorithms have a logarithmic complexity?
Binary search
What is linear complexity?
An algorithm whose performance will grow in proportion to the size of the data set
An algorithm whose performances declines as the data set grows
What is the efficiency of linear complexity?
Reduces efficiency with increasingly large data sets
What is the Big O notation for linear complexity?
O(n)
What algorithms have linear complexity?
A loop iterating through a single dimension array
Linear search
What is linearithmetic complexity?
Algorithms that divide a data set but can be solved using concurrency on independent divided lists
What is the efficiency of linearithmetic complexity?
Not as efficient as logarithmic algorithms
What is the Big O notation of linearithmetic complexity?
O(nlogn)
What algorithms have linearithmetic complexity?
Merge sort
Quick sort
What is polynomial complexity?
An algorithm whose performance is proportional to the square of the size of the data set
Deeper nested iteration result in O(N^3), O(N^4) etc depending on the number of dimensions
Used for algorithms that have nested loops (number of nested loops is x)
What is the efficiency of polynomial complexity?
Significantly reduces efficiency with increasingly large data sets
What is the Big O notation of polynomial complexity?
O(n^x)
What algorithms have polynomial complexity?
A nested loop iterating through a two dimension array
Bubble sort
What is exponential complexity?
An algorithm that doubles with each addition to the data set in each pass
Execution time can quickly become very large
Opposite to logarithmic
What is the efficiency of exponential complexity?
Inefficient
What is the Big O notation for exponential complexity?
O(2^n) - for a problem that doubles as the size of the data set increases
What algorithms have exponential complexity?
Recursive functions with two calls
Fibonacci number calculation with recursion
Brute force of a password
