Fundamentals of algorithms Flashcards
describe breadth-first
shortest path for an unweighted graph
describe depth-first
Navigating a maze
describe pre order
copies a tree
describe in order
outputs the contents of a binary search tree in ascending order
describe post order
emptying a tree
why RPN is used
Easier for computer to analyse
Do need brackets so don’t have to keep track of parentheses
where RPN is used
Used in interpreters based on a stack for example Postscript and bytecode.
binary search
continually divides a list by two, eliminating the part of the list that cannot have your item in it
O(log n)
linear search
checks each element to see if it matches the target
O(n)
bubble sort
swaps the largest with the smallest until list is in order
O(n^2)
{example of a particularly inefficient sorting algorithm, time-wise.}
merge sort
splits the input into two lists of similar sizes, sorts them recursively and merges them back together into one sorted lists
O(nlog n)
applications of shortest path algorithm.
navigation system to find most efficient routes between locations
recursion vs iteration
iterative solutions often start small and build up
recursion solutions often start big and break the problem down
pros and cons of iteration and recursion
iterative solutions often start small and build up
recursion solutions often start big and break the problem down
pros:
recursive solutions can be more concise and readable
iterative solutions often execute faster
cons:
recursion can run infinitely when the the general case doesn’t move towards the stopping case / can take up more memory
iteration can run infinitely if an indefinite loop is used and the condition never changes
recursion
Subroutine that calls itself
