3-1 Hash It Out

使用哈希函数$h(k)=(11k+4)\mathrm{mod}9$，插入整数keys A=[67, 13, 49, 24, 40, 33, 58]到尺寸为9的哈希表。冲突应该通过链来解决，冲突被存储在链的尾部。画一个所有key被插入完后的哈希表图。

h(A)=[3,3,3,7,3,7,3]

0:

1:

2:

3:67->13->49->40->58

4:

5:

6:

7:24->33

8:

3-2 哈希序列（Hash Sequence）

哈希表不止对实现集合操作有用；它们也可用于实现序列（集合、序列接口定义在lecture 02）！给定一个哈希表，描述如何当作黑盒使用它（仅使用它的集合操作），来实现序列接口：

• build(A)，以期望$\mathcal{O}(n)$时间运行

• get_at和set_at，以期望$\mathcal{O}(1)$时间运行

• insert_at和delete_at，以期望$\mathcal{O}(n)$时间运行

• 四个动态first/last操作每个以分摊的、期望的$\mathcal{O}(1)$时间运行

使用一个哈希表H实现序列操作，把序列项目x存储在对象b（有b.key、b.val=x），我们将存储这些拥有键的对象到哈希比表中。我们也保存哈希表中最小的key s，为了维持不变式，n个存储项目有keys $(s,...,s+n-1)$，序列中的第i个项目存储在key为 s+i 的对象中。

为了实现build(A)，对于$A=(x_0,...,x_{n-1})$每个项目$x_i$，构成它的有键对象b，$b.key=i$进行初始化，最坏情形$\mathcal{O}(1)$时间；以期望的$\mathcal{O}(1)$时间使用Set的insert(b)写入到哈希表，总共时间为期望的$\mathcal{O}(n)$。初始化s=0确保不变式满足。

为了实现get_at(i)，用Set find(s+i)，以$\mathcal{O}(1)$时间返回key=s+i的存储对象的值，由不变式可知是正确的。相似地，为了实现set_at(i, ,k)，使用find(s+i)找到key=s+i的对象，改变它的值为x，也花费期望$\mathcal{O}(1)$时间。

为了实现insert_at(i, x)，对从s+n-1到s+i的j，使用delete(j)以期望$\mathcal{O}(1)$时间移除key=j的对象b，改变它的key为j+1花费最坏情形$\mathcal{O}(1)$时间，用insert(b)以期望$\mathcal{O}(1)$时间插入对象。用值x和key=s+i构建一个有键对象b’，并用insert(b’)以期望$\mathcal{O}(1)$时间插入，总计期望$\mathcal{O}(n)$时间。这个操作恢复每个受影响项目的不变式。

相似地，为了实现delete_at(i)，用delete(s+i)以期望$\mathcal{O}(1)$时间移除存储在s+i处的对象b’。j从s+i+1到s+n-1，使用delete(j)以$\mathcal{O}(1)$时间移除key=j的对象b，以最坏情形$\mathcal{O}(1)$时间改变它的key=j-1，用insert(b)以$\mathcal{O}(1)$时间插入对象。返回对象b’的值，总共花费期望$\mathcal{O}(n)$时间。这个操作通过不变式返回正确的值，恢复每个受影响项目的不变式。

为了实现insert_last(x)或delete_last()，简单地以期望$\mathcal{O}(1)$时间insert_at(s+n)或delete_at(s+n-1)，因为没有对象需要被移动。

为了实现insert_first(x)，构建一个有键的对象b，值为x、key=s-1，用insert(b)以期望$\mathcal{O}(1)$时间插入它。设置存储值s=s-1，恢复不变式。delete_first()是相似得，使用delete(s)以$\mathcal{O}(1)$时间移除key=s的对象，返回对象的值。然后设置s的存储值为s+1，恢复不变性。

3-3 生物排序（Critter sort）

Ashley Getem收集、训练口袋兽，与其他口袋兽战斗。她总共收集了n个口袋兽，她对每个口袋兽$C_i$保存一些统计数据。基于下面每种key，描述高效算法来对Ashley的口袋兽排序。

(a) 物种ID：一个整数$x_i$，-n到n之间（负ID是脾气暴躁的）

