Covers abstract data types and structures including dictionaries, balanced trees, hash tables, priority queues, and graphs; sorting; asymptotic analysis; fundamental graph algorithms including graph search, shortest path, and minimum spanning trees; concurrency and synchronization; and parallelism.

Data Structures and Parallelism.md

General knowledge:

• Data Structures: "clever" ways to organize information in order to enable efficient computation over that information
• Trade-offs: time vs. space, efficiency, generality vs. simplicity vs. performance
• ADT: Description of a "thing" with set of operations unit
• Algorithm: high level description of step-by-step process

Analysis:

• Comparing using large inputs because it is plenty good for small inputs
• Consecutive: Sum of each
• Conditional: condition + slower branch
• Loop: number of iterations * time for loop's body
• Function: time of function's body
• Recursion: solve recurrence's equation
• 2^x > x^2 > x * log(x) > x > log^2 (x) > log(x) > 1
• Upper Bound: g(n) is Big-Oh(f(n)) iff there exists c and k such that g(n) <= c * f(n) for all n >= k
• Lower Bound: g(n) is Big-Omega(f(n)) iff there exists c and k such that g(n) >= c * f(n) for all n >= k
• Tight Bound: g(n) is Big-Theta(f(n)) iff Big-Og(f(n)) and Big-Omega(f(n)) happen
• Recurrence relation:
• Linear: T(n-1) + O(1), 2 * T(n/2) + O(1), T(n/2) + O(n)
• Log: T(n/2) + O(1)
• Exponential: 2 * T(n - 1) + O(1)
• Quad: T(n - 1) + O(n)
• O(n * log(n)): 2 * T(n/2) + O(n)

Stack: LIFO

• Methods: push, pop, top/peek, isEmpty
• Implemented using linked list or array
• Uses: balancing symbols or postfix notation

Queue: FIFO

• Methods: enqueue, dequeue, isEmpty
• implemented using circular array or linked list

Priority Queue:

• A queue that holds Comparable data

BST:

• Terms for tree: root, leaves, children, parent, siblings, ancestors, descendents, subtree, depth, height, degree, branching factor, perfect tree, complete tree
• Height h means 2^(h+1) - 1 nodes and 2^h leaves
• n nodes means height = log(n)
• Minimum number of leaves is 1 and minimum number of nodes is h + 1
• Delete node : findMin(node.right) or findMax(node.left) and delete that node after replacing value

Heap:

• A complete tree that priority of every non-root is greater than the priority of its parent
• Implemented using array by skipping index 0, left child at index 2 * i, right child at index (2 * i) + 1 and parent at index i / 2
• insert: percolate up (swap parent if larger)
• deleteMin: percolate down (choose smaller child)
• buildHeap: using Floyd's algorithm: put everything in the array then fix everything from index size / 2 to index 1 by percolating down
• Worst time for insert and deleteMin is O(log(n)); buildHeap is O(n)

AVL Tree:

• A self-balancing BST such that the heights of the two child subtrees of any node differ by at most one
• Minimum number of nodes is S(h) = S(h - 1) + S(h - 2) + 1 at height h
• Insert or delete means checking balance: 4 cases:
• Single rotation: rotate left or rotate right
• Double rotation:
  • Right left: right node = left rotation and then rotate right
  • Left right: left node = right rotation and then rotate left
• Worst time for insert, find and delete is O(log(n)); buildTree is O(n * log(n))