高级算法分析与设计期末试题回想

以下是 2023 年冯剑林老师（学硕和博士合班）的高级算法课期末试题回想。

我下面只简写了题干的关键部分，实际试卷上的字比下面的多得多。他很贴心地对几乎每个概念都作了解释（就怕你上课没听），比如第 4 题就 LCS 问题详细描述了一遍，还给出了例子。

1. (10’)

   1. 从大 O 记法的定义出发，证明$T(n)=2n^2+3n+4=O(n^2)$。
   2. 使用替换法求解$T(n)=1+2T(n-1),\ T(1)=0$，写出详细过程。

2. (20’) 考察 LSH、MinHash

   给定以下三个文档的词项表：

   D1	D2	D3
   1	0	1
   0	1	0
   1	0	1
   1	1	0
   0	0	0
   0	0	1
   1	0	0

   1. 计算 D1 和 D2、D2 和 D3 之间的 Jaccard 距离和相似度。
   2. 给定排列 P1=2765413，P2=3574621，求三个文档的 MinHash 结果。

3. (10’)

   1. 解释一下 A-Prioir 算法中的“单调性”是什么意思。
   2. 已知频繁的 2-项集$\left{ {b,m}, {b,c}, {c,m}, {c,j} \right}$，进行修剪（prune）以得到 3-项集的候选，对于每个项集，给出修剪掉的原因。

4. (20’)

   1. 给出最长公共子序列问题（LCS）的递归关系式。
   2. 给出最大独立集问题（MIS）的递归关系式。

5. (10’) 滑雪板租赁问题

   设滑雪次数（$n$）、租用费（$r$）、购买费（$b$），$b$是$r$的倍数。

   给定在线算法：当使用次数小于$\frac{b}{r} - 1$时租用，之后购买一个滑雪板。

   在以下两种情况下分析在线算法和离线算法的竞争比：

   1. $n \lt \frac{b}{r}$
   2. $n \ge \frac{b}{r}$

6. (20’) 给定一具体的带权图（太麻烦了不画了）：

   1. 试卷上给出了 Prim 算法的伪代码，请你根据算法把最小生成树求出来，画出结果。
   2. 试卷上给出了 Kruskal 算法的伪代码，请你根据算把最小生成树求出来，把边以$(u,v)$的形式按算法过程中的添加顺序写出来。

7. (10’)

   1. 解释 P 和 NP，并各举一个例子，分别说明这两个例子为什么是 P/NP。
   2. 证明每个大小为$k$的独立集（图顶点的子集，两两不相连）都可以归约到大小同样为$k$的团（图顶点的子集，两两相连）。