这些整数时线性的、有界的，但不是正数。因此用最坏情形$\mathcal{O}(n)$时间对每个口袋兽的ID加n，那么对于所有i，$x_i\le 2n=u$。对它们使用计数排序，最坏情形用时$\mathcal{O}(n+2n)=\mathcal{O}(n)$，然后对每个ID减n，最坏情形用时$\mathcal{O}(n)$

(b) 名字：一个唯一的字符串$s_i$，包含最多$10\lceil \lg n\rceil$个英文字母

让我们假设：每个字符串存储在连续的内存块，数字（常数k为边界，比如26用于英文字母编码、256用于字节编码）代表每个字符进行编码，如果在字母表中$c_i$在$c_j$前面，那么字符$c_i$的数字表示小于另外字符$c_j$。每个字符串可被视作一个整数：0到$u=k^{10\lceil \lg n\rceil }=\mathcal{O}(n^{10\lceil \lg k\rceil })=n^{\mathcal{O}(1)}$，以常数个机器字存储，因此可用基数排序进行排序，耗时$\mathcal{O}(n+n{\log }_n{n}^{\mathcal{O}(1)})=\mathcal{O}(n)$。

可选择地，如果每个字符串$s_i$中每个字符用它自己的机器字存储，那么输入尺寸$\Theta (n\log n)$。对每个字符串，计算它的$n^{\mathcal{O}(1)}$数字表达，需要$\mathcal{O}(\log n)$个数学运算（每个数学运算以$\mathcal{O}(1)$时间运行，因为每个中间表达最多10个机器字）。然后像上面那样使用基数排序。计算字符串的数字表达式花费$\mathcal{O}(n\log n)$时间，与输入尺寸是线性关系。

© 战斗次数：一个小于$n^2$的正数$f_i$

这些整数有多项式（polynomially）边界：$u=n^2$，因此对它们使用基数排序进行排序，最坏情形$\mathcal{O}(n+n{\log }_n{n}^2)=\mathcal{O}(n)$时间

(d) 胜率，比率$w_i/f_i$，$w_i\le f_i$是战斗胜利的次数

非整数除法可能产生一个数，需要无限个数字来表示，因此我们不能直接计算这些数字。没有考虑精度地尝试计算、比较这些数字的解法，不能得分。有两个解法。

第一个解法使用最优的比较排序算法（像归并排序）来对胜率排序，花费$\mathcal{O}(n\log n)$时间。通过交叉乘法，两个胜率$w_1/f_1和w_2/f_2$可比，因为当且仅当$w_1{f}_2<w_2{f}_1$时，$w_1/f_1<w_2/f_2$。这种解法得4/5分。

第二个解法是更棘手的。想法是有效地放缩比例，使得它们不相等时，整数部分也不相等。首先，对每个胜利次数，计算$w_i^{\prime }=w_i\cdot n^4$耗时$\mathcal{O}(1)$。通过整数除法计算$p_i=\lfloor w_i^{\prime }/f_i\rfloor$耗时$\mathcal{O}(1)$,$w_i^{\prime }=p_i\cdot f_i+q_i,q_i=w_i^{\prime }\mathrm{mod}{f}_i$。那么，因为每个$p_i$是一个正整数，边界为$\mathcal{O}(n^6)$，我们可以用最坏情形$\mathcal{O}(n+n{\log }_n{n}^6)=\mathcal{O}(n)$时间利用$p_i$通过基数排序进行排序。

现在我们必须证明：利用$p_i$排序等价于利用$w_i/f_i$。当且仅当$p_i-p_j>0$为真，足以证明：$w_i/f_i-w_j/f_j>0$为真。

$d_w=w_i/f_i-w_j/f_j=(w_i\ast f_j-w_j{f}_i)/f_i{f}_j>1/n^4，所以放缩比为n^4$

$w/f=p+k\ast (1/n^4)+q，那么：w\ast n^4/f=n^4\ast p+k+q\ast n^4，q\ast n^4取值为[0,1)$

$w_i^{\prime }/f_i-w_j^{\prime }/f_j=整数部分+(q_i-q_j)n^4，因为(q_i-q_j)\ast n^4的绝对值小于1，所以整数部分决定了整体。$

