Fundamentals of Algorithms

• What are the two ways to traverse a graph?


  • Depth first
  • Breadth first
• Use of depth-first graph traversal

  • Find a solution to a maze, where the maze is modelled as a graph
  • Finding a valid path from node to another (though not the shortest path)
  • Determining the order which processes that are dependent upon each other should occur
• Uses of breadth-first graph traversal

  • Identifying friends and first-degree contacts in social networks
  • Finding a valid path between nodes within an unweighted graph
  • Crawling web pages to build an index of linked pages as used by search engines
• what is breadth first search?

  is a node-based method of finding the shortest path through a graph
• What data structure does a breadth-first search make use of?

  • It makes use of an FIFO structure: a queue
• Describe the process of a breadth-first search

  • With a breadth-first search one node at a time is selected, visited and marked
  • then adjacent nodes are visited and stored in a queue
• What is depth-first search

  is an algorithm for searching a graph and starts at the root node and explores as far as possible along each branch before backtracking
• what data structure is used in a depth-first search algorithm?

  A list in first out data structure: a stack
• Describe the two stages of depth-first

  • Visited nodes are pushed onto the stack
  • When there are no nodes left to visit, the nodes are popped off the stack
• What technique does depth-first search use?

  An edge-based technique
• : What is the difference between Breadth-First Search (BFS) and Depth-First Search (DFS)?

  BFS explores nodes level by level, starting from the root node and visiting all its neighbors before moving to the next level. DFS explores a branch of the graph deeply, going as far as possible along one path before backtracking. BFS uses a queue (FIFO) to manage nodes, while DFS uses a stack (LIFO) or recursion.
• How is Depth-First Search (DFS) implemented using recursion?

  DFS is implemented using recursion by visiting a node, then recursively visiting all its unvisited neighbors before backtracking. The recursion works by exploring deeper into the graph, using the function calls as the stack to track which nodes to explore next. A base case is used to stop recursion when all neighbors are explored or no unvisited nodes remain.
• Why is Breadth-First Search (BFS) suitable for finding the shortest path in an unweighted graph?

  BFS explores nodes level by level, visiting all nodes closest to the starting node first before moving to the next level. This ensures the shortest path is found in an unweighted graph. BFS uses a queue (FIFO) to maintain the order of exploration, adding nodes to the queue as they are discovered. Once a node is explored, it is dequeued, and its unvisited neighbors are added to the queue for future exploration.
• What is the purpose of reverse polish notation?

  • RPN simplifies mathematical expressions and removes the need for brackets
• Explain why infix notation is used by humans, whereas post-fix notatation may be used by complier or intepreter?

  • Humans need brackets in order to process mathematical expressions correctly
  • Intepreters and compliers analyse code by looking first at operands and than at operators
  • It is therefore more efficient for the expressions to be written with the operators on the right hand side => Reverse Polish Notation.
  • The operators appear in the order required for computation and are thus simpler for a machine to evaluate.
• What is a use of post-order traversal

  • for post-fix notation