Algorithms Flashcards
What are the different ways to traverse a binary tree?
- Preorder
- In order
- Postorder
How do all of the tree traversal algorithms work?
- Algorithm given a input
- Algorithm outputs a data in a different order
- Depending on algorithm used
How does preorder traversal work?
- The top down traversal method
- Encounters all roots before encountering the leaves
- Left over right
What is the pseudo code for preorder traversal?
How does in order traversal work?
- Traverse left sub tree
- Visit the root first
- Traverse the right sub tree
What is the pseudo code for in order traversal?
How does post order traversal work?
- Bottom up traversal
- Encounter all the leaves before the roots
1. Traverse the left sub-tree
2, Traverse the right sub-tree
3. Visit the root
What is the pseudo code for post order traversal?
What is the infix notation?
- A + B
- The + notation is fixed in between the two operands (numbers)
What is the problem with infix notation?
- When not using brackets with longer expressions
- Order of calculations can be ambiguous
- 2 * A + B
- Computers don’t know what to do first without brackets
What is Polish notation?
- Alternative to infix notation
- A + B -> +A B
- Add number A to number B
- Prefix notation due to operator before opperand
- No ambiguity meaning its easier for computers to understand
What is reverse Polish notation?
- Postfix notation
- Operator after operand
- A + B -> A B +
- No ambiguity
Why is reverse Polish notation important in comp Sci?
- Unambiguous and doesn’t require brackets
- Can be worked out using stacks
What can you do with infix notation (3*(1+2)) and a binary tree
- You can use reverse Polish notation to store tree traversal routes
How do use a stack with reverse Polish notation
- You use the reverse Polish notation and go from left to right
- To push items onto stacks if they are numbers
- To pop items out of stacks and carry out calculations if there is an operator
What are the steps in converting from infix to reverse polish notation?
- Use infix notation to contruct binary tree
- Use binary tree to write reverse polish notation
- Using post order tree traveersal
What are the steps in converting 3*(1+2) to a binary tree
How do you convert a binary tree to reverse polish notation?
From the root node:
- Go left and call traverse
- Go right and call traverse
- Out node
- Go up if you can
Explain this psudocode
- Linear seach
- Linear time complexity O(n)
- Keep going along the data set until you have found the datayou want
Explain this psudocode
- Binary Search
- Time complexity O(log n)
- Uses a Lower Bound, Mid Point and Upperbound which are assigned to indexes
- Uses a 2 ranges lower to mid and mid to upper to estimate which range the wanted data is in
- Repeats until the mid is the same as upper or lower
What are the two different ways to traverse a graph?
- Depth first (using a stack)
- Breath first (using a queue)
What is the depth-first approach?
- Graph Traversall algorithm
- Uses a stack
- Start at the root and follow one branch as fasr as it will go
- Then backtrack
What is the breath-first approach?
- Graph Traversal allgorithm
- Uses a queue
- Starts at the root, scan every node connected
- Continue scaning from left to right
What is the psudocode for a depth first approach?
Use the diagram to traverse the graph using the depth first approach
What is the psudocode for a breadth first approach?
Use the diagram to traverse the graph using the breadth first approach
What is merge sort?
- Sorting algorithm
- O (n log n)
- Fast
- Divide and concquer approach
- Uses Recusion
How does merge sort work?
How can you layout dijkstras shortest path?
- Represented as an array
- Can use a series of lists and a cube structure
Perform Dijkstras algorithm on this graph
