# Data structure
### 1. Fib

int fib(int n){
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else
    return fib(n-1)+fib(n-2);
}

### 2. GCD

int GCD(int m, int n)
{
  if (m % n == 0)
    return n;
  else
    return GCD(n , m%n);
}

### 3. Tower of Hanoi

#num, from , middle, to 
void Tower_of_Hanoi(int n, char A, char B, char C) 
{
  if (n != 1)
  {
  Tower_of_Hanoi(n-1, A, C, B);
  Tower_of_Hanoi(1, A, B, C);
  Tower_of_Hanoi(n-1, B, A, C);
  }
}
# time complexity = O(2^n)

### 4. Print all permutations of n data.

void permutaion(arr n, int s, int t)
{
int j, temp;
if (s == t){
for(j=1; j<=n; j++)
    print(n[j]);
}
else{
  for(j=i; j<=n; j++){
    SWAP(n[i],n[j]);
    permutation(n, i+1, t);
    SWAP(n[i],n[j]);
}
}
}
# time complexity = O(t!*t)

### 5. Order recursive algo

void Postorder(treenode *t){
  if (*t != NULL){
    Postorder(t->Lchild);
    Postorder(t->Rchild);
    print(t->data);
  }
}

### 6. Build Heap(bottom up)

char adjust(int* tree[], int s, int t){
  int x = tree[s];
  j = 2*s; 
  while(j <= t){
    if (j<s){
      if(tree[j]<tree[j+1])
        j = j+1;
      if (x >= tree[j])
        break;
      else
        tree[j/2] = j;
        j = j*2;        
    }
  }
  tree[j/2] = x;
}

char heap(int* tree[], int n){
  for(i = n/2; i>0 ; i--)
    adjust(tree, i, n);
}
#time complexity = O(n)

### 7. Thread B.T to find x's successor

### 8. Binary search

str Binary_search(char a[], int n, int s, int t){
  int index = (s+t)/2; 
  int pk = a[index];
  if (pk == n)
    return 'find';
  else if (pk < n)
    Binary_search(a, n, index+1, t);
  else if (pk > n)
    Binary_search(a, n, s, index-1);
  else if (s==i && pk != n)
    return 'not found';
}
# time complexity = O(logn)

### 9. Insertion sort

void insertion_sort(char &a[],int len){
  for(i = 1; i< len; i++){
    int j=0;
    int pk = a[i];
    while(j<=i){
      if(a[i] > a[j])
        j++;
      else
        SWAP(a[i],a[j]);
        j++;
    }
  }
}
#time complexity = O(n^2)

### 10. Selection sort

void selection_sort(char &a[], int len){
  for(int i = 1; i < len; i++){
    int j = a[i]
    for (int k = 0; k < i; k++){
      if(a[k] < a[i])
    }
  }

}

### 11. Bubble sort

void bubble_sort(char& a[],int len){
    for(int i = 0; i<len; i++){
        int j = 0;
        while(j < len){
            if(a[j] > a[j+1]){
                SWAP(a[j],a[j+1]);
            }
            j++;
        }
    }
}

### 12. Quick sort

### 13. Merge sort
### 14. Heap sort
### 15. Counting sort
### 16. DFS traversal

#assume use adjacency matrix
bool adj[9][9];
bool visit[9];

void DFS(int i){
  for(int j = 0; j<9; j++){
    if (adj[i][j] && !visit[j]){
      visit[j] = true;
      DFS(j);
    }
  }
}

void traversal(int n){
  for (int i = 0; i<9; i++)
    visit[i] = false;    #init
  DFS(n);
  for (int i = 0; i<9; i++){
    if(visit[i] = false)
      DFS(i);
   }
}

### 17. BFS traversal

#assume use adjacency matrix
bool adj[9][9];
bool visit[9];
void BFS(){
  queue<int> q;
  for (int i=0; i<9; i++)
    visit[i] = false;
  
  for (int k=0; k<9; k++){
    if(visit[k]!= true){
      q.push(k);
      visit[k] = true;
      
      while(!q.empty()){
        int i = q.front;
        q.pop();
        for (int j=0; j<9; j++){
          if(adj[i][j] && !visit[j]){
            q.push(j);
            visit[j] = true;
          }
        }
      }
    }
  }
}

### 18. DFS use stack

