Please enable JavaScript.

Coggle requires JavaScript to display documents.

IADs, Times for all ops, IADs ToDo: 1. Write up master theorem, learn best…

- - - - Master Theorem
        
        What is the formula, what does each term mean?
        
        what are: a,b,e,k
        
        different time complexities for ways in which e compares to k
        
        why is it a compares to b^k rather than a compares to n^k/b
  - - - f grows slower than g
    - - f grows at maximum the same speed as g (as it can be asymptotically tight)
    - - f is an asymptotically tight bound for g. g is between two values c1 and c2 for f over a large enough input.
    - - f grows faster than g
- - - - The stack is contiguous memory so items on the stack have fixed size.
      - Stack items usually contain a basic value, or a reference to something on the heap
      - Program variables are stored in the stack
    - - Memory set aside for dynamic allocation. Allows items to grow and shrink.
      - Not contiguous, items can be stored anywhere on the heap
      - Heap objects can become unreachable, garbage collectors then deal with them.
      - Equality testing: by reference or by content
      - Shallow copy vs deep copy
        
        Shallow copy only copies the reference(s)
        
        Deep copy creates a fresh copy of the entire structure
      - Accessing an object from a reference is called dereferencing. As you are getting the value instead of the reference.
  - - - Array
        
        Allocating is O(1), initialising is not
        
        Why is insert O(n) and append is O(1)
        
        Fixed size
        
        Extensible
        
        It assigns more space than is currently needed by some factor r.
        
        s=logr(m/a). s:number of steps(array copies), r:extend factor, a original array size, required array size
      - Trees
        
        Can represent hierarchical relations in data
        
        Depending on implementation can provide worst case operations of O(log(n))
        
        Self balancing trees
        
        AVL
        
        Red Black tree
        
        Root and all null nodes are black (all leaves have two null children nodes)
        
        All paths from root to leaves have the same number of black nodes
        
        On all paths there are never two red nodes consecutively. Red nodes can only have black children
        
        min path length of b max path length of 2b-1
        
        2-3
        
        Unbalanced binary tree
        
        Creating a binary tree from n an array of length n is n*lg(n) (as there are n inserts)
        
        Max/min Heap
        
        Not total ordering only provides a good way of getting max value
        
        every node >= its child nodes
        
        all leaves must be at either h-1 or h. The tree needs to be complete or almost complete
        
        Operations
        
        Heap max - max on heap O(1)
        
        Max heapify - maintain the max heap O(lgn)
        
        Assumes left node and right node are both valid max/min heaps and that i is the problem node
        
        swaps nodes down tree until valid heap
        
        Heap Extract Max - Pops max value of heap and maintains heap properties O(lgn)
        
        Max Heap Insert - Inserts new item into stack O(lg n) while maintaining heap properties
        
        Insert node into next available spot in the level and bubble up the tree
        
        Build max heap - takes array and produces heap
        
        Heap sort is O(n lgn), it is inplace, it is not stable
      - Linked List
      - HashMap
        
        Hashing rules. What are good criteria for hashing algorithms
        
        How to deal with clashes
    - - set: overwrite at position
      - append: add item to the end of the structure
      - add item to middle of strucutre (displaces items, but doesn't overwrite or delete)
    - - Queues
        
        array
        
        linked list
      - Stacks
        
        linked list
        
        array
      - Dictionary
        
        data not stored in sequential order
        
        stored as key value pairs
        
        Usually implemented as a HashMap
        
        no two items have the same key
      - Set
        
        same idea as a mathematical set
        
        There is no order to the items
      - Priority queue
        
        Max heap
        
        Red black tree. Has O(lg n) max heap so isn't as good as max heap
      - Graph: a set of vertices and edges connecting vertices
        
        can be directed or undirected
        
        Implementations
        
        Adjacency matrices
        
        Adjacency lists
- - - - Finds shortest path (by smallest number of edges) to all vertices in the graph
      - produces tree with all reachable vertices
      - white node undiscovered, grey node discovered not visited, black node discovered and visited.
      - Uses a queue to visit the nodes in a breadth first fashion. This means that for each depth level (number of edges away from start node)) it visits all the nodes before descending to another depth level.
      - Time complexity is O(V + E)
    - - Can perform topological search for DAG
      - Decomposing DAG into strongly connected components. Strongly connected if every component can reach every other component