data structures

• stacks?

  abstract data structure operating on a last in, first out basis
• queues

  abstract data structure operating on a first in, first out basis
• 3 types of queues:

  • linear - when the spaces are filled, no more items can be added - data can't be overwritten
  • circular - data can be overwritten, front/rear pointers can move around the queue (e.g front pointer can be on 5 and rear can be on 0)
  • priority - is still FIFO but takes priority into consideration. Items with a higher priority are placed in front of those with lower priority, but behind those with equal or higher.
• call stack:

  Used when a subroutine is called. Things are saved to the call stack, such as: values of local variables currently in use, the line of code to return to, values of parameters passed to subroutine
• types of errors:

  • underflow error - when you try to remove from an empty data structure
  • overflow error - when you try to add to a full (static) data structure
• trees

  An undirected graph with no cycles. Data doesn't follow a sequential pattern. Used to show hierarchical data.
• binary tree

  • dynamic data structure
  • rooted tree
  • each node has at most 2 child nodes
  • each node has a left and right pointer
  • used for efficient sorting/search and retrieval
• hash tables

  creates a mapping between keys and values. Each input maps to only one output. The input cannot be calculated from the output.
• hashing collisions


  occur when two key values compute the same hash value. If this occurs, the second value can be stored in the next available location
• graphs

  abstract data structure representing more complex relationships. A set of connected nodes, can be unweighted or weighted, directed or undirected.
• vectors& the ways of storing them

  used to store information numerically. Can be stored as lists, dictionaries, 1d arrays, and functions.
• convex combination & its conditions

  Au+Bv. Produces any point on the line that passes through u and v. A, B >= 0, A+B=1.
• static vs dynamic data structures

  • static - fixed in size, size determined at compile time. If size is exceeded, overflow error occurs. typically stores data in consecutive memory locations. Can waste space.
  • dynamic - can change to fit amount of data. If the number of allocated memory locations is exceeded, new locations can be added to it. Data is not typically stored in consecutive locations.
• rehashing


  increasing the size of a hash table and re-storing all of the items into the table using the hash
• explain what is meant by recursive subroutine and base case:

  A subroutine which calls / is defined in terms of itself. Base case - the circumstance when a recursive subroutine does not call itself
• describe the steps involved in adding a record to a hash table:

  • apply algorithm to key value
  • result is the location in table where the record should be stored
  • if location is not empty, then use next free location
• advantages of using RPN vs infix:

  • simpler for computer to evaluate
  • doesn't need brackets
  • no need for order of precedence of operators
  • no need to backtrack when evaluating
• describe how a single stack could be used to evaluate RPN expression:

  • push values onto stack
  • when you get to an operator, pop top two values off stack, apply operator to them
  • push result onto stack
  • when end of expression is reached, the top item of the stack is the result
• intractable problem:


  can be solved, but not within polynomial time