参考书籍：《大数据：互联网大规模数据挖掘与分布式处理》（第二版）

原版英文书籍：Mining of Massive Datasets

注：答案为本人自己做的，并非标准答案，仅供参考。
如有错误，请私信我，我将及时修改。

《大数据：互联网大规模数据挖掘与分布式处理》（第二版）第八章习题答案

注：本书包含大量习题，较难的习题或习题中较难的部分都会用！标记，最难的习题用！！标记。

!习题8.2.1

在线算法：“立即购买滑雪板”。

设天数为x，当天数小于等于10时，竞争率为x/10；当天数大于10时，竞争率为1。

习题8.3.1

!习题8.3.2

G₄有4个完美匹配。

G₅有2个完美匹配。

!习题8.3.3

对于图8-1来说，只有一个完美匹配，有432*1=24种顺序。

简单检测方法：

1. 若4不和a匹配，则一定不是完美匹配；
2. 若2不和b匹配，则一定不是完美匹配；
3. 若满足4和a匹配，2和b匹配，还需要1-c和3-d，该匹配才是完美匹配。

习题8.4.1

!(a)

最差情况：

x-B
x-C
y-B
y-C

此时分配到了4个。

其他情况查询分配数大于等于4。

!!(b)

查询序列：yyzz

最优离线算法：2个y分配给B，2个z分配给C，收益为4。

贪心算法：2个y分配给C，收益为2，是最优离线算法的一半。

!!习题8.4.2

不会。

!习题8.4.3

假定有两个广告商A₁和A₂以及一个查询q，q的出价及预算为：

广告商	出价	预算
A1	a（->0）	c
A2	b（>>a）	d

其中，c>d在查询过程中一直成立。

设查询q的次数为x。此时，最优的离线算法会把所有的查询分配给A₂，而Balance算法会把所有的查询分配给A₁，竞争率c=(xa)/(xb)=a/b≈0。