# CLRS

## How to prove the algorithm's correctness

[連結](https://hackmd.io/xe4bpXZ_R7SP-owqNZs7Kw#)

## Chapter 2

### Insertion sort

### Loop invariant

### Merge sort
<br>
<br>

## Chapter 3

### Comparing function
<br>
* polylogarithmetically bounded <br>

## Chapter 4

### Methods for solving recurrence function

### The maximum-subarray problem
* Brute force
* Divide & conquer


* Greedy (best) time complexity : O(n)

### Strassen's algorithm

* Brute force, time complexity : Θ($n^{3}$)


* Strassen


### Substitution method

### Recursion-tree method




### Master theorem method


## Chapter 5

### The hiring problem

## Chapter 6

### Heap sort
* Heapify

* Build heap


### Priority queue


## Chapter 7
### Partition

### Quick sort



### Randomized Quick sort



## Chapter 8

### Counting sort




### Radix sort


### Bucket sort


* Proof that bucket sort's time complexity is linear time




## Chapter 9
### Selection problem




* worst case




## Chapter 10
### Sentinels




### Comparsions among list


## Chapter 11
### Analysis of hashing using chaining


* unsuccessful search


* successful search





### Open addressing




### Linear probing


### Quadratic probing


### Double hashing


### Perfect hashing



## Chapter 12
### The number of bst with n node





## Chapter 13
### [Insertion](http://alrightchiu.github.io/SecondRound/red-black-tree-insertxin-zeng-zi-liao-yu-fixupxiu-zheng.html)
* Uncle is red → color change
* Uncle is black (insert node is right child) → left rotation
* Uncle is black (insert node is left child) → right rotation

### [Deletion](http://alrightchiu.github.io/SecondRound/red-black-tree-deleteshan-chu-zi-liao-yu-fixupxiu-zheng.html)

## Chapter 14
### Interval trees


## Chapter 15

### Dynamic programming definition


### Rod cutting


* Brute Force : time complexity O($2^n$)
* DP Equation : time complexity O($n^2$)

1. Top-down with memorization


2. Bottom method


3. Reconstructing a solution (not only value but an optimal solution)


### Matrix-chain multiplication

* Brute force : time complexity O($n^3$)

* Counting the number


* DP Equation : time complexity O($n^2$)





### LCS

* time complexity : O($m * n$)
* space complexity : O($m * n$)




### OBST

* Naive recursive approach time complexity : O($2^n$)
* DP time complexity : O($n^3$)





### Longest simple path in a directed acyclic graph

* time complexity : O(n)
* space complexity : O(n)


### Edit distance

s is the maximum edit distance
* time complexity : O($s×min(m,n)$), where m and n are the lengths of the strings.
* Space complexity is O($s^2$) or O(s)




## Chapter 16

### Greedy definition


### An activity-selection problem




### Greedy strategy elements

1. A candidate set : 可構成解的子集
2. A selection function : 用來選擇最佳解的 function
3. A feasibility function : 用來決定誰可成為 candidate 的 function
4. A objective function : 此問題的部分解
5. A solution function : 用來決定完整解是否已被找到


### Huffman codes




* Correctness about constructing a Huffman tree


## Chapter 17

[講解影片](https://youtu.be/kShuBNlXQ8M)

[台大ppt](https://www.csie.ntu.edu.tw/~hsinmu/courses/_media/ada_11fall/amortized_analysis.pdf)

## Chapter 18

### B-tree definition



### B-tree height



### B-tree search


### B-tree create tree


### B-tree vs B + tree


### B tree vs B + tree time complexity



### B-tree insert / deletion

[教學網站](https://medium.com/hallblazzar-%E9%96%8B%E7%99%BC%E8%80%85%E6%97%A5%E8%AA%8C/%E5%AD%B8%E7%BF%92%E6%89%8B%E8%A8%98-2018%E6%B8%85%E8%8F%AF%E5%A4%A7%E5%AD%B8db-ai-bootcamp-ii-b-tree-indexing-648a096e1598)

## Chapter 19

### time complexity

* Prim's algorithm & Dijkstra's algorithm 因 decrease key O(1) 時間複雜度降低


[教學影片](https://youtu.be/y2v6SwOvB_M)

### [Fibonacci number analysis](https://stackoverflow.com/questions/14333314/why-is-a-fibonacci-heap-called-a-fibonacci-heap)



### Difference between Binomial heap and Fibonacci heap

[Greeksfoegreeks](https://www.geeksforgeeks.org/difference-between-binary-heap-binomial-heap-and-fibonacci-heap/)


## Chapter 20

### Definition

[MIT教學影片](https://youtu.be/hmReJCupbNU)

[Wiki](https://en.wikipedia.org/wiki/Van_Emde_Boas_tree)

* Use bit vector to represent the universe integer set
* And buid tree on the bit vector
* Using binary search to search the value， in each level
* Time complexity : $O(lglgn)$
* Recursion function : $T(n) = T(\sqrt n) + O(1)$

## Chapter 21

### Definition

[Disjoint set](https://cihcih.medium.com/%E5%9C%96%E8%AB%96%E6%BC%94%E7%AE%97%E6%B3%95ch21-ds-for-disjoint-sets-de61210d671a)

[NTU ppt](https://www.csie.ntu.edu.tw/~hsinmu/courses/_media/dsa_17spring/disjoint_set.pdf)

Weight Union
* Union by size
以點數較多者為合併對象，點數少者合併至點數多者，將 pointer 指向多者 set 之 root
* Union by height
以樹高較高者為合併對象，樹高低者合併至樹高高者，將 pointer 指向高者 set 之 root

* Path compression (路徑壓縮)
路徑壓縮是一種在樹上使用 Find 時平展樹結構的方法。由於在到達根的途中訪問的每個元素都是同一集合的一部分，因此所有這些訪問的元素都可以直接重新附加到根。生成的樹要平坦得多，不僅加快了對這些元素的未來操作，而且也加快了對引用它們的元素的操作。

簡而言之，在 Find-Set () 過程中尋訪之元素將其原指向 parent pointer 改指向 root (降低樹高)

Weight Union + Path compression → time complexity O(α(n)*m) = O($lg*n$)

其中，α 為 [Ackermann inverse function](https://en.wikipedia.org/wiki/Ackermann_function#Inverse)，趨近於 constant which $< 5$
m 為 operation 次數 (Make-Set / Find-Set / Union)，n 為 Make-Set 個數

### Analysis


### Amortized analysis


### Potential function



### Why Link operation cost α(n)


## Chapter 22

### Incidence matrix (directed graph)


### BFS


### Diameter

* 對經過每一點之一邊做一次 BFS，time complexity O(|E|) = O(|V| - 1) = O(V)



### DFS


* Edge type



* White path theorem


### Topological sort


### Euler tour


[Solution](https://walkccc.me/CLRS/Chap22/Problems/22-3/)

### Find strongly connected component

Strongly connected : 每點 vertex 至圖中任一點皆有路徑經過

演算法將會用到Transpose of Graph，edge的方向顛倒，就得到$G^{T}$，

例如，原本的 edge(0,1) 改為 edge(1,0)，edge(5,6) 改為 edge(6,5)。

$G$與$G^{T}$的SCC完全相同


[Method](http://alrightchiu.github.io/SecondRound/graph-li-yong-dfsxun-zhao-strongly-connected-componentscc.html)

## Chapter 23

### Kruskal's algorithm


### Prim's algorithm

<img src="https://i.imgur.com/KDWtKPx.png">

### Sollin's algorithm


### Second best MST

找不在集合邊且加入後與原先MST差相距最小

[Algorithm](https://www.geeksforgeeks.org/second-best-minimum-spanning-tree/)

## Chapter 24

### Dijsktra's algorithm





* Prove the correctness



### Bellamn-Ford


* Prove the correctness



### Floyd-Warshall


### Johnson's algorithm




* time complexity : $O(V(VlogV + E)) = O(V^{2}logV + VE)$ with Fibonacci heap
* if use binary heap : $O(V((V+E)logV + E)) = O(VElogV)$
* But all the above are better than Floyd-Warshall with $O(V^{3})$

## Chapter 25

### Ford-Flukerson

* Given a flow network G = (V, E) and a flow f , an ==augmenting path== p is a simple path from s to t in the residual network $G_{f}$
* We call the maximum amount by which we can increase the flow on each edge in an augmenting path p the ==residual capacity== of p


### The Edmonds-Karp algorithm
==We can improve the bound on FORD-FULKERSON by finding the augmenting path p in line 3 with a breadth-first search.== That is, we choose the augmenting path as a shortest path from s to t in the residual network, where each edge has unit distance (weight). We call the Ford-Fulkerson method so implemented the Edmonds-Karp algorithm. We now prove that the Edmonds-Karp algorithm runs in ==$O(VE^{2})$== time.