CS3230 notes

CS3230 notes

greedy algo analysis

1. To prove sub-optimal structure:

   Assume the overall solution X is optimal

   Assume the sub-structure is not optimal

   using an optimal substructure can result in a better overall solution

   contradiction

   例子：MIS on tree

   最优子结构性质： 如果 S 是图 G 的最大独立集，且 v∈S 是一个通过贪心选择选中的叶子节点，u 是 v 的邻居。那么，S∖{v} 必定是子图 G′=G−{v,u} 的最大独立集。 换句话说：原问题的最优解 = 贪心选择 (v) + 子问题 (G−{v,u}) 的最优解。

   形式化证明 (Cut-and-Paste / 反证法)： 令 G 为原图，v 为贪心选择的叶子，u 为其邻居。令 G′=G−{v,u} 为剩余的子图。 假设 S∗ 是 G 的包含 v 的最大独立集（由 B.2.1 可知必存在）。那么 S′=S∗∖{v} 是 G′ 的一个独立集，且 ∣S∗∣=∣S′∣+1。

   1. 假设 S′ 不是 G′ 的最大独立集。
   2. 这意味着存在 G′ 的另一个独立集 B，使得 ∣B∣>∣S′∣。
   3. 考虑集合 C=B∪{v}。
      • 由于 B 是 G′ 的独立集，其中的节点都不在 {v,u} 中。
      • v 只与 u 相连，而 u 已经被移除且不在 B 中。
      • 因此，v 与 B 中的任何节点都没有连边。C 是原图 G 的一个合法独立集。
   4. 计算 C 的大小： ∣C∣=∣B∣+1>∣S′∣+1=∣S∗∣。
   5. 这推导出存在一个比 S∗ 更大的独立集 C，这与 S∗ 是 G 的最大独立集（最优解）相矛盾。
   6. 结论： 假设不成立，S′ 必须是子图 G′ 的最大独立集。

   例子：fish seller

   

   

2. To prove optimal strategy: (exchange method)

   Assume we have an optimal solution. We exchange one step using our strategy, we test if it will make the overall outcome worse. If not worse, then valid.

   例子：MIS on tree

   贪心策略： 在给定的 Hazard-graph（森林/树）中，总是选择一个叶子节点（leaf node，度为1的节点）v 加入到我们的独立集中，然后从图中删除 v 以及 v 的唯一邻居（父节点）u。重复此过程，直到图中没有节点为止。（对于孤立点/度为0的点，直接选择并删除）。

   形式化证明 (Exchange Argument)： 令 T 为给定的树。假设 v 是 T 中的一个叶子节点，u 是 v 的唯一邻居。我们要证明存在一个最优解（最大独立集）S∗ 包含 v。

   1. 设 S∗ 是 T 的一个最大独立集。
   2. 情况 1： 如果 v∈S∗，则证明完成。
   3. 情况 2： 如果 v∈/S∗。
      • 由于 v 是叶子节点且 v∈/S∗，为了使 S∗ 是最大独立集，它的唯一邻居 u 必须在 S∗ 中（即 u∈S∗）。（注：如果 u 也不在 S∗ 中，我们可以直接把 v 加入 S∗ 从而得到一个更大的独立集，这与 S∗ 的最优性矛盾）。
      • 现在，我们构造一个新的集合 S′=(S∗∖{u})∪{v}。即从 S∗ 中移除 u，加入 v。
      • 由于 v 只有邻居 u，且 u 已经被移除，所以 v 加入后不会与 S∗∖{u} 中的任何其他节点产生冲突（边）。
      • 因此，S′ 也是一个合法的独立集。
      • 且 ∣S′∣=∣S∗∣−1+1=∣S∗∣。这意味着 S′ 的大小与 S∗ 相同，所以 S′ 也是一个最大独立集。
   4. 结论： 无论如何，我们要么已经有一个包含叶子节点 v 的最优解，要么可以通过交换构造出一个包含 v 的最优解。因此，总是选择叶子节点是安全的。

   例子：fish seller

   

time complexity

amortize analysis

1. Aggregation method

   Use when you can easily add up the time cost.

2. Accounting method

   store some balance into the bank when doing cheap operations, and spend the balance when doing expensive operations.
   Prove that the balance never drops below zero. Need to keep track of the balance according to some numerical features of states.

3. Potential method

   Find a potential function $\phi$, where 1) initial $\phi = 0$ 2) $\phi$ is non-negative all the time

   $\hat c_i = c_i + \Delta \phi_i$

   To construct $\phi$, we need to use some non-negative numerical features of the states.

   Now, we don't know your actual cost, so setting $\phi_0 = 0, phi_{other} = 1$ is no help. We need a fixed $\hat c_i$ here. So $c_i + \Delta \phi_i$ is better to be a fixed number.

   As long as $\Delta \phi_i$ is always > 0, and $c_i$ is the actual cost of one operation, we recognize $\hat c_i$ is its amortized cost.

   For different operations of the same question, we had better use the same potential function.

final 错题

1. $100^{logn}!=O(n)$, because $100^{log_2n} = n^{log_2100}$

2. Huffman coding algo

3. Easy questions can always be reduced to hard problems

   构造归约过程

   无论 C 是什么复杂度（只要 C 不是那种“永远是 Yes”或“永远是 No”的无聊问题），只要 C 里至少有一个 Yes 实例（记为 yes）和一个 No 实例（记为 no），我们就可以构造如下归约：

   算法（输入是 A 的实例 x）：

   1. 自己动手算： 因为 A 在 P 里，我们直接运行 A 的算法来判断 x 是 Yes 还是 No。（这一步花多项式时间）。
   2. 映射输出：
      • 如果 x 是 Yes → 输出 C 的那个已知实例 yes。
      • 如果 x 是 No → 输出 C 的那个已知实例 no。
   3. 结束： 我们把输出丢给 C 的黑盒子。

   结果：

   • C 的黑盒子回答 yes (即 Yes)，我们就知道了 A 的答案是 Yes。
   • C 的黑盒子回答 no (即 No)，我们就知道了 A 的答案是 No。

4. Extended Master Theorem:

   

   case 2: k < 0, then T(n) = $\Theta(n^{log_ba})$

5. Las Vegas ≤p Monte Carlo

6. proof of NP-completeness:

   1. Prove it is NP(verifiable within polynomial time)
   2. can be reduced from other NPC
      1. Construct reduction scheme
      2. A yes -> B yes
      3. B yes -> A yes