Algorithms Flashcards
Algorithm for removing from a queue?
Found in photos
Algorithm for adding to a queue?
Found in photos
Algorithm for removing from a stack?
If stack pointer minimum then report stack empty
Else
Set data to stack(stack pointer)
Set stack pointer to stack pointer -1
Endif
Algorithm for adding to a stack?
If stack pointer maximum then report stack full
Else
Set stack pointer to stack pointer +1
Set stack(stack pointer) to data
Endif
What are the two main types of algorithmic operations?
- sequential operations = instructions executed in order
- control operations = instructions not executed in order. include conditional (if statements) and iterative (loops) operations
What are the two approaches used by sorting algorithms?
- incremental approach (go through line by line)
- divide and conquer approach (breaks down list into smaller lists and reassemble into correct order)
What is bubble sort? +/-
-uses incremental approach
-Each value is compared to adjacent values and bubbled up the list if it is greater than its adjacent value
-Repeated for each value until in correct order
-very slow and inefficient so only used for small lists
+most simple to understand
How are variable values swapped in programming?
- When two variables have their values swapped a third variable is created allowing switch to be possible
- eg: p=5 q=79 to switch we would set new variable temp =p then p=q and finally q=temp
What is insertion sort?
- incremental approach
- goes through each item one by one and places them in correct order in list
- needs partially ordered lists
- faster than bubble but still not quick
What is linear search?
-start at beginning of list comparing your value to this value. if not the same move on if it is the same your finished. Repeat until value found
-simple loop with incrementing values used to represent
+list does not have to be ordered
+efficient for long lists
-only returns value once so if it represented multiple times it will still only be outputted once
What is binary search?
- uses divide and conquer approach
- sets an upper and lower bound then finds the midpoint by ub+lb/2
- We check if the value we want is at this midpoint. If not we check if it is smaller or bigger than midpoint. if smaller we repeat process for values smaller than mid point. vice versa for larger.
- must be sorted
- better for more complex data searches
What is complexity?
- not a reflection of how quickly an algorithm runs
- instead it tells us how well the algorithm scales given increasing sizes of data
- how quickly the runtime grows relative to input as the input gets arbitrary large
What is the basis of big O notation?
- the language we use to articulate how efficient an algorithm is
- called Big O because we express it as O(x) where x is the worst case complexity of the algorithm
- only care about how the algorithm scales with increased data not the exact time taken, therefore we simplify the number of steps in the algorithm
What is the time complexity in big O notation of 7n^3+n^2+4n+1?
O(n^3)
What is constant complexity? Draw the graph
- graph on paper
- O(1)
- algorithm that will ALWAYS execute in the same time regardless of the size of input data
- eg; pushing an item onto, or popping an item from a stack
What is linear complexity? Draw the graph
-graph on paper
-O(n)
-if the input size doubles, the time taken for the algorithm to complete also doubles
Eg; average time to find an element using linear search
What is polynomial complexity? Draw the graph
- graph on paper
- O(n^k)
- time taken as the input size increases can be expressed as n^k where k is a constant
- constant and linear are also polynomial as n^0=1 and n^1=n
- examples are quadratic O(n^2) and cubic O(n^3)
- Karmarkers algorithm for linear programming
What exponential complexity? Draw the graph
- graph on paper
- O(k^n)
- as the input n gets larger the time taken increases at a rate of k^n
- do not scale well
- eg; recursive calculation of Fibonacci numbers
- Eg; solving matrix chain multiplication via brute force search
What is logarithmic complexity? Draw the graph
- graph on paper
- O(log n)
- the inverse of exponentiation
- scale very well
- The rate at which their execution time increases, decreases as the data set increases
- Eg; binary search, as the data doubles the number of items to be checked only increases by 1
What is Dijkstra’s shortest path algorithm used for? Algorithm?
- finds shortest path between two points
- marks the start node as a distance of 0 from itself and all others as an infinite distance from this node
- start at start node. Visit all nodes connected. Mark down total distance. Close current node. Visit all nodes connected to current shortest path. Repeat.
- algorithm in book
What is the A* algorithm?
- also goes through every node like Dijkstra’s but is faster than as it utilises heuristic values
- heuristic is when existing experience is used to form a judgement
- heuristic must NEVER be an overestimate
- speed depends of efficiency of heuristic
- A* refines search into a direct area whereas DJK’s searches all areas even if destination is not there
Look over 15 puzzle
In book
What is merge sort?
- if we have two ordered lists we can merge them into a single ordered list
- principle; spit n items into a list of 1 item, While there is more than 1 list recursively pair up the lists and merge each pair into a singe list twice the size
- if one list is emptied before the other, add the remaining items into the new list
- example of divide and conquer
What is quicksort?
- divide and conquer algorithm
- involves pivots and sub lists. Pointer can be any value to start with, sub lists are not ordered
- its powerful and fairly quick
- due to its recursive nature it can be an issue when being applied to large data sets causing a stack overflow error
Why is the ‘in place’ version of Quicksort sometimes used?
- Goes through the same process as the original but on a single list without the need for recursive calls
- uses pointers
Algorithm for getting output of linked list
In notes
Algorithm for searching a linked list?
In notes
Algorithm for preorder traversal of trees?
In notes
Algorithm for in-order traversal of trees?
In notes
Algorithm for postorder traversal of trees?
In notes
Algorithm for depth first traversal of graphs? When is this used?
- stacks
- in notes
Algorithm for breadth first traversal of graphs? When is this used?
- quests
- in notes
