Algorithims Flashcards
What are the 2 features of a breadth first graph traversal?
Shortest path for an unweighted graph
uses a queue
What are the 2 features of a depth first graph traversal?
Navigating a maze
uses a stack
pre order tree traversal order and when its used
Root, Left, Right - Copying a tree.
post order tree traversal and when its used (2)
Left, Right, Root -
Binary search tree
Outputting the contents of a binary search tree in ascending order.
in order tree traversal and when its used (3)
Left, Root, Right -
Infix to RPN conversions
Producing a postfix expression from an expression tree
Emptying a tree.
Time complexity of linear search
O(n)
Time complexity of Binary/Binary tree search
O(log n).
Time complexity of Bubble sort
O(n^2).
Time complexity of Merge sort
O(n log n).
What is djikstras algorithim? and the applications?
Shortest path algorithim
chip design
finding routes from one place to another
web crawlers
What does it mean when algorithims are tractable?
These are problems that have a polynomial (or less) time solution (x^2)
What is it when an algorithim is intractable?
These are problems that have solutions in greater than polynomial time
What methods are used when tackling intractable problems
Heuristic methods
