Algorithms

• In depth-first traversal, we use a stack to follow one branch as far as it will go, and then backtrack
• In breadth-first traversal, we use a queue to scan every node connected to the root and continue to scan left to right
• Breadth-first can be used for finding the shortest path on an unweighted graph
• Depth-first can be used to navigate a maze
• Tree traversal can be done with pre-order, in-order or post-order.
• For pre-order traversal, place a point to the left of all nodes. Visit the root, then traverse the left sub-tree, then traverse the right sub-tree
• For in-order traversal, place a point underneath all nodes. Traverse the left sub-tree, then visit the root, then traverse the right sub-tree
• For post-order traversal, place a point to the right of all nodes. Traverse the left sub-tree, then traverse the right sub-tree, then visit the root
• Pre-order traversal is a top-down approach and can be used to copy a tree
• In-order traversal can output the contents of a binary tree in ascending order (eg alphabetical)
• Post-order is a bottom-up approach and can be used to convert from infix to RPN, or to empty a tree
• Humans use in-fix notation for mathematics, eg A + B. The opcode is fixed between the operands. This can be ambiguous for longer statements unless we use brackets or BODMAS
• Polish notation places the operator at the front of the expression, eg + A B. This is called pre-fix.
• Reverse Polish Notation (RPN), or post-fix, is used in computing. It places the operator at the end, eg A B +
• RPN is ideal as it is unambiguous and can be executed on a stack. This is helpful for stack-based interpreters such as bytecode
• You can convert between in-fix and post-fix using tree traversal
• To make a binary tree from in-fix, start with the leftmost number. When you find an operator, it moves up the tree and becomes a central node. The following expression is placed on the right branch and the process repeats
• To convert from in-fix to RPN, make a binary tree and then traverse. To convert from RPN to in-fix, draw a stack and work through the steps.
• A linear search checks every item in a list in sequence. It can be used on unordered lists
• Linear search is rarely used due to its high time complexity. Its big O notation is O(n)
• A binary search looks at the midpoint of a sorted list and determines if it is higher or lower than the target, then identifies the next midpoint accordingly.
• A binary search halves the list each search, so its big O notation is O(logN)
• A binary tree search is the same as a binary search, except it is performed on a binary tree
• Bubble sort makes passes through a list, swapping adjacent items to sort them gradually
• Bubble sort is quite inefficient. It has a time complexity of O(n^2)
• Every pass a bubble sort makes, it can guarantee the final position is sorted, and then the penultimate position, and so on
• A bubble sort must make a pass where there are no swaps before it terminates
• A merge sort splits a list into smaller and smaller lists, then reforms them into bigger and bigger sorted lists.
• A merge sort uses the divide and conquer method. Its big O notation is O(nlogn)
• Dijkstra's algorithm finds the shortest path from a starting node to every other node
• Dijkstra's algorithm is heavily used in navigation systems, eg satnavs, and even by routers to route packets across a network in the shortest amount of time
• Dijkstra's - from a starting node, visit all adjacent nodes and update their shortest distance, and record the node they were visited from. Then visit the next unvisited node with the shortest distance. Continue to update distances if they are shorter. Once a node is visited, we know the shortest path to it has been found.