今天学完了Coursera上Princeton的Algorithm的课程，第一周的课程主要包括一个入门问题的讲解-UnionFind-和算法复杂度介绍。

Union-Find

这个问题是这样的：对于一个序列或者阵列（甚至更高维度的数据）而言，怎么找到相连的两个数据或者为数据增加一条关系。

Union：直观地，我们可以想到直接找到两个相关的数据，将它们所在的集合进行融合。

Find：直观地，我们定位到需要的两个数据，然后查看它们是不是在一个集合中。

因此，我们明确了这个问题，我们需要考虑需要如何抽象数据结构（Data Structure）和算法（Algorithm）。

数据结构和算法的考虑：

我们需要的主要数据结构是一个记录每个数据和其所在类或者说组。那么我们可以对不同的组建立一个索引，这样可以直接查到每个数据所在的组。这样的算法我们可以看出，索引很迅速，因为只需要查号就可以了（即Find比较容易），而对两个组进行合并的时候，这个索引的作用就没那么大了（即Union比较难）。

因此，我们可以很快地从反面入手。我们可以加快Union的速度，那么另一个思路就是建立一个树的结构，那么进行结构变化的时候一般都比较快。而这样Find会减慢，因为我们不能直接索引到相应的数据，而需要在树的结构中进行查找。

从这个问题和问题解决我们可以看到，解决一个问题需要以下一些步骤：

1. 问题的分析：明确我们需要解决的问题是什么

2. 根据需求，构建数据结构并思考建立在这个数据结构上的算法

3. 分析之前的数据结构和算法，分析其效率，进行改进。

Algorithm Analysis

1. 时间：统计方法（Running Time），数学模型（与机器无关的）

2. 空间：注意计算机的规格，Pending，head等问题。

课程中还出现了一些小问题，比如3-Sum（在一个序列中是否存在3个数的和为0）。也具体思考这里的一些算法，我得到的启示是：

1. 如果问题的一部分可以转换为Search的话，结合Sort可以加速算法。

Programming Assignment

Percolation

问题的描述应该很清楚，在很多地方都有，而其应用也非常广泛，比如水利，网络等等。在解决这个问题（造成Percolation和统计Percolation条件）可以使用Union-Find的算法。

因为近两三个月的编程量都比较小，所以现在开始重新着重练习编程能力。

首先我完全使用VIM进行编码，放弃使用IDE（除非我需要进行特大工程开发和User Interface的开发时候使用IDE）。

这样做的目的是了解各语言（比如现在我重点练习Java）的库和编码错误和错误率的控制。