> For the complete documentation index, see [llms.txt](https://ysfang82.gitbook.io/development-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ysfang82.gitbook.io/development-notes/data-structure-and-algorithm.md).

# Data Structure & Algorithm

**Time Complexity Expressions:**

* Omega: best scenario
* Theta: average scenario
* Big-O: worst scenario
  * [Big-O cheatsheet](https://www.bigocheatsheet.com/)

**Trees**

* [BST (Binary Search Tree)](https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/)
  * Adding element according to status of children (can become an unbalanced BST in worst cases).
  * Having `Θ(log N)`, `O(N)` for access, search, insertion, deletion due to the BST is balanced or not.
* Red-black Tree
  * Self-balanced (not perfectly balanced) BST with `O(log N)` for searching, insertion, deletion.
* Heap
  * Adding elements from left to right and check its ancestors (no need to re-balancde it.)
  * Good at finding max / min and adding elements. Ex. priority queue, sorting algorithm.
  * Having `O(1)` for finding max /min, `O(log N)` for insertion, deletion, `O(N)` for lookup.
* Trie (prefix tree)
  * Usually a empty root node, can have multiple children nodes.
  * For auto-completion lookup.
* Tree Traversal (Depth First Search)
  * Pre-order: **self** -> left -> right.
  * In-order: left -> **self** -> right.
  * Post-order: left -> right -> **self**.

**Sorting**

* [Types and Implementations](http://www.java2novice.com/java-sorting-algorithms/):
  * Selection Sort (not practical)
    * IMPL: Search the min (max) value and swap to the front in each round.
  * Bubble Sort (not practical)
    * IMPL: Compare with neighbor and swap.
  * Insertion Sort
    * **Good at dealing with small data set (or almost sorted data set).**
    * IMPL: Create sub-group with size 1 at the front, move edge element into sub-group by bubble sorting in each round.
  * [Merge Sort](http://www.java2novice.com/java-sorting-algorithms/merge-sort/)
    * Stable time complexity: `N log N`, but space complexity is `O(N)`.
    * IMPL: A recursive function to split array (sub-array) into 2 halves till becoming single element and then merge them back.
  * Quick Sort
    * Good space complexity with `O(log N)`, and time complexity: linearithmic `Θ(N log N)`and quadratic `O(N^2)` if chosed worst pivot.
    * IMPL: 
      * Choose strategy for pivot (Ex. at the end.)
      * A recursive function to :
        * (1) move elements larger then pivot to the right, keep smaller elements at the left.
        * (2) sub-array at the left calls step (1)
        * (3) sub-array at the right calls step (1)
  * [Heap Sort](https://www.geeksforgeeks.org/java-program-for-heap-sort/)
    * Stable time complexity: `N log N`, and good space complexity: `O(1)`.
    * IMPL: Given root as index: `0`.
      * index of parent: `(i - 1) / 2`
      * index of left child = `2i + 1`.
      * index of right child: `2i + 2`.
  * [External Sort](https://www.geeksforgeeks.org/external-sorting/)

**Searching**

* Linear search (checking elements sequentially)
* Binary search (check sorted elements from the middle)
* BFS
  * Good at finding shortest path, but takes more memory to keep track of neighbors.
  * Impl: Queue
* DFS
  * To identify a path especially when it's far away from the source (Ex. a maze), with less memory.
  * Impl: Stack

**Recursion**

* [Fibonacci](https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)
  * Time complexity: `O(2 ^ N)` (exponential, pronounced as "two to the N").
* Find tree depth
  * `return 1 + Math.max(findMax(node.left), findMax(node.right));`

**Dynamic Programming (Caching)**

* Fibonacci
  * Time complexity: `O(N)`, space complexity: `O(N)`.

**Graph**

* Example
  *   `2 - 0`\
     `/ \`\
    `1 - 3`
* Example with primitive representations
  * Edge List
    * `int[][] data = {{0, 2}, {1, 2}, {1, 3}, {2, 3}};`
  * Adjacent List
    * `int[][] data = {{2}, {2, 3}, {0, 1, 3}, {1, 2}};`
  * Adjacent Matrix
    * `int[][] data = {`\
              `{0, 0, 1, 0},` \
              `{0, 0, 1, 1},` \
              `{1, 1, 0, 1},` \
              `{0, 1, 1, 0}};`
* Finding shortest path with weight
  * Dijkstra's algorithm (more effecient but can only take positive weight)
  * Bellman-Ford algorithm (can take negative weight)

**Bit Manipulation**

* [Find the single number in an array](https://leetcode.com/problems/single-number/)

**Linear Algebra**

* Matrix 
  * [Multiplication](https://en.wikipedia.org/wiki/Matrix_multiplication)
  * [線性代數的第一堂課──矩陣乘法的定義](https://ccjou.wordpress.com/2010/06/18/線性代數的第一堂課-矩陣乘法的定義/)