#assume use adjacency matrix
bool adj[9][9];
bool visit[9];
void DFS_stack(int s){
  stack<int> stack;
  for (int i=0; i<9; i++)
    visit[i] = false;
  stack.push(s);
  while(!stack.empty()){
    s = stack.top();
    stack.pop();
    if(!visit[s]){
      visit[s] = true;
    }
    
    for (int j=0; i<9; j++){
      if(adj[i][j] && !visit[j]){
        q.push(j);
        visit[j] = true;
     }
  }
}

### 19. Undirected graph connected

#assume use adjacency matrix
bool adj[9][9];
bool visit[9];
void find_connected_component(graph G, int n){  
#n is number of vertex
  for(int i = 0; i<n; i++)
    visit[i] = false;
  for(i=0; i<n; i++){
    if (visit[i]) = 0{
      DFS(i);
    }
  }
}

### 20. Detected cycle in undirected graph

bool adj[9][9];
#if back edge exist, cycle exist
bool isCyclic(){
  bool* visit = new bool[V];
  for(int i = 0; i<V; i++)
    visit[i] = false;
  for(int u = 0; u<V; u++){
    if(!visit[u]){
      if(isCyclicUtil(u, visit, -1))
        return true;
    }
  }
  return false;
}

bool isCyclicUtil(int v, bool visit[], int parent){
  visit[v] = true;
  for(int i=0; i<9; ++i){
    if(adj[v][i] && !visit[*i]){
      if(isCyclicUtil(*i, visit, v))
        return true;
    }
    else if(*i != parent)
      return true;
  }
  return false;
}

### 21. Strongly Connected Component
若要尋找是否為強連接，先使用DSF(G)找出所有子集，並將G所有edge更改方向，更改方向完再做一次DSF(G)，看子集是否與交換方向前的子集相同。
### 22. Kruscal's algo

int Kruscal(graph G, int w[]){
  int T = 0;
  for each vertex v of G
    make-set(v);  #build disjoint set
  sort the edge with weight;   #Heapsort
  for each edge(u,v) order by weight{
    if Find-set(u) != Find-set(v){
      add(u,v) to T;
      Union(u,v);
    }
  }
  return T;
}

### 23. Prim's algo

void Prim(Graph G, int W[], int n){
    for(each u){
        u.key= ∞;
        u.dis= Nil;
    }
    r.key = 0
    Q=G.V  #create priority queue
    while(Q!=empty){
        u = Extract-min(Q);  #delete min
        for each v belong to G.adj[u]{
            v.π = u;
            v.key = w(u,v);
        }
    }
}

### 24. Sollin's algo
一開始各點設成獨立的tree, 就各個tree挑出小成本之tree edge, 剃除重複挑出的tree edge, 保留一份即可, repeat until 只剩一顆tree。
### 25. DAG

void DAGSP(Graph G, int W[], int s){ #W is set of edge weight
#s is start vertex
    Topological sort on G;
    Initial(G,s);
    for each vertex u in topological sort order{
        for each vertex v belong to G.adj[u]
            Relax(u,v,w)
    }
}
Intial(G,s){
    for each vertex v belong to G.V{
        v.d = ∞;
        v.π = Nil;
    }
    S.d = 0;
}
Relax(u,v,w){
    if v.d > u.d + W(u,v){
        v.d = u.d + W(u,v);
        v.π = u;
    } 
}

### 26. Dijkstra's algo

Dijkstra(G,W,s){
    Initial(G,s);
    Selected = 0;
    Q = G.V; #build priority queue
    while(Q!= empty){
        u = Extract-Min(Q);
        add vertex onto the selected set;
        for each vertex v belongs to G.adj[u]{
            relax(u,v,W);   #heap:O(logV), Fib heap:O(1)
        }      
    }
}
Intial(G,s){
    for each vertex v belong to G.V{
        v.d = ∞;
        v.π = Nil;
    }
    S.d = 0;
}
Relax(u,v,w){
    if v.d > u.d + W(u,v){
        v.d = u.d + W(u,v);
        v.π = u;
    } 
}
#time complexity = heap: O(ElogV) FibHeap: O(VlogV+E)

### 27. Bellman-Ford's algo

void Bellman_Ford(int cost[][], int dist[], int s, int n){
#cost = matrix, dist = [1...n], n = num of vertex, s = start vertex
    for(i=1; i<=n; i++){
        dist[i] = cost[s,i];
    }
    dist[s] = 0;
    for(int k=2; k<= n-1; k++){
        for each vertex v do{
            for each u that has edge<u,v> do{
                if(dist[v]> dist[u]+cost[u,v])
                    dist[v] = dist[u]+ cost[u,v];
            }
        }
    }
}
#time = O(n^3)

### 28. Floyd-warshell's algo

FloydWarshell(int cost[][], int n){
    int i,j,k;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            a[i,j] = cost[i,j];
    }
    for(k=0; k<n; k++){
        for(i=0; i<n; i++){
            for(j=0; j<n; j++){
                if(a[i,k]+a[k,j] < a[i,j])
                    a[i,j] = a[i,k] + a[k,j];
            }
        }
    }
}
#time complexity = O(n^3)