3-4 高校建设（College Construction）

Mit已经雇佣Gank Frehry建造Stata中心的新侧厅，来容纳新的计算学院。Mit想让新建筑尽可能的高，但剑桥区法律，限制所有新建筑的高度不得超过正整数h。作为一名创新建筑师，frehry已经决定建造新侧厅，将两个巨大的堆叠在一起，里面的房间将会被雕刻。然而，frehry的铝立方体供应商只能制作立方体（有限正整数边 S = { s 0 , . . . , s n − 1 } S=\{s_0,...,s_{n-1}\} S={s0​,...,sn−1​}），帮助frehry购买铝立方体用于新建筑。

(a) 假设输入S占$\Theta (n)$个机器字，描述一个期望时间为$\mathcal{O}(n)$的算法，来判断S中是否存在一对边，长度之和为h。

解：对每个$s_i$，是否$(h-s_i)\in S$。我们可以执行这个检查，通过比较$h-s_i$和 s j ∈ S − { s i } s_j\in S - \{s_i\} sj​∈S−{si​}，每个$s_i$花费$\mathcal{O}(n)$时间，致使$\mathcal{O}(n^2)$运行时间。我们可以通过：先把S中的元素存到哈希表H，以便查找$h-s_i$可以很快完成。对每个$s_i\in S$，插入$s_i$到H以期望时间$\mathcal{O}(1)$。现在S中所有值出现在H中，因此对每个$s_i$，以期望$\mathcal{O}(1)$时间检测$h-s_i$是否存在于H中（如果供应商每种尺寸仅能建造一个，那么也要检查$h-s_i\ne s_i$）。构建哈希表，然后检查匹配，每个花费期望$\mathcal{O}(n)$时间，因此这个算法执行时间是$\mathcal{O}(n)$。这个粗鲁的暴力算法是正确的，因为每个$s_i$满足$s_i+k_i=h$，有一个整数$k_i$，我们检查所有可能$(s_i,k_i)$

(b) frehry是不幸地，S中没有一对边的长度之和正好等于h。假设$h=600n^6$，描述一个最坏情形$\mathcal{O}(n)$时间算法，来返回S中一对边，它们的长度之和最接近h（不超出）。

解：我们不知道是否所有$s_i\in S$，是n的多项式范围内的。但我们知道h是多少。如果有些$s_i\ge h$，它不会是正数边对（和比h小）的一部分。因此首先执行一个S的线性扫描，移除所有$s_i\ge h$构建集合$S^{\prime }$。现在$S^{\prime }$中每个整数的上边界为$\mathcal{O}(n^6)$，因此我们可以耗费最坏情形$\mathcal{O}(n+n{\log }_n{n}^6)$时间使用基数排序对齐排序，然后把输出存储到数组A。

现在我们可以用双指算法扫描有序list（就像归并排序中的归并步骤，找出最大和的“对”，最大为h，如果这个对存在）。特别地，初始化索引i=0、j=$|S^{\prime }|-1$，重复下面过程，记录至今为止找到的最大和t（初始化为0）。

如果$A[i]+A[j]\le h$，$t<A[i]+A[j]$，找到更大的一对，因此设置$t=A[i]+A[j]$，$（A[k]+A[j]<t，所有k\le i,因此i加1）$。

否则如果$A[i]+A[j]>h$，那么$A[i]+A[l]>h，对于l\ge j$，所以j减1。

如果$j<i（或者j=i，我们想区分s_i,s_j）$，那么返回false。这个循环保证每次循环开始时的不变性：我们已经确认：$A[k]+A[l]\ge t，对于k\le i\le j\le l，A[k]+A[l]\le h$，因此算法是正确的。因为循环的每次迭代花费$\mathcal{O})(1)$，循环j-i次，且j-i=|S’|-1，始于正数，止于j-i<0，这个过程最坏情形花费$\mathcal{O}(n)$时间。

3-5 Po-k-er Hands

Meff Ja是玩牌高手，喜欢玩卡牌游戏。他发现了一副不寻常的纸牌，每张牌标记了26个英文字母中的小写字母。我们将一副牌视作一个字母序列，首个字母对应第一张牌。Meff想和你玩Poker游戏。游戏开始，他用下面方式给你发k张牌：

