Please enable JavaScript.

Coggle requires JavaScript to display documents.

ITP 365 Final Prep (Data Types (Vector (Functions and their Big Os (push…

- - - - Can access specific indexes
      - Can be implemented with a vector
      - Adds and removes at the end
      - Similar to an array of chars
      - Does not contain clear
    - - push_back : O(1)
      - pop_back / += : O (1)
      - insert at front : O(n)
      - erase at front : O(n)
      - [n] : O(1)
      - clear
    - - First In / Last Out (FILO)
      - Adds at the end
      - Removes at the end
      - Cannot access specific indexes
      - Can be implemented witha doubley OR Singley Linked List OR a Vector
      - Does not contain pop_front or push_front
  - - - push_back : O(1)
      - pop_front : O (1)
      - insert after finding : O(1)
      - erase after finding : O(1)
      - Finding item n : O(n)
      - pop_back : O(1)
      - push_front : O(1)
    - - Does not contain push_front or pop_back
      - Can be implemented with a doubley linked list
      - Cannot access specific indexes
      - Removes at the begin
      - Adds at the end
      - First In / First Out (FIFO)
  - - - push_back : O(1)
      - insert after finding : O(1)
      - erase after finding : O(1)
      - Finding item n : O(n)
      - pop_back : O(1)
  - - - Can access specific indexes
      - Functions and their Big Os
        
        Access / [Key] : O(log n)
        
        insert : O(log n)
        
        erase : O(log n)
        
        find : O(log n)
        
        count : O(log n)
      - Implemented using a balanced binary search tree
      - Matches a specific Key variable to a Value variable
      - std::map
    - - Functions and their Big Os
        
        Access / [Key] : O(1)
        
        insert : O(1)
        
        erase : O(1)
  - - - If can go no deeper, add the item at the empty space
    - - Access : O (n)
      - insert : O (n)
      - erase : O (n)
  - - - Storage : O(V + V)
      - Add Vertex : O(1)
      - Add Edge: O(1)
      - Remove Edge: O (V)
      - Remove Vertex: O (V + E)
      - Query : O (V)
    - - A vector keeps extra data when it doubles and the size of it decreases
      - You are not worried about the time it takes to look up items in the adjacency list since operations are conducted from start to end
- - - - Can create problems if the heap values are modified for one pointer but not another
    - - Pass by Reference: &varName
      - Function call by Reference: (vartType& name)
      - &varName gets the memory address
- - - - Uses a Visited Bool for each node
      - Add the root node of the graph to the Queue
      - While the queue is not empty
      - raphs, unlike trees,. may contain cycles
      - Pop the first item in the queue and set it to current node
      - If the current node is not the item being searched for, set its Visited Bool to True
      - Loop through all the current node's neighbors and enqueue the ones that have have Visited = False
      - If the queue is empty and the item was not found, then no path exists from the root node to the node being searched for
      - Big O = O(V+E)
    - - Add the root node of the graph to the Queue
      - While the queue is not empty
      - Pop the first item in the queue and set it to current node
      - If the current node is not the item being searched for, enqueue its right and left children (if they exist)
      - If the queue is empty and the item was not found, then there is no path from the starting node to the node being searched for
      - Big O =N
  - - - If the adjacent node is not in the Closed set
        
        If it has a previous, determine if the current node is a superior route to the adjacent node by comparing its path cost to the path cost of the current node + the cost of traversal
        
        If the current route is superior, then set the nodes previous to the current node
        
        If it doesn't have a previous,
        calculate its path cost and add the cost of the current node, set its previous to the current node, and add it to the open set
      - Pop the node in the open set with the lowest path value
        
        If the set is empty, then there is no path
- - - - Modify and return OS
  - - - mVars = other.mVars
      - return *this
- - - - return size
- - - - Example: 4,2,5,1,3
    - - Can be reversed to get the nodes in a non-increading order
  - - - Example: 4, 5, 2, 3, 1
  - - - Example: 1,2,4,5,3