摘要：算法鏈接學習工具，，環境搭建在小伙伴的推薦下，這個學期開始上普林斯頓的算法課。一系列的整數對代表與相互連接，比如等，每一個整數代表了一個。我覺得這個可能也是并查集相關應用。這學期繼續學習深入理解了就能明白了。

《算法》鏈接：1.5 Case Study: Union-Find
學習工具：mac，java8，eclipse,coursera

環境搭建
在小伙伴的推薦下，這個學期開始上普林斯頓的算法課。
這門課有自己的Java library，剛開始的時候研究載入這個library花了好長時間，最終的解決方案是下載algs4.jar包，然后在eclipse軟件中將其作為外部library，使用的時候import statement要寫成類似這樣的：

import edu.princeton.cs.algs4.StdRandom;

教授一開始就講到了dynamic connectivity，其實這是Union Find算法的一種應用，這學期選修的另外一門network model和這個也有關。

Input: 一系列的整數對（p,q）代表p與q相互連接("is connected to")，比如（4,3）(3,8)等，每一個整數代表了一個object。這里的"is connected to"表示的是沒有方向的對稱連接,且一個p可以與自身p相連。
Goal:當讀取的(p,q)整數對本來不相連時，輸出這個整數對(p,q)且使其相連；如果相連的話，就不輸出，忽略這個整數對

algs4.jar中已經有了UF這個class，可以直接使用。

public static void main(String[] args) {
        int n = StdIn.readInt();
        UF uf = new UF(n);
        while (!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }

數組形式進行存儲array id[i]
如果兩個objects相互鏈接，那么他們數組的值相同
All sites in a component must have the same value in id[].
例如，當union(p,q)時，p所存的值改為q所存的值。id[p] = id[q]

同樣是id[i]數組形式，不同的地方是id[i]中存儲父節點
如果兩個sites的根相同，那么他們在同一個component
根節點i == id[i]
例如，當union(p,q)時

    pID = id[p];
    qID = id[q];
    循環數組中所有值等于pID的，如果id[i]==pID，則id[i] = qID;
    也就是說p所在的樹將作為q的子樹

4.1 weighted
增加sz[]數組來存儲一顆樹里面objects的個數
當要鏈接(p,q)時，需要比較sz[i]和sz[j]的大小（假設i,j分別是他們的root）

4.2 path compression
只需要增添一個語句

id[i] = id[id[i]]

兩種運用

quick union with path compression

weighted quick-union with path compression

教授列舉了相當多的應用，物理學上的，應用到其他算法或者語言的。所給的面試題也很常見。
最近剛接觸seo相關的內容，老師談到IR system需要將用戶提供的單詞和收集的items中相關的words比對，如果對上了(match)，那么這些items就可能是用戶想要的。我覺得這個可能也是并查集相關應用。這學期繼續學習深入理解了就能明白了。

Write a program to estimate the value of the percolation threshold via Monte Carlo simulation.
Percolation. Given a composite systems comprised of randomly distributed insulating and metallic materials: what fraction of the materials need to be metallic so that the composite system is an electrical conductor? Given a porous landscape with water on the surface (or oil below), under what conditions will the water be able to drain through to the bottom (or the oil to gush through to the surface)? Scientists have defined an abstract process known as percolation to model such situations.
The model. We model a percolation system using an n-by-n grid of sites. Each site is either open or blocked.

open

full

Percolation data type：

public class Percolation {
   public Percolation(int n)                // create n-by-n grid, with all sites blocked
   public    void open(int row, int col)    // open site (row, col) if it is not open already
   public boolean isOpen(int row, int col)  // is site (row, col) open?
   public boolean isFull(int row, int col)  // is site (row, col) full?
   public     int numberOfOpenSites()       // number of open sites
   public boolean percolates()              // does the system percolate?

   public static void main(String[] args)   // test client (optional)
}

PercolationStats data type：

public class PercolationStats {
   public PercolationStats(int n, int trials)    // perform trials independent experiments on an n-by-n grid
   public double mean()                          // sample mean of percolation threshold
   public double stddev()                        // sample standard deviation of percolation threshold
   public double confidenceLo()                  // low  endpoint of 95% confidence interval
   public double confidenceHi()                  // high endpoint of 95% confidence interval

   public static void main(String[] args)        // test client (described below)
}

要點

導入WeightedQuickUnionUF,在程序中主要使用connect(p,q),union(p,q)函數

題目默認(1,1)就是左上角的位置，(n,n)就是右下角的位置，所以我先創建了一個siten+1的二維數組, 并全部初始化為0，代表全部block

創建WeightedQuickUnionUF對象，由于UF算法中都是以一維數組存儲，所以數組uf[1]-uf[NN]對應NN矩陣中的位置，并且根據老師的提示，創建了top virtual site uf[0]和bottom site uf[NN+1], 所以整個uf一維數組的長度是NN+2

最關鍵也是最容易出錯的地方就在open一個點以后，檢查上下左右鄰近的點，并對open的鄰近做union的過程，要考慮到邊緣位置的特殊情況，比如中心點在第一行，那么該點上下左右最多只有三個臨近點，而上點可以與top virtual site連通。

Debug

Percolation.java的問題

幾次發現結果不對，問題都出在open函數里面

對eclipse還不熟，測試中In in = new In(args[0]) 語句要求從命令行鍵入文件名，回車運行。eclipse的操作方法是，在 run configurations-->arguments-->program arguments-->鍵入文件名，可以不打引號,也可以打引號。

如果不想寫路徑，只寫filename.txt，文件要放在項目目錄下(我的項目名是algs)，因為eclipse默認的根目錄就是項目目錄

等待解決的bug：一旦連通，再在第N行open的單元格會變成full狀態，因為bottom virtual root 已經聯通，那么與之相連的方塊都認為是與top virtual root 相連的。目前想到的解決方案有

去掉bottom root,但是這樣會遍歷n次

isFull方法加上if判斷

思考優化open 方法

Percolationstat.java 的問題

Percolationstat.java 在編寫時，for循環里面，每一次判斷一個網格是不是連通之前都要新創建一個n-by-n的網格，但是我把創建的語句寫在了for循環外面，導致同一個網格會被實驗T次

計算時除號/左右兩邊numberOfOpenSites和(nn)都是整數，所以得到的結果也是整數；需要強制轉換成double類型，即numberOfOpenSites/(double)(nn)

每次讀取一組整數對后，open site前先要判斷這個點是否被open了，以免多計算在numberOfOpenSites里面

作業提交遇到的問題

所有的fields 和自己定義的methods都要寫為private

最后提交的作業91分，看了一下report, 扣分主要就扣在bottom root與所有最后一行的sites連通的問題上。以后有時間再來修改code吧