# Fundamentals Of Data Structures
[交大開放式課程](http://ocw.nctu.edu.tw/course_detail-v.php?bgid=9&gid=0&nid=412)

[Ctutor](http://pythontutor.com/c.html#mode=edit)

## Chapter 1. Basic concepts

### Overview: System Life Cycle
#### Requirement
系統的需求
#### Analysis
* Bottom-up
* Top-down
#### Design
* Data objects: abstract data types
* Operations: specification(function) & design of algorithms(設計演算法達到 function 的目的)

#### Refinement & Coding
* Choose representations for data objects
* Write algorithms for each operation on data obejcts

#### Verification
* Correctness proofs: selecting proved algorithms
* Testing: correctness & efficiency
* Error removal: well-document

### Evaluative judgments about programs
* Meet the original specification?
* Work correctly?
* Document?
* Use functions to create logical units?
* Code readable?
* User storage efficiently?
* Running time acceptable?(as fast as possible)

### Data Abstraction
* Predefined & user defined data type

Struct student{
    char last_name;
    int student_id;
    char grade;
}

* Data type: objects & operations (加減乘除等等)
* Reoresentation: char 1 byte, int 4 byte
* Abstract Data Type (ADT): data type specification(object & operation) is separated from representation.
* ADT is implementation-independent(與實作無關，ADT 僅定義如何做，但沒有實作細節。p.20 Abstract data type NaturalNumber)

### Algorithm Specification
#### Algorithm criteria
* Input
* Output
* Definiteness
* Finiteness
* Effectiveness

演算法是用來解決問題的方法，演算法中的 input and output 表示了你的問題。我們會希望我們的演算法能夠有效率且能夠在有限的步驟內，解決問題。

最簡單的演算法，排序。
input: 一串數值。
output: 一串數值，但需依照大小順序排好。

**program doesn't have to be finite(e.g. OS scheduling)**

### Example 1: Selection Sort

* From those integers that are currently unsorted, find the smallest and place it next in the sorted list.

// 虛擬程式碼
for(i=0; i < n; i++){
    Examine list[i] to list[n-1] and 
        suppose that smallest integer is list[min]
    Interchange list[i] & list[min]
}

void sort(int list[], int n)
{
    for (i=0; i < n-1; i++){
        min = i;
        for(j = i+1; j < n; j++){
            if(list[j] < list[min])
            min = j; }
            SWAP(list[i], list[min], temp)
        }
    }
}

### Example of Binary Search

Search 最暴力的方法：一個一個去確認搜尋。
在執行 Binary Search 前需要先進行排序。
圖中 * 為二分點
不一定找得到輸入的數值


// pseudo code
While (there are moree integers to check){
    middle = (left + right) / 2;
    if(searchnum < list[middle])
    right = middle -1 ;
    else if(searchnum == list[middle])
        return middle;
        else left = middle+1;
}

int compare(int x, int y)
/* return -1 for less than, 0 for equal */

int binsearch(int list[], int searchno, int left, int right)
{
    while (left <= right){
        middle = (left + right) / 2;
        switch (COMPARE(list[middle], searchno)){
            case -1: left = middle +1;
                    break;
            case 0: return middle;
            case 1: right = middle -1
        }
    }
}

**不要為了學語言而學語言，學會解決問題的方法。**

### Example 3: Selection Problem
* Selection problem: select the kth largest among N number
* Solutions:

    * Approach 1
        * read N numbers into an array
        * sort the array in decreasing order
        * return the element in position k
        
    * Approach 2
        * read k elements into an array
        * sort them in decreasing order
        * for each remaining elements, read one by one
            * ignored if it is smaller than the kth element
            * otherwise, place in correct place and bumping one out of array

* Which is better?
* More efficient algorithm?

### Recursive Algorithms
* Direct recursion: functions that call themselves
* Indirect recursion: Functions that call other functions that invoke calling function again
* C(n, m) = n!/[m!(n-m)!] -> C(n, m) = C(n-1, m) + C(n-1, m-1)
* Boundary condition for recursion (停止條件 Boundary)

**不要讓演算法進入無限迴圈**

### Recursive Factorial
* n! = n * (n-1) -> fact(n) = n * fact(n-1)
* boundary -> 0! = 1

int fact(int n){
    if( n == 0 )    // Boundary condition
        return (1)
    else
        return (n*fact(n-1))
}

### Recursive Multiplication
* a * b = a * (b-1) +a
* a * 1 = a

int mult(int a, int b)
{
    if(b == 1)
        return (a);
    else 
        return ( mult(a, b-1) + a )
}

### Recursive Summation
* sum(1, n) = sum(1, n-1) + n
* sum(1, 1) = 1

int sum(int n){
    if(n == 1)
        return (1);
    else 
        return ( sum(n-1) + n )
}

也可以直接使用 for 迴圈寫完

### Recursive binary search

int binsearch(int list[], int searchno, int left, int right)
{
    if(left <= right){
        middle = (left + right) / 2;
        switch(COMPARE(list[middle], searchno)){
            case -1: retrun binsearch(list, searchno, middle + 1, right)
            case 0: return middle;
            case 1: return binsearch(list, searchno, left, middle - 1)
        }
    }
    return -1;
}

### Recursive Permutations
* Permutation of { a, b, c }

(a, b, c), (a, c, b)
(b, a, c), (b, c, a)
(c, a, b), (c, b, a)

* Recursion?
* a + Perm({b, c}) -> {a, b, c} and {a, c, b}
* b + Perm({a, c}) -> {b, a, c} and {b, c, a}
* c + Perm({a, b}) -> {c, a, b} and {c, b, a}


void perm(char *;list, int i , int n){
    if(i == n){
        for(j = 0; j <=n; j++)
            cout<<list[j];
    }else{
        for(j = i; j <= n; j++){
            SWAP(list[i], list[j], temp);
            perm(list, i+1, n)
            SWAP(list[i], list[j], temp)
        }
    }
}

Q. 字元排序問題如果不用 recursive 要怎麼解決？ for loop？

### Performance Evaluation
* Performance analysis: machine independent
* Performance measurement: machine dependent

### Performance Analysis
* Complexity theory
* Space complexity: amount of memory
* Time complexity: amount of computer time

### Space Complexity

### Time Complexity

* Worst case
* Best case
* Average case


### Asymptotic Notation - Big "oh"

### Asymptotic Notation - Omega
The most important is most lower bound.

:::info
如何計算 recursive 的時間複雜度。








https://github.com/illuminate/support/blob/master/Arr.php#L207

10 ans. D
:::

Int a = 0
Int* c = &a
*c = 1

Int b = 10
c = &b
*c = 3

## Array

Array: a set of index and value
* data structure
For each index, there is a value associated with that index

Array ADT


:::info
:::

https://youtu.be/cgaPEsMJkSc?t=3132


https://blog.gtwang.org/programming/memory-layout-of-c-program/

001080
000000
040300
600000
000000
050000
000000

array[7][6]

| - | - |
| - | - |
| 0 | 765 |
| 1 | 021 |
| 2 | 048 |
| 3 | 214 |
| 4 | 233 |
| 5 | 515 |

12345
06789
00abc
000de
0000f

index of e = 13
index of any (x,y) where x >= y in n by n matrix = ((n+1) + n-i +1) * i / 2 + (j - i)

---

https://docs.google.com/presentation/d/1PfNCvxJV_pOozArub_N-99-fXwu7yNw_Lt3EjlVKLiU/edit#slide=id.p

## Array

int list[5]: 存放5個int的array
int* plist[5]: 存放list[5]內5個int的pointer的array

陣列內value存放的記憶體空間為連續
*plist = list[0]: base address = alpha
list[1]: address = alpha + sizeof(int)
list[2]: address = alpha + 2*sizeof(int)
...

---

### loser me

10歲的james薪水就有35000 QQ

---

### polynomial

* purpose：do the basic oparation like addition or substraction

#### 表示方法1:
x^4^+10x^3^+3x^2^+1 = [1, 0, 3, 10, 1]

| 0 (constant) | 1 | 2 | 3 | 4 |
| - | - | - | - | - |
| 1 | 0 | 3 | 10 | 1 |

Example:
a = 3x^20^+2x^5^+4 = [4, 0, 0, 0, 0, 2, 0, ... , 0, 3]
b = x^4^+10x^3^+3x^2^+1 = [1, 0, 3, 10, 1]
result = []

1. compare a.count and b.count: a>b -> case 1
result[20] = a[20]
a.remove(index: 20)
(到a[5]前皆同)

沒有2，因為我懶得打惹

#### 表示方法3:

若多項式為 2x^1000^+1 = [1, 0, ... , 0, 2]
則Array多數空間被浪費 -> 用一個global array存放所有多項式

A(x) = x^1000^+1
B(x) = x^4^+10x^3^+3x^2^+1

| | A Start | A Finish | B Start | | | B Finish | free |
| - | - | - | - | - | - | - | - |
| coef | 2 | 1 | 1 | 10 | 3 | 1 | |
| exp | 1000 | 0 | 4 | 3 | 2 | 0 | |
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |

* free: 允許加入其他多項式 or 存放相加後結果
* 須清楚各多項式的起始及終點位置所對應的index值

Example:
1. Compare A-start and B-start's exp: A-start>B-start -> case 1
copy A-start to free
free++

#### complexity = O(n+m)

* 若free超過了一開始宣告的maxTerm:
* 回收(destruture)已做過運算且不會再使用的polynomial
* 缺點: release後的空間不連續
* 須改寫程式碼以避免問題，大家自己回家想一波，期中考會考 😈

---

### Sparse Matrix

* 矩陣內大部分element為0，使用2-dimension array紀錄hen浪費空間
* 使用1-dimension array紀錄非0的element的<row, column, value>
* 排序先row再column

### 矩陣轉置

#### dumby method

* row與column值互換
* 互換後需再重新檢查並排序array，調整時間成本高
* O(column * term)

#### smart method

* 先統計transport後各個row有幾個element，紀錄位置後再進行transport
* O(row * column)

### 矩陣相乘

* result(i,j) = sigma(a(i,k)*b(j,k))

### 矩陣存放

* 先存row再存column(row major)

---

### String的存放

#### 英文

| H | E | L | L | O | | W | O | R | L | D | \0 |
| - | - | - | - | - | - | - | - | - | - | - | - |

#### 中文

* 中文的字串處理(自己google)
* 資料檢索

### 字串的運算

* string match
* 字串串接
* tring copy
* string insert
* trim
* print

### String match

* 查詢P字串有無在T字串內出現

#### dumby method

* 從P1/T1開始比對，若不吻合則shift一格，比對P1/T2直到吻合或回報-1
* O(mn)

#### KMP

* 建構可快速移動的failure array，再由此加速字串比對
* O(m+n)

### KMP

#### first case
* 從P1/T1開始比對，若在P4/T4處不吻合，則直接shift至比對P1/T4

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | - | - | - | - | - | - | - | - |
| A | G | C | **C** | T | A | T | C | A |
| A | G | C | **G** | G |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| - | - | - | - | - | - | - | - | - |
| A | G | C | C | T | A | T | C | A |
| | | | A | G | C | G | G |

#### second case

* 當字串不吻合時，發生不吻合的字元前(已比對過的字元)若有與字首吻合的字元，則不需再做比對

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| - | - | - | - | - | - | - | - | - | - | - | - | - |
| A | G | C | C | T | **A** | **G** | C | T | C | A | T | T |
| **A** | G | C | C | T | **A** | **C** |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| - | - | - | - | - | - | - | - | - | - | - | - | - |
| A | G | C | C | T | **A** | G | C | T | C | A | T | T |
| | | | | | **A** | G | C | C | T | A | C |

#### third case

* second case在非單一字元的情況下同樣適用(failure array)

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| A | G | C | C | G | **A** | **G** | **G** | T | C | A | T | T | A | G | T | A | A |
| **A** | **G** | C | C | G | **A** | **G** | **C** | A | G | G | C |

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| A | G | C | C | G | **A** | **G** | G | T | C | A | T | T | A | G | T | A | A |
| | | | | | **A** | **G** | C | C | G | A | G | C | A | G | G | C |

### failure function


#### example

| q | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| - | - | - | - | - | - | - | - |
| p | a | b | a | b | a | c | a |
| ㄇ | 0 | 0 | 1 | 2 | 3 | 0 | 1 |

## Stack and Queue

### Template

* 當data type改變時，對function本身沒有影響

### Stack

* last-in-first-out(LIFO)
* top
* abstract data type(ADT)
* top
* finite order list
* Boolean IsFull()
* void Push/Add(const KeyType & item)
* Boolean IsEmpty()
* KeyType* Delete/Pop(KeyType &)
* 可用array inplement(但array不是唯一)

#### 迷宮老鼠


* 有幾種走法(8個方位)
* 用stack存放行走路徑[row][column][dir]，若無法前進則pop回前一步
* 圍牆用1表示
* maze記錄曾經走過的path
* move決定行走方位
* mark記錄有無走過
* 存不存在一條路徑到達終點
* 是否為最短路徑
* 出口位置未知
* 出口數量不只1個

#### Operate

* Postfix evaluation


* infix轉postfix
* 先括弧、移項後刪除
* */的priority大於+-


* priority table


### Queue

* first-in-first-out(FIFO)
* job schedule
* 排隊即queue
* Priority Queue(插隊仔)
* abstract data type(ADT)
* front / rear
* 其他跟stack差不多
* 因資料delete後不進行搬移，故queue size(IsFull())可能造成誤判
* data movement
* 修改procedure
* 環狀queue(保留一個空間去做判斷)
* front = rear: empty
* rear + 1 = front: full
* delete front + 1

## Linked List

### Array

* 連續的記憶體空間
* 有大小限制
* 有空間浪費問題
* 當資料做增減時，可能產生誤判

### Linked List

* 有序
* element中存放資料以及pointer(存放下一筆資料的記憶體位置)
* insert資料時，assign插入資料的記憶體位置給上一筆資料的pointer，並將插入資料的pointer指向下一筆資料的記憶體位置。
* 刪除資料時，需先依序搜尋資料是否存在以及存放位置，再對pointer重新做assign，搜尋成本高。(element可刪除可不刪)
* double linked list
* 可從頭尾同時搜尋，降低搜尋成本。
* 可避免pointer鏈結斷掉造成找不到下一筆資料的情況。

### Implement Linked List

* Composite Classes
* class Node: data, next pointer
* class List: first node
* 優點：class Node可共用
* 缺點：自己想

* Nested Classes
* class List: class Node
* class Node: data, next pointer
* 缺點：共用需要再複製一份
* 優點：自己想


### insert

### delete

### list iterator

* 一個 class 存放 scan, number of element, first, isEmpty...(因重複使用率高)

### invert a list

* 反轉 linked list 所有 pointer
* first重新assignment


### Concatenating

* if p,link = null {p -> link = b.first} else {p.link = p}

### list desctrutor

* delete first

### circular list

* 需註明first與last

`linked list也可用來表示polynomial以及stack and queue`

### polynomial

* 相加
* 指數部分相同->係數相加
* 不同-> copy較大者係數
* 複製後pointer往後走
* 直到兩者pointer都為null為止


### free pool

* delete掉的node丟進free pool裡，不先destructor。要創建新的node時可從free pool中取用(first)再修改值，可減少系統請求記憶體空間的程序。
* 環狀linked list -> 可將polynomial一次return進free pool

### equivalence relations

* symmetric
* reflexive
* transitive


* phase1 - 讀完所有的pair，process未處理的pair(seq array w/ directive equivalence linked list)
* phase2 - output結果(output array: output過的index轉成true)
(使用stack尋找indirect的equivalence number(transitive))
* input順序不同會造成output的set內容順序不同，但element相同

### Sparse Matrix

每個row與column都會對應到一個環狀的linked list

* 藍色代表是4 by 4的matrix
* header node僅有一藍四黃(左與上為同一組head node)
* 紅線為column構成的linked list
* 黑線為row構成的linked list
* 數字的左上/右上代表pointer，指向對應的row及column
* 如果要做transport，需調換row/column及改變pointer


### Doubly linked list

* 有llink及rlink 2個pointer
* header node 的 rlink 指向linked list的first，llink指向linked list的last
* insert(修改4個pointer)/delete(修改2個pointer)

## Tree

* a collection of nodes
* a distinguished node root
* zero or more nonempty (sub)trees
* level: height of tree(長得像大ray哥的老師在他家祖譜排level 32)
* degree: number of pointing out
* parent: 最原始的祖先

### 表示法

#### linked list表示法
* ( A ( B ( E ( K , L ) , F ) , C ( G ) , D ( H ( M ) , I , J ) ) )
* 如果n個node就件n筆資料(n個pointer)，很浪費memory(?)
* 整理成2元樹，每個node只記錄left child及right child

#### binary tree

* child只有2個(right/left)
* 允許zero node
* 在binary tree裡，如果level是i，最多的node數為2^i-1^
* maximum number of pointer (B): B+1=n

**(the properties of binary tree沒聲音)**

* full binary tree: has maximum number of node
* complete tree: 照次序排列的樹
* skill tree: child偏向依邊的歪斜樹

#### Array表示法

* 次序編號: index -> 丟入相對應的value
* left child: even value = 2i
right child: odd value = 2i+1
i=1: parent node

#### 優缺點

array: 可快速查找，但skill tree容易遇見空間的浪費
linked list: 查找困難

### binary tree traversals
* 快速得知tree的結構，以便比較及複製
* **LVR(inorder), LRV(postorder), VLR(preorder)**, VRL, RVL, RLV
* L: 往左查訪
* R: 往右查訪
* V: 印出資料
* recursive function or using a stack/queue

#### inorder

* recursive
* inorder(currentNode -> left child);
* cout << currentNode -> data;
* inorder(currentNode -> right child);
* stack
* 往左走訪
* 有child -> 加入stack
* 沒child -> pop out the last element in stack and visit the right child

#### preorder

* recursive
* cout << currentNode -> data;
* inorder(currentNode -> left child);
* inorder(currentNode -> right child);

#### postorder

* recursive
* inorder(currentNode -> left child);
* inorder(currentNode -> right child);
* cout << currentNode -> data;

#### level order

* 照index順序


* only inoder can check two trees equal

### Propositional calculus expression

#### boolean tree(供三小)



* use postorder -> evaluate expression value
* the last element is the root

### Threaded Binary Trees（ㄅ重要）

* 讓 tree 裡沒有被使用的node 被充分利用 -> 使用 inorder 讓空的 node 指向他上一個或下一個 node
* 可快速查找 inorder 順序


* 實線：原本的 tree
* 虛線：thread binary tree，每個 element 都指向他前後的 2 個 element

#### 缺點
* 多增加了 2 個欄位空間
* 增加了 insert 和 delete 的難度

### Huffman code

* 目的在於用最少的 code text 進行編碼
* 根據 message 的使用頻率來決定表達方式
* 例如出現頻率若最高，就用最少的單位(minimum code size)表示，使解碼的速度加快


* M1 = 000
M2 = 001
...依此類推

#### huffman function

* 建立方法
* bottom-up
* 先選頻率最小的 2 個 message 並 merge 出現頻率
* 將 merge 後的頻率加入比較，再選出最小的 2 個 message 並 merge


* 程式
* 宣告一個 binary tree 的 priority queue
* 選最小的 2 個 element(最前面 2 個) merge
* delete 已被 merge 的資料
* insert merge 後的資料(priority queue)
* 呼叫自己
* huffman code 並不唯一


### Priority Queue(heap)

* 為 complete binary tree
* 分 maximum 與 minimun，差在 return 值以及 root
* maximum/minimum heap 只在乎 tree/subtree 的 root 是 maximum/minimum，其餘 leaves 的排列隨便


#### insert

* bottom-up
* insert element 到最一個位置
* 若 leaf 比 root 大則進行交換，最多交換 logn次

#### delete

* top-down
* 將最上面的 element output
* 把最後一個 element 放到 root 的位置
* 若 leaf 比 root 大則進行交換，最多交換 logn次

#### heap sort

* 建立 minimum/maximum heap tree
* insert n 個 element
* delete(pop out) n 個 element

### Binary Search Tree

* delete max/min: O(logn)
* delete arbitary: O(n)
* search: O(n)
---
* element of left-subtree < root < element of right-subtree

#### search

* 若所蒐數值比 root 小 -> 查找左邊，比 root 大 -> 查找右邊，直到找到 null 為止
* 找第 n 大的數字 -> sorting(maximum heap tree)

#### size

(???-36:30)

#### Insert

* 跟 search 差不多

#### delete

* 刪除指定 element
* 只有左/右子樹 -> 直接拉上去
* 同時有左右子樹 -> 拉左子樹裡最大的 element 或右子樹裡最小的 element

#### AVL tree

* 將 binary search tree 調整成左右 level 相差不大於 1

### selection tree

* 每個 leaf node 分別是一個 queue
* 可輕鬆做排序

#### winner tree

??? - (52:00)
* 大量數字排序，memory 無法開另一個空間存放時

#### loser tree

### Forest

* a set of tree

#### forest traversal


#### disjoint set union

* 兩種做法的優缺點取決於 element 被查找的頻率


#### weighting rule

* root i 的 leaf 若比 root j 少，則 union 時把 j 當成 root
* 猶豫的ppt https://www.csie.ntu.edu.tw/~hsinmu/courses/_media/dsa_17spring/disjoint_set.pdf

## Graph

* vertice(V) & edge(E)
* 一比劃問題
* 電路分析
* 最短路徑問題
* 專案規劃
* social science(fb)

### 一筆劃問題

* 七條橋(經典)
* Euler's graph -> 每個點的 degree 僅能為偶數

### 最短路徑問題

* 地圖

### graph 種類

* complete gragh -> 每個點都和其他點有連接
* directed graph -> 有向的


* multigragh -> 當 edge 有其他記憶條件因素時
* DAG -> 有向無環圖
* connected component -> 沒有人是局外人
* strongly -> 每個點都有相互連接(左) or isolated component(右)


### ADT

* 使用矩陣表示點和點之間是否有相連
* 在 undirected graph 下為 symmetry


* 若不是 complete graph，使用 matrix 較浪費空間，可改用 linked list 表示


* 用 one-dimension array(有點複雜)
* 紅色(起始點) -> 與 component 有連接的資料的放置位置
* 缺點 -> 刪除資料麻煩(需要一直 shift)


* adjacent list
* 記載 component 的 out-degree
* inverse adjacent list
* 記載 component 的 in-degree

* multilists
* 以 edge 為出發點
* 記錄跟該 edge 有連接的 node 及其 value
* N 的個數為 number of edge


### weight edge

* 光復路的故事

### traversal

* DFS
* depth preorder traversal
* 向一個方向走到不能再走後，退回上一個component 繼續走訪
* 如果表示方法為 list，複雜度 = O(e)；若為 matrix，複雜度為O(n^2)
* BFS
* level by level
* 先走訪一個component 所有連接的 component
* 走過的 mark 為 1 (boolean array)
* 皆不唯一

### Spanning tree

* sub-graph
* minimum cost spanning tree -> 能用最少的 edge 連接所有 vertice
* 不唯一
* 有 3 個 greedy 的演算法

#### kruskal

* 以 edge 為主
* 從權重最小的 edge 開始選擇
* 不能有 cycle (how to detect loop)
* 使用 priority queue

#### print

* 以 vertice 為主
* 決定一個起點，選擇與起點連接權重最小的 edge
* 再往外擴張

#### sollin

* 一次決定多個起點，選擇起點們連接的最小權重邊
* 結合 kruskal 及 print

### Biconnected components

* articulation point ->在 graph 中若拿掉會使 graph 形成 2 個獨立的 connected components 的 vertice
* 在 graph 中沒有 articulation point 則為 bioconnected component


* 若不被任一 subgraph 包含的話則為 maximum biconnected component
* 可用 DFS 查找，查找完將 graph 中原有的 edge 補完(back edge)


* low -> 以 root 為出發點，DFS 時可以拜訪到對最小數值

(48:00) 為何右邊的最小拜訪值不是 1 ？ 567 為何一樣？

#### find articulation point in programming

* make the DFS spanning tree -> decide DFN(越靠近 root, DFN 值越小)
* 補上 back edge
* 於自己本身的 DFN, child node 的 DFN, 以及 back edge 連接的 node 的 DFN 中取最小值(?)(bottom up)
* root 一定為 articulation point(若選擇非 articulation point 做 root?)，若 u 不為 root ，則與 u 連接的 child node 1 皆無法不通過 u 拜訪 chide node 2， 則 u 為一個 articulation point

### Shortest Path

* Dijkstra
* 從起點開始選擇最小權重邊延伸，直到所有點都被拜訪過為止
* 選定起始點加入陣列，與起始點相連的點更新權重，其餘為無限大
* 將權重較小的點加進陣列裡(已走訪過)，並做為新的起始點，更新與之相連的點的權重
* 重複以上動作
* 全部點都被走訪完畢後，得知起點至所有點的最短路徑
* 要知道 path 則需另外紀錄
* 為 greedy 演算法
* 無法處理有負權重的情況

* Bellman-Ford
* 當只允許走一條路徑時，列出到每個點的最小 cost
* 開放走 2 條路徑，經由上一次的結果更新 cost
* 不斷更新 cost 直到走訪 edge - 1 次
* 若第 edge 次仍可以更新權重，代表 graph 中有負迴圈

### All-Pairs

* a^k^[i][j]: 從 i 走到 j ，最少經過 k 個頂點 = a^k-1^[i][k] + a^k-1^[k][j]

#### Transitive closure

* 做完 all-pair 後，大於1的在 transitive closure 中皆為1，表示可連通， 0 表示無路徑可連通

### Activity-on-Vertex (AOV) Network

* 每個 vertex 代表一個 activity，有先後順序關係。若先決條件的 activity 沒發生，則該 activity 不會發生
* in-degree 為 0 的 output 出來(不拘順序)，output 後對有與 output 連接的 vertex 更新 in-degree
* order 並不唯一


### Activity-on-Edge (AOE) Network

* activity 在 edge 上，vertex 只代表 activity 的開始即結束
* edge 可同時執行
* vertex 紀錄最早完成時間
* 利用 compage order 依序走訪

 

### critical path

* 在 graph 中不能有 delay 的空間
* 先計算每個 activity 的時間
* 在 in-degree 不為 1 的 vertex 前建立 vertex'，edge 為 ?，order 為前置作業的 maximum 值
* 從左往右推 -> 完成需花費最短時間


* 從右往左推(選 minimum) -> 最多可 delay 時間


* critical path: 從右往左及從左往右推的時間相減為 0 的即為 critical path
* critical path 是否一定存在？

## Sorting

* data base: records(key)
* get / set
* scan / match
* return data
* ex: 電話簿
* binary search
* 須先做排序
* 可將 search 複雜度從 O(n) 降至 O(logn)

* internal sort: 要排序的資料皆可放入 memory 中
* insert
* n-1 筆 data 已排序，將第 n 筆 data 插入已排序 data 中適當位置
* recursive
* 將 unsolve 的資料加入已排序資料最後項(A(j))，若A(j)<A(j-1)則做swap，j- -
* selection
* 從未排序資料中挑選最小的資料加入已排序資料
* 最小的資料與第一筆資料 swap 後，將第一筆資料加入已排序資料
* bubble
* 兩兩做比較後如有需要則 swap
* merge
* 合併 2 個已經排序完成的資料
* recursive
* divide and conquer
* 先將資料切成 n 組最小的 set 後，每 2 組做排序合併，合併時需新開一個 array 存放合併後的結果
* complexity: O(nlogn)
* quick
* comparison base 中最快的
* recursive
* divide and conquer
* 在資料中隨機選一筆資料作為分段點，將資料分成比分段點小及分段點大 2 堆，各自再選擇分段點，重複動作
* sampling: 為避免隨機選擇的數字過於偏大或偏小而失去 quick sort 的優勢，可隨機選擇多筆資料，以中位數的資料作為分段點
* 不適合資料筆數少的排序
* complexity: O(nlogn)
* heap
* 建立一個 minimum heap tree，delete root 後重新做調整(O(logn))，共做 n 次 delete(O(n))
* 須建立額外的空間存放 delete 的值
* 若使用 maximum heap tree 則不需額外建立 array 存放 delete 的 element
* 建立 heap: top-down or bottom-up(O(logn))
* bucket
* 根據資料特性建立 bucket，並將資料放入對應的 bucket 中
* implement in queue
* radix
* approach from bucket sort
* most significant bit(MSB): radix-exchange sort，根據最重要的位元進行排序
* least significant bit(LSB): straight-radix sort，根據最小的位元進行排序，recursive 至最大位元後，從最小的 bucket 依序從最底端 output 出來(queue)

* external: data 太大無法放進 memory(目前較少使用，未來趨勢)
* merge
* 假設 memory 只能放進 750 個 record，而資料有 4500 筆
* 將 data 做 partition，分段處理

### weighted external path lenght

* element 的個數及被 merge 的次數乘積的加總
* 可用 huffman-code 解決

### Proof Lower Bound of Sorting

* 在 comparison sorting algorism 中，最小複雜度為O(nlogn)


## Hashing

* hash key(bucket)
* hash funciton
* static v.s. dynamic
* static - hash function 不會隨資料的比數或狀態改變
* dynamic - hash function 會隨資料的比數或狀態調整
* identifier density: n(所有資料)/T(可能的key)
* loading density: hash table 被佔用的情況。n(所有資料)/sb(每個bucket所能容納資料數 * bucket)
* collision: 2 筆資料都要進同一 bucket
* overflow: 資料要進已滿的 bucket
* cardinality: 資料筆數
* degree: 欄位數

### symbol

* directory base
* 可作新增、搜尋、刪除

### Hash Function

* 目標
* 發生 collision 的情況越少越好
* 每個 bucket 的容納資料筆數平均
* 常見形式
* Mid-Square
* 將資料轉成二進位
* 取中間數(不限定幾位)
* 將取出數開平方
* Division
* 取mode
* Fold
* 將資料轉成二進位
* 將轉換後的資料分為好幾個區間，分別去做運算(23:44?)
* 對折
* solve overflow
* open new bucket
* linear: 找附近的空 bucket
* quadratic: 找遠一點的空 bucket，若 bucket key 為 i，則一次跳 i 平方格查找
* rehash: 共有 m 個 hash function，再 hash 一次
* chaining
* 使用 linked list 串接
* 搜索長度：所有可能走訪的 linked list/總資料筆數

### Dynamic Hashing

* 用資料分布的狀態來決定 hash
* 將 key 轉換成二進位表示法
* 轉換成 binary search tree
* sstime(travers tree's time，與樹的高度有關)
* 樹的歪斜問題
* extendible hash(?)
* 將 tree 建一個目錄(避免 travers 的時間)
* directoryless hash(?)
* 沒有 directory
* overflow -> linked list?


## search structure

### AVL Tree

* binary tree 受 input 的影響，可能不 balance
* high balance - 左右樹高度差(balance factory)只能為 1, 0, -1
* 在 insert 的過程中只要有 node 違反 BF 值則必須做調整
* 依據 insert 位置，可分為 LL, LR, RR, RL

#### 調整(只能意會)

* LL
* RR
* LR(31:00)
* RL
* 將 insert 後產生衝突的 C 往上拉
* 其餘4顆子樹照 binary search tree 順序排放

#### Complexity


* 建 AVL tree 的 cost?

### Optimal Binary Search Tree

* 在最壞的狀況下有幾次的 comparison(與 tree 的高度有關)
* 當每個 node 都有 priority 時，與搜索的頻率有關(與 path 長度有關)
* internal path - 搜索到 node 的路徑
* external path - fail node, node 並不存在 binary search tree 中
* cost: internal path * frequency + external path * freqiency
* 資料為 static set
* if the data is dynamic set?

#### Determine(?)

* Tij - optimal binary search tree, 包含 a(i+1)-a(j) 個 words
* Cij - Tij 的 cost
* Cij = cost(L) + cost (R) + weight(L) + weight(R)
* Rij - Tij 的 root
* Wij - weight, 所有 priority 的加總(static)

##### 若 tree 的 subtree 為 optimal，則 tree 本身有高機率為 optimal

* 假設 a(k) 為 Tij 的 root(Rij) 則左子樹包含 a(i+1)-a(k-1)，右子樹包含 a(k+1)-a(j)
* Cij = Pk + cost(L) + cost(R) + weight(L) + weight(R)，cost(L) 與 cost (R) 再繼續 recursive

* 橫軸代表編號，縱軸代表 word 個數

### M-Way Search

* 最多有 M 個 subtree(M 個 pointer)
* if x=K -> search complete
if x=/=K -> 尋找 x 的坐落區間

### B-Tree

* 是一個 m-way search tree
* 若 m = n，則叫做 2-3-...-(n-1) tree
* root 最少要 2 個 pointer
* 除了 root 外，每個 node 最少要有 m/2 個 children
* 所有的 failure node 都在同一個 level
* 可以解決 binary tree 當 data 過多時樹高過高的問題
* 缺點：在每個 level 比較時耗時較長，故在比較時會使用 binary search

#### insert

* 尋找 word 是否已存在，若不存在則判斷適當插入位置
* 當 leaf node還有空間 -> 直接插入
overflow -> create node(split)
新 node 包含衝突的資料內的最大值
middle 值拉到 parent


#### delete

* 尋找數字是否存在
* 刪除後符合 B-tree 特性 -> 直接刪除
* 刪除後不符合：
隔壁有 node 可以提 -> rotate (隔壁 node 提到 parent，parent 送一個 node 給原本的 pointer)
隔壁沒有 node 可以提，parent 也沒 node 可以送 -> combine


### B+ tree

* 可一次找一堆值
* 將 leaf node 用 linked list 串接
* balance
* 可把想搜索的範圍鎖定在某 subtree 內
* search 到 leaf node 後透過 linked list 做 range query


### R tree(不在課程範圍內)

* 可處理多維空間(ex:經緯度)