Lec01 - 方程组的几何解释
第 1 课 方程组的几何解释
第 1 课主要阐述了何为线性方程组的行图像和列图像，并从列图像出发去理解线性组合，最后基于线性组合提出并初步解答了一个重要的问题：对任意 $b$ ，是否都能求解 $Ax=b$
线性代数的基本问题是求解给定包含 n 个未知数的 n 个线性方程。举个例子：
\displaylines{
2 x-y =0 \\
-x+2 y =3
}将其重写为矩阵和向量表示：
\displaylines{
\left[\begin{array}{rr}{2} & {-1} \\ {-1} & {2}\end{array}\right]\left[\begin{array}{l}{x} \\ {y}\end{array}\right]=\left[\begin{array}{l}{0} \\ {3}\end{array}\right]
}
Row picture（行图像）
Column picture （列图像）$\rightarrow$ Linear Combination（线性组合）
从列图像的角度去理解线性组合，也即 $Ax$ 就是对 $A$ 的列向量进行 $x$ ...
Assignment1 - Backwash In Percolation
Assignment1 - backwash in Percolation
作业网站：Assignment1-Percolation，包含本次作业的说明，FAQ，相关的有用资源文件。
backwash 问题在作业网站的 FAQ 中提到了一个叫做 backwash 的问题：
Q: After the system has percolated, my PercolationVisualizer colors in light blue all sites connected to open sites on the bottom (in addition to those connected to open sites on the top). Is this “backwash” acceptable?
A: No, this is likely a bug in Percolation. It is only a minor deduction (because it impacts only the visualizer and not the experiment to es ...
Union-Find
Union Find关于 path compression 的补充说明在 improvements 一节中我们谈到了对 Quick Union 算法的两种改进，一种是带权（Weighted Quick Union），另外一种是路径压缩（Quick Union + path compression），这两种改进的算法对于在 $N$ 个对象上的 $M$ 次 union-find 操作其 worst-case time 皆为 $N+M\log N$。
该节中还提到了 Weighted Quick Union + path compression，这种方法结合了带权和路径压缩（worst-case time 为 $N+M\lg^*N$），但是在编码上需要注意一些问题。
在实现 Quick Union + path compression 时，我们知道采用单程实现（半展平）只需要在 root 中添加一行代码即可：
1234567public int root(int p) { while (p != id[p]) { id[p] = id[id[p]]; ...