三个简述题

ENGLISH

Q1:Question 1
Social network connectivity. Given a social network containing n members and a log file containing m timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend … of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be logm logn or better and use extra space proportional to n.

A1:We can solve this problem using the weighted quick union algorithm. When initialized, the n members are each in an independent group, and count=n is recorded as the current remaining continuous flux. The weighted union operation is performed each time a log is read, and the remaining continued flux is reduced by 1. When the remaining flux drops to 1, the earliest connection time is the current log time。

Q2：Union-find with specific canonical element. Add a method find() to the
find(i) returns the largest element in the connected component containing i. The operations, union(), connected(), and find() should all take logarithmic time or better.For example, if one of the connected components is {1,2,6,9}{1,2,6,9}, then the find method should return 99 for each of the four elements in the connected components.

A2：We use the weighted quick-union algorithm to solve this problem. When initialized, each data is independent as a group, we define two arrays: arr records the maximum number of each group, arr[i]=i.; sz[i]=1 is the current size of each set of trees. Update arr[Root node of a larger tree] =max(arr[root(p)],arr[root(q)]) when performing the union operation, that is, when connecting a small tree to a large tree. When performing the find (i) operation, return the value of arr[root(i)]

Q3：Successor with delete.Given a set of n integers ={0,1,…,N-1}.S={0,1,…,n−1} and a sequence of requests of the following form:

  • Remove x from S
  • Find the successor of x: the smallest y in S such that y≥x.

design a data type so that all operations (except construction) take logarithmic time or better in the worst case.

A3:We use quick-union with compression. Design two arrays: parent[], to record the data set, initialized with each element pointing to itself; next[] Record the next successsor for i. When remove x from s is executed, the collection to which x belongs is first pointed to next[next[i]] by uinon(x, next[i]). We optimize the algorithm with path compression when merging the two collections. When we find the current successor to x, return the value next[root[x]]. So we’re going to have a logarithmic complexity

通过并查集模拟渗流问题（ddl: 4.14）

这是Coursera留下的并查集大作业

渗流模型简述：在给定的n*n网格中，每一个格点有三个状态（关、开、充满水），当水流自上而下能够流通网格时（水的流通方向为上下左右），该模型处于渗流状态。

问题简述：数学家发现当每个格点打开的概率为p,存在一个阈值p ，当n最足够大时，所有p>p 的模型几乎都处于渗流，而所有p<p 的模型几乎处于阻塞状态。然而数学家无法运用数理方法准确估计p 的值。现在我们在计算机上设计程序模拟该p*。 Alt text

设置头部虚拟节点(topsite)和尾部虚拟节点(tailsite)，当topsite和tailsite连通时，改模型为渗流状态。头部虚拟节点相当于水源，尾部虚拟节点相当于水桶。当水桶里有水了，说明模型处于渗流状态。

使用weighted quick-union算法解决，当然直接用迭代判断渗流也可，但算法时间复杂度高于前者

提交的percplation.zip 包含 percolation.java、percolationStats.java

percolation.java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

import edu.princeton.cs.algs4.WeightedQuickUnionUF;
public class Percolation {
   private boolean[][] grid;
   private WeightedQuickUnionUF uf;
    private  int topsite;
    private  int bottomsite;
    private  int n;

    // 创建n*n的网格（grid），初始化时所有格点为闭塞状态（false）
    public Percolation(int n){
        if(n<0)
            throw new IllegalArgumentException("the n is outside");

        this.n=n;
        uf =new WeightedQuickUnionUF(n*n+2);
        topsite=n*n;
        bottomsite=n*n+1;
        grid=new boolean[n][n];
        this.n=n;

    }

    // 打开指定格点，并且连接四周以开放的格点
    public void open(int row, int col){
        if(row<0||row>n-1||col<0||col>n-1)
            throw new IllegalArgumentException("the row/col is outside");
        int [][] direction={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        if(!grid[row][col]){
            grid[row][col]=true;
            if(row==0){
                uf.union(encode(row,col),topsite);

            }
            if(row==n-1)
            {uf.union(row*n+col,bottomsite);
                grid[row][col]=true;}
            for(int[] d:direction){
                int addrow=row+d[0];
                int addcol=col+d[1];
                if(addrow>=0&&addcol<=n-1&&addcol>=0&&addcol<=n-1&&isOpen(addrow,addcol)){
                    uf.union(encode(row,col),encode(addrow,addcol));
                }
            }

        }

    }

    //判断格点是否为打开状态
    public boolean isOpen(int row, int col){
       if(row<0||row>this.n-1||col<0||col>this.n-1){
            //throw new IllegalArgumentException("the row/col is outside");
            return false;
       }
        return grid[row][col];

    }

    // 过查看格点与头部虚拟节点连判断格点是否为注满水，
    public boolean isFull(int row, int col){
        if(row<1||row>n||col<1||col>n)
            throw new IllegalArgumentException("the row/col is outside");

        return uf.find(encode(row,col))== uf.find(topsite)&&isOpen(row,col);

    }

    // 记录已打开格点的个数
    public int numberOfOpenSites(){
        int count=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(isOpen(i, j)==true)
                    count++;
        }
        }
         return count;
    }

    // 通过查看bottoemsite是否连通topsite判断模型是否渗流（connected()方法已被弃用了）
    public boolean percolates(){

        return uf.find(topsite)==uf.find(bottomsite);

    }
    private int encode(int row ,int col){
        return row*n+col;
    }







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


    }
}

percolationStats.java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdIn;
public class PercolationStats {
   //x数组存储每次实验的渗流概率
    private  double[] x;
   private  int n;
    private  int T;

    // 测试T次n*n的模型
    public PercolationStats(int n, int trials){
        this.n=n;
        T=trials;
        if(this.n<=0||T<=0)
         throw new IllegalArgumentException("the n/trials is outside");
        x=new double[trials];
        int row;
        int col;
        for(int i=0;i<trials;i++){
            Percolation a=new Percolation(n);
            while(!a.percolates()){
               do{
                row=StdRandom.uniformInt(n);
                col=StdRandom.uniformInt(n);}while (a.isOpen(row,col));
                a.open(row,col);

            };
            x[i]=a.numberOfOpenSites()/(double)(n*n);

    }
    }

    // sample mean of percolation threshold
    public double mean(){
            double m;
            m=StdStats.mean(x);
            return m;

    }

    // sample standard deviation of percolation threshold
    public double stddev() {
            double s;
            s=StdStats.stddev(x);
            return s;

    }

    // low endpoint of 95% confidence interval
    public double confidenceLo(){
            double c;
            double s=StdStats.stddev(x);
            c=StdStats.mean(x)-1.96*s/Math.sqrt(T);
            return c;


    }

    // high endpoint of 95% confidence interval
    public double confidenceHi(){
        double c;
        double s=StdStats.stddev(x);
        c=StdStats.mean(x)+1.96*s/Math.sqrt(T);
        return c;


    }

    // test client (see below)
    public static void main(String[] args){
        int n;
        int T;
        n=StdIn.readInt();
        T=StdIn.readInt();
        PercolationStats m=new PercolationStats(n,T);
        StdOut.println("mean                    = "+m.mean());
        StdOut.println("stddev                  = "+m.stddev());
        StdOut.println("95% confidence interval = ["+m.confidenceLo()+","+m.confidenceHi()+"]");
        }


}