Please enable JavaScript.

Coggle requires JavaScript to display documents.

cs 361 part 1 - cs381 module 4,5 - Coggle Diagram

- - - - \(p = \frac{numberOfCasesFavorableToDesiredOutcome}{numberOfEquallyLikelyToOccurCases}\)
      - ex:
        
        coin toss: probability i get heads
        
        p (heads) = \(\frac{1(numberOfOutcomesHeadsWillOccur)}{2(numberOfEquallyLikelyOutcomes)}\)
    - - only one of outcomes can occur at time
        
        ex:
        
        coin toss: i can only ever get heads or tails
      - P(A or B)
        
        \(P(A) \cup P(B)\)
        
        P(A) + P(B)
      - "add" probabilities together
    - - one outcome or multiple can occur at the same time
        
        to find the likelihood of one or the other, but not both, occuring:
        
        P(A) + P(B) - P(AB)
        
        "add" likelihood of each outcome occuring on its own, "subtract" probability of multiple outcomes occuring at once
      - P(A and B)
        
        P(AB)
    - - occurence of one event has no effect on probability of other events occuring
        
        ex:
        
        coin toss: likelihood of getting heads once and tails once
        
        1/2 * 1/2 = 1/4
      - multiply each event's probability together
      - P(A) * P(B) * P(C)
    - - occurence of one event affects the likelihood of another
      - \(P (\frac{A}{B})\)
        
        Probability of A when B has occured
        
        \( (\frac{P(A \cap B}{(B)})\)
        
        \(P (\frac{B}{A})\)
        
        \( (\frac{P(A \cap B}{(A)})\)
        
        probability of both occuring over probability of denominator occuring
- - - - types of search algorithms
        
        linear search
        
        locates item in list by looking at each element in order one at a time
        
        worst case: O(N)
        
        binary search
        
        compares element to be found with middle element in a list, if the middle element is lower than the element being searched, searches upper half of list
        if middle element is higher than the element being searched, it checks the bottom half of the list
        
        worst case: O(N/2) = O(N)
    - - 3 types of sorting algorithms
        
        bubble sort
        
        insertion sort
        
        worst: \(O(N^2) \)
        
        average: \(O(N^2) \)
        
        merge sort
        
        worst: \(O(N \text{ log } N) \)
        
        average : \(O(N \text{ log } N) \)
        
        best: \(O(N \text{ log } N) \)
        
        speed limits
        
        pair-wise comparison
        
        compares two elements at a time
        
        average time no greater than \(O(N^2) \)
        
        adjacent-swap comparison
        
        swaps two elements at a time
        
        average time no greater than \(O(N^2) \)
        
        quick sort
        
        average: \(O(N \text{ log } N) \)
        
        worst: \(O(N^2) \)
    - - types of optimization algorithms
- - - - \(O(\text{ log } n) \)
      - \(O(n \text{ log } n) \)
      - \(O(N^2) \)
        
        double nested loop both from 0 to N
      - \(O(N^3) \)
        
        triple nested loop both from 0 to N
      - \(O(2^N) \)
      - \(O(N) \)
        
        loop from 0 to N
      - \(O(1) \)
        
        array addressing (if array is made of primitives/O(1) components)
        
        arithmetic, assignment, & relational operations on primitive types
        
        pointer dereferencing (but not operations done on derefenced pointers, that depends on what data type is at that address)
        
        member selection operator(dot operator) (.)
        
        pointer derefence + member selection operator (->)
    - - while
        
        init + cond + incr + (body * iterations)
      - for
    - - O(condition) + then/else(whichever is bigger)
        
        if the one of either the then or else statements will never be executed, their complexity is ignored
    - - add together
    - - # of recursive calls * complexity of body
- - - - pre-order
        
        examines node, processes data at node, moves on to children of that node
        
        1245367
        
        *+13a-x1
      - in-order
        
        used in binary trees
        
        examines node, examines left child of that node, processes left child data, then returns to that node and processes its data, then examines right child and examines its data,
        
        4251367
        
        13+a*x-1
      - post-order
        
        examines node, examines children of that node, processes data of children of that node before processing that node
        
        4526731
        
        13a+x1-*
      - level-order
        
        process nodes at same height before moving on to nodes beneath them
        
        1234567
      - 1
        / \
        2 3
        / \ / \
        4 5 6 7
      - *
        / \
        + -
        / \ / \
        13 a x 1
    - - sequence of nodes where the first node is a parent of the next node and each node after that is a child of the previous node
      - three valid types
        
        [parent, child, child of child, etc..]
        
        [one node]
        
        [] (empty sequence
    - - root
        
        parent
        
        child
        
        sibling
        
        a node which shares a parent with another node
        
        leaves
        
        node without children
      - height
        
        height of a node = length(number of edges) of longest path from that node to any leaf
      - depth
        
        depth of a node = length of path(number of edges) from root to that node
        
        depth of root = 0
    - - binary
        
        each node can only have <= 2 child nodes
        
        binary search trees
        
        children on left <= parent, children on right >= parent
        each node >= its left descendents, and <= its right descendents
      - general
        
        can have (but does not have to) more than 2 child nodes per node
  - - - 3 hash-based
        
        unordered map
        
        unordered multimap
        
        unordered multiset
      - 4 tree-based
        
        set
        
        map
        
        multiset
        
        multimap
    - - initializer list
      - vector
      - deque
      - list
      - 2 adapters
        
        queue
        
        can convert deque or list into queue
        
        stack
        
        can convert vector, list, or deque into stack
      - array
- - - - for (i = 0; i < N; ++i){
        a[i] = 0;
        for (j = 0; j < N; ++j){
        a[i] = a[i] + i*j;
        }
        }
        
        how many times is each line iterated through?
        
        line 1: N iterations
        line 2: N iterations
        line 3: \(N^2\) iterations
        line 4: \(N^2\) iterations
        
        how many assignments
        
        line 1:1st: i=0 = 1 times
        ++i N times
        = N + 1 assignments
        
        line 2: a[i] = 0; N times
        = N assignments
        
        line 3:
        j = 0 N times
        ++j \(N^2\) times
        = \(N^2+ N\) assigments
        line 4: a[i] = a[i] + i*j \(N^2\) times
        = \(N^2 + N\) assignments
        
        how many comparisons
        
        line 1: i<N N times
        then one more where i will = N
        = N + 1comparisions
        line 3: j<N \(N^2 times\)
        then one more before j=N which will happen N times
        = \(N^2 + N\) comparisons
        
        how many additions
        
        line 1: ++i N times
        =N additions
        
        line 3: ++j \(N^2 times\)
        line 4: a[i] + i*j \(N^2 times\)
        bonus:
        line 2: a[i] = 0; N times
        line 4: line 2: a[i] N^2 times
        a[i] N^2 times
        = \(3N^2 \)
        
        how many multiplications
        
        line 4: i*j \(N^2 times\)
        bonus:
        line 2: a[i] = 0; N times
        line 4: line 2: a[i] N^2 times
        a[i] N^2 times
        = \(3N^2 \)
        
        side note: a[i] = 1 addition and 1 multiplication and 1 assignment
        (base address of array + index * size in bytes of a
      - inner loop runs through elements every iteration of the outer loop