1、牌以已知顺序、毛面向下放置

2、Meff公平地随机从某个位置 i ∈ { 0 , . . . , n − 1 } i\in\{0,...,n-1\} i∈{0,...,n−1}切牌，比如将前i张牌按顺序放到牌底部

3、Meff从切过的牌上面给你发k张牌

4、你对k张牌按字母表排序，形成你的Po-k-er hand

让$P(D,i,k)$表示Po-k-er hand（从D的位置i切牌）。切D=’abcdbc‘于位置2，得到’cdbcab’，产生Po-4-er hand $P(D,2,4){=}^{\prime }bcc{d}^{\prime }$。给定一副扑克，多hands可能依赖牌从哪切。给定一副牌，Meff想知道最可能的Po-k-er hand。假设：最可能的Po-k-er hand并非必须唯一，Meff总是更倾向于字典排序最小的hand。

（a）描述一个数据结构，会耗时$\mathcal{O}(n)$由n张卡的D和整数k构建，可以支持$same(i,j)$：常量时间操作，当$P(D,i,k)=P(D,j,k)$时返回true，否则false。

解：构建一个直接访问数组，映射每个索引 i ∈ { 0 , . . . , n − 1 } i\in\{0,...,n-1\} i∈{0,...,n−1}到一个频率表（P(D, i, k)的字母数），特别地，一个直接访问数组A的长度是26，A[j]对应英文字母表第j+1个字母出现的次数。$P(D,0,k)$的频率表可以用$\mathcal{O}(k)$时间计算，简单地循环卡片，并把它们加到频率表中。给定$P(D,i,k)$的频率表，我们可以计算$P(D,i+1,k)$的频率表，耗费常量时间，减去D[i]处的字母，添加D[i+k]处的字母。构建上述哈希表花费$\mathcal{O}(k)+n\mathcal{O}(1)=\mathcal{O}(n)$。为了支持same(i, j)，查询直接访问数组中的索引i和j，耗费常量时间。如果对应频率表是一样的，那么就是匹配的。我们可以检测它们是否匹配，以最坏情形常量时间，因为每个频率有固定长度（比如：26），因此这个操作花费最坏情形$\mathcal{O}(1)$时间。

（b）给定一副n个卡片的牌，描述一个$\mathcal{O}(n)$时间算法来找到最可能的Po-k-er hand，可能性一样时，用字典序来打破。表明你的算法运行时间是最坏情形、分摊、还是期望。

解：构建（a）部分的数据结构耗费最坏情形$\mathcal{O}(n)$时间，访问频率表的直接访问数组。现在，直接计算每个的频率：遍历直接访问数组，把每个频率表加到一个哈希表T，映射值为1，若表h已经存在于T中，T[h]加1。这个过程中，对n个表中每个都执行一次哈希表操作，因此它运行时间为期望$\mathcal{O}(n)$时间。接下来，遍历T找出最大频次的表，保存f为最大频次，耗费最坏情形$\mathcal{O}(n)$时间。然后再次遍历T，构建频次为f的表list，找到频次为f的表追加到动态数组A后面，也耗费最坏情形$\mathcal{O}(n)$时间。字母字典序的首个，是频次表字典序的最后一个（比如，(1,0,…)>(0,1,…)，但’a…'<‘b…’），因此遍历频次表，找出最后一个，耗时最坏情形$\mathcal{O}(n)$时间。最终，基于频次按顺序拼接k个字母，转换频次表t，耗费最坏情形$\mathcal{O}(k)$时间，然后返回它。总共，这个过程以期望$\mathcal{O}(n)$时间运行。

我们可以使用基数排序，而非哈希表来对频次计数，我们可以减少到最坏情形$\mathcal{O}(n)$时间。我们对part (a)中的数据结构使用元组/基数排序。每个频次表包含26个数字（[0-n]），因此我们可以将其视作基底为n+1的26个数。从最低权重到最高权重，对其排序，我们把频率表以升序排列。扫描数组，每步检测当前频率表和前一个频率表是否一样，计算每个频率表的出现次数。扫描发生频次，找出最大频次f，再次扫描数组，找出频次为f的字典序最后一个。