Fundamentals of algorithms

• Graph traversals


  Graph traversal is the process of visiting each vertex in a graph. Can be performed on any connected graph.
• Depth-first search


  A branch is fully explored before backtracking, uses a stack, used for navigating a maze.

  
• Breadth-first search


  A node is fully explored before venturing on to the next node, uses a queue, useful for determining the shortest path on an unweighted graph.
• Prefix traversal


  Used for all trees, mark the left of each node, used for copying a tree.
• Infix traversal


  Only well defined for binary trees, mark the bottom of each node, can be used on binary search trees to output the contents in ascending order.
• Postfix traversal


  Can be applied to any tree, mark the right of each node, used for emptying a tree, used for infix to RPN (postfix) conversions, can be used to create an expression from an expression tree.
• Tree traversal



  Tree traversal is the process of visiting/updating/outputting each node in a tree

  • It is an algorithm
  • Unique to trees
  • Must start at the root
  • Works around the tree anticlockwise
  • Form of depth-first traversal
  • Three types are prefix, infix and postfix

  
• Reverse Polish Notation


  • A way of writing expressions
  • Uses postfix notation
  • Operators are placed after the operands on which they operate

  
• Converting between Infix and Postfix

  Infix expressions can be converted into reverse Polish (and vice versa) by traversing an expression tree

  • To return an infix expression, use an in order traversal
  • To return a postfix expression, carry out post order traversal

  Simpler expressions can be converted by observation

  
• Why is Reverse Polish Notation used?

  • Reverse Polish Notation eliminates the need for brackets, simplifying expressions
  • It is well-suited to manipulation by a stack, so is a popular choice when working with computers
• Where is Reverse Polish Notation used?

  Reverse Polish Notation is used in interpreters which are based on stacks:

  • Bytecode
  • PostScript
• Searching algorithms


  A searching algorithm is used to find a specified data item within a set of data.
• Linear search


  • Can be conducted on any list, even if the data isn’t in order
  • Works by inspecting every item in a list one by one until the desired item is found
  • Very simple to program
  • Comparatively high time complexity of O(N)
  • If the target does not exist in the list, the algorithm will still check every single item in the list
• Binary search 


  • Can only be used on ordered lists
  • Works by looking at the midpoint of a list and determining if the target is higher or lower than the midpoint
  • More efficient than the linear search algorithm
  • Midpoint calculated by adding the first and last positions of the data, and dividing by two
  • The list of data is halved with each iteration
  • Can be implemented both iteratively and recursively
  • Good time complexity of O(logN)
• Binary tree search


  • The same as a binary search, but conducted on a binary tree
  • A binary tree is a rooted, ordered tree in which each node has no more than 2 children
  • Can be implemented both iteratively and recursively
  • Same time complexity as binary search, O(logN)
• Sorting algorithms


  • Used to put the elements of an array into a specific order
  • The binary search algorithm can only be carried out on sorted arrays, so a sorting algorithm must be used before the search if the array is not ordered
• Bubble sort


  • Swaps adjacent items in an array until the array is in order
  • Has a time complexity of $O(n^2)$
  • A particularly inefficient sorting algorithm

  
• Merge sort

  • An example of a “divide and conquer” sorting algorithm
  • Divides an array into smaller arrays until each array contains just one element
  • When an array has just one element, it can be considered an ordered array
  • Arrays are then merged back together in order to form an ordered array
  • Has a time complexity of O(nlogn)
  • An efficient sorting algorithm

  
• Optimisation algorithms


  Find the best possible solution to the problem posed

  • An important optimisation algorithm is Dijkstra’s algorithm
• Dijkstra’s algorithm


  • Finds the shortest path from a starting node to every other node in a network
  • Is similar to the breadth-first search algorithm, but keeps track of visited nodes with a priority queue rather than a standard queue
  • These points may be modelled as nodes in a weighted graph
  • Used in satellite navigation systems to find the shortest route between locations
  • Used in routers to send packets via the fastest route through a network