what is an algorithm
an algorithm is a set of steps for solving an instance of a particular problem type
correctness
an algorithm should terminate for every input with the correct output.
efficiency
- runtime: time for algorithm to execute is as fast as possible
- storage: amount of physical storage required to run the algorithm is as little storage as possible
algorithmic analysis
how well an algorithm performs
linear search
binary search
linear search
- initialize the index to the first element of the list
- while index points to a list element
o if the value at the current list index is equal to the required value, terminate and return the index
o else increment the index - if the index has run off at the end of the list, return none
binary search
- more efficient than linear search
- initialize a sub-list to the full list, and the index to the midpoint of the list (keep going to the mid point and comparing it)
algorithm families
exact methods
approximate methods
exact methods
calculate the solution with a guarantee of correctness, provides exact solution
- brute force
- divide and conquer
brute force
exact method
/ generate and test
- assumption: set of candidate answers can be generated exhaustively
- strategy: generate candidate answers and test them one by one until a solution is found
- eg: linear search, testing whether a number is prime
divide and conquer
exact method
- strategy: solve a smaller sub-problem akin to the original problem and extend the sub-solution to create the solution of the original problem
- eg: binary search
- eg: memoisation – technique to store the results of expensive function calls so that they can be reused later
Approximate methods
estimate the solution with how close it is to the exact solution
simulation
heuristic search
simulation
type of approximate method
- Strategy: play out a complex scenario with random inputs until we can verify stability of the answer
- Eg: weather forecast, movement of planets
- multiple runs
heuristic search
type of approximate method
- strategy: search for a solution by exploring more promising avenues fist
- sacrifice optimality for efficiency
memoisation
technique to store the results of expensive function calls so that they can be reused later
used to improve efficiency when a function is called several times with the same input to avoid duplicate computation
