2.3 Algorithms

• Explain the similarities and differences between a record and a class

  • Record is a data structure
  • A class is a template for making data structures
  • Class also has methods which describes functionality
  • Both store data of different types
  • Both can have multiple instances
  • Class can include visibility of properties / private
• Define the term 'queue'

  A data structure

  FIFO (first in first out)
• Explain how a private attribute improves the integrity of the data

  • Properties are encapsulated and can only be accessed through their methods
  • Cannot be changed/accessed accidentally
• What does it mean for a list to be dynamic?

  items can be added and deleted, inserted at any place
• Difference between breadth first and depth first

  • Depth-first goes to left child node always, if there is no left child it goes to the right child. When there are no child nodes the algorithm ‘visits’ it’ and backtracks to the parent node.
  • Breadth-first visits all nodes connected directly to start node Then visits all nodes directly connected to each of those nodes and so on
  • Depth-first uses a stack
  • Breadth-first uses a queue
• Difference in storage structure between breadth and depth first traversal?

  Queue for breadth-first traversal, stack for depth-first traversal
• Similarities graph and tree

  • Both consists of nodes
  • Both are connected by edges
  • Both are non-linear data structures
  • Both are dynamic data structures
• Explain how a data item is removed from a linked list

  1. Traverse the list to the item immediately prior to the item to be removed
  2. Find the value of the next pointer of the item to be removed
  3. Set the next pointer of the item prior to the item to be removed to the next pointer value
  4. Update the next pointer
• Explain how backtracking is used in depth-first

  • Depth first starts at the root and goes all the way down one branch to the bottom
  • It stores which nodes it has visited onto a stack
  • When it cannot go any further it backtracks to the previous node and continues to backtrack until a node is reached with unvisited children and checks down that branch
• Explain how 1D array can be set up and used to push and pop items as a stack

  • Array size defined
  • A stack pointer is used to point to the top of the stack
  • When an item is pushed the stack pointer is incremented
  • When an item is popped the stack pointer is decremented
• Describe how an array can be used to implement a queue data structure

  • Queue has head pointer and tail pointer
  • When an item is enqueued the tail pointer increments
  • When an item is dequeued the head pointer increments