何为贪心？

• 贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就作出选择（下一步的选择总是在当前看来收敛最快和效果最明显的那一个），而且一旦做出了选择，不管将来有什么结果，这个选择策略都不会改变（以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题）。
• 贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。
• 贪心算法对于大部分的优化问题都能产生最优解（如单源最短路径问题，最小生成树等），但不能总获得整体最优解，通常可以获得近似最优解。
• 贪心策略一旦经过证明成立后，它就是一种高效的算法。

基本概念？

• 点连通度（图的连通度）：对应一个图 $G$，对于所有点集 $U \subset V_G$，也就是 $V_G$ 的子集中，使得 $G-U$（在图 $G$ 中删去 $U$ 和与 $U$ 关联的边）要么是一个非连通图，要么就是一个平凡图，其中最小的集合 $U$ 的大小 $|U|$ 就是图 $G$ 的点连通度（有时候也直接称为图的连通度）。

　　在计算机算法求解问题当中，经常用时间复杂度和空间复杂度来表示一个算法的运行效率。空间复杂度表示一个算法在计算过程当中要占用的内存空间大小；时间复杂度则表示这个算法运行得到想要的解所需的计算工作量，并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快，即探讨的是当输入值接近无穷时，算法所需工作量的变化快慢程度。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

二分图匹配问题

• 二分图
  
  • 顶点被分成两个不相交的集合（$U$ 和 $V$）并且同属一个集合内的点两两不相连（$E_{in U} = E_{in V} = \emptyset$），即要么没有圈，要么圈所包含的边数必定是偶数。
  • 二分图 的一个等价定义是：不含有 含奇数条边的环 的图。

并查集

• 并查集：并查集处理的是集合之间的关系，即 union，find。在这种数据类型中，N个不同元素被分成若干个组，每组是一个集合，这种集合叫做分离集合。并查集支持查找一个元素所属的集合和两个元素分别所属的集合的合并。注意：并查集只能进行合并操作，不能进行分割操作。
• 并查集支持以下操作：
  • makeset(x)：创建一个仅包含 x 的独立集合（分离集）；最初每个节点单独构成了一个分离集 ==> 一组分离集
  • find(x)：不断重复地检验节点对，判断其是否属于同一个集合？
  • union(x, y)：每当增加了一条边，将与之相关的两个集合合并。

• Consider the following game. A “dealer” produces a sequence $s_1, …, s_n$ of “cards”, face up, where each card $s_i$ has a value $v_i$. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as bills of different denominations.) Assume n is even.

网络流：最大流问题

• 所谓网络：
  • 一个有向图 $G=(V, E)$
  • G中有两个特殊节点 $s, t \in V$，分别称为 G 中的源点(source) 和汇点(sink)。
  • G中每条边都有容量 $c_e \lt 0$。
• 所谓流是指一种特定的输送方式，其中对每条边赋予一个变量 $f_e$，使其满足如下三个基本性质：

　所谓 回文（palindrome），指的是正读和反读都是一样的。而 字符子串 和 字符子序列 的区别，在前面 算法设计与分析[0011] Dynamic Programming(III)（Longest Common Subsequence） 中也有提到过，字符字串指的是字符串中连续的n个字符，而字符子序列指的是字符串中不一定连续但先后顺序与原字符串一致的n个字符。