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
