4.3 Fundamentals of 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 traversa
Left, Right, Root -
in order tree traversal and when its used (1)
Left, Root, Right -
Used in binary search trees
What is Meant by O(N)
O represents the order of complexity
N represents the number of inputs
What are the factors of complexity used in big o notation
Memory used, time clompexity
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 real life applications? (3)
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
