ads知识

introduction

lz的排版按照myc老师的教学安排方式，可能里面有一些概念的定义与ppt不同，请以课程ppt为主。

hw1 AVL树和红黑树

• 知识1 在AVL树中四种样例的划分是来自于 troublemaker、 troublefinder retated child 与 troublefinder
  （总结：关注trouble finder（距离案发现场最近的trouble finder）的孩子(trouble finder’s child,left or right)的孩子树(left or right)是否包括troublemaker，例如 LR，表示的是 Trouble Maker 在 Trouble Finder 的 L 孩子节点的 R 孩子树中。）

• 知识2 在AVL中四种样例的具体调整方法还是不太清楚（并且由于对称性，我们综合下来就是两种情况，一种情况进行单次旋转，一种情况进行两次旋转）

• 知识3 AVL树的节点数量递推式
  $n(h)=n(h-1)+n(h-2)+1$

• 知识4 若AVL树进行删除操作只会影响到一个节点，但是当我们修复后矛盾可能往上移动，所以可能需要$Olog(n)$次旋转

• 知识5 红黑树的定义

  1. 每一个节点都是黑色或者红色
  2. 根一定为黑色
  3. 叶子（要注意叶子节点一定是空节点，这个概念是很关键的）都为黑色
  4. 红色节点的孩子一定为黑色
  5. 对每一个节点，从该节点到叶子的路径中均有数量相同的黑色节点。
     
     

• 知识6 红黑树的插入以及相关的不平衡调整情况

  1. 先将整个红黑树当作一个普通的二叉搜索树，将目标数据插入到树的末端（也就是置换一个 NIL 节点），并将它染为红色，再调整使之在保证黑高不变的情况下，满足红色节点不能相邻的要求。（因为我们这样操作后，原有的黑高性质不会被破坏，但是可能出现红色节点相邻的情况）
  2. 此时，插入操作后可能存在下述三种情况：
     
     （操作为上方红节点染黑及它的父亲染红加旋转）
     
     （操作为旋转，转化为上面的样例1）
     
     （操作为染黑这两个红兄弟与染红它们的父亲，矛盾上移，则可能会出现4种情况(其中可能存在这三种情况的相互转化，但是核心都是解决问题并将矛盾上移)）
  3. $T=O(h)$

• 知识7 红黑树的删除以及相关的平衡调整情况

删除的操作与分类：

1. 若没有非NIL节点，直接用NIL节点替代
2. 若只有一个非NIL节点，直接用非NIL节点替代
3. 有两个非NIL节点，将值与左子树最大值或右子树最小值交换，颜色不换然后删去目标点
4. 如果删除的是红节点不会影响黑高，若删除的是黑节点，我们将红黑树分为以下四类
   

删除理解：

1. case1（根未知，兄弟和兄弟孩子都是黑）：case1.1 若a为红根，则将a和w颜色交换 case1.2 若a为黑根，但是w仍然变化为红色，再向上递归当a是整颗树的根时我们便可结束操作
2. case2（根未知，兄弟黑，兄弟孩子一个红一个未知）：将w染成a的颜色，再将a和原来红色的儿子染成黑色；再将a左旋
3. case3（根未知，兄弟黑，兄弟孩子一个红一个黑）：交换b（红色儿子）和w的颜色；将w右旋转化为case2的情况。
4. case4（根黑，兄弟红）：交换a和w的颜色，将a左旋，再根据子树a的情况转化为case 1.1/case 2/case 3

删除总结：
旋转的最多情况是case4到case3再到case2即3个，而时间最复杂的情况则是一直递归到整颗树$T=O(logN)$

ex1:

解释：当对avl树进行删除操作后，则只能有一个点发生不平衡，现在对一这个点为根的子树进行分析。因为我们调整整颗avl树，则首先这颗树的高度会减少1。如果整棵树已经平衡，则停止操作。但是如果因为这颗子树的高度减一导致上方节点的左右子树的高度差大于等于2，则需要上移矛盾再进行操作，则这颗子树的高度可能最终保持不变。

ex2:

解释：这道题需要结合红黑树的几个基本性质进行解决，u是红黑树的内部节点，其中u有两个孩子，其中一个孩子v是红黑树的内部节点，另一个孩子是nil节点。由红黑树的第五个定义，因为另外一个节点为内部节点则一定有两个nil，由第五个性质，则v一定为红色，再由第四个性质，u一定为黑色。

hw2 摊还分析与splay树

• 知识1 splay树的具体操作还得记一记喵

  1. splay树的操作相当简单，首先按照bst进行操作，然后每一次对于操作的节点都进行旋转直到转到根节点处。
  2. 注意删除时，是先找到节点，然后不断旋转X至根，接下来删除root节点。并在维护BST性质的情况下递归地合并左右子树（splay（左子树最大），attach右子树to左子树）。

• 知识2 对摊还分析的思考(常用的是势能法)
  接下来，我们需要设计一个势能函数
  Φ(x)，并且根据我们提到过的势能分析法的特性，
  Φ(x) 应该具有这么几个特征：
  开销大的操作应当倾向让势能降，开销小的操作应当倾向让势能升；
  势能高倾向于让某些操作开销大，势能低倾向于让某些操作开销小；
  Φ(final)>Φ(initial)；

• 知识3 均摊O(logn)

• ex1

解释：这是splay树的一个特殊情况，也是最坏情况。当我们将一个递增的序列添加到一个空树中的时候，
每次都是最大值在根节点，所以添加的新的节点在它的右侧，旋转到根节点，均会退化为链表。

• ex2

解释：这道题感觉比较有迷惑性，因为如果这颗树要找某个键值的节点，最多就是O(h)的时间复杂度
而我们根据摊还分析可以证明高度为O(logn),而后每次寻找都在根节点即为O(1),所以综上，时间复杂度为O（m+logn）

• ex3

解释：这是一道均摊分析的题目，所谓摊还分析就是对于任何情况下的操作$cost=actual cost+\Delta \phi=O(target)$,因为题干要求amortized cost为O(1),不妨定义$\phi=the opposite of the number of available cells in the array$,则当普通的添加操作一定符合O(1),研究扩展space时的操作$cost=c+nc+-nc=c$符合O(1),经验证其他选项都不满足条件。

• ex4
  
  解释：这道题存在疑问（我觉得是perform insertion consecutively？的问题）

hw3 b+tree and heap

• 知识1 b+树的定义与性质
  

  1. 根是叶子或者有2到M个孩子
  2. 所有非叶子的节点（除了根以外），有[M/2]到M个孩子，其本身最多存M-1个值
  3. 所有的叶子的深度是一样的（真实数据都存储在叶子中）
  4. 在空间最浪费的情况下是一颗[M/2]叉树，the deep of it is $O(log_{[M/2]}N)$

• 知识2 b+树的操作

  1. 查找：类似于不断比较，根据非叶节点的信息找到对应的叶子，然后从叶子中查找。
  2. 插入：首先用与查找相同的方式找到应该插入的位置，然后插入。但是有可能导致叶子节点的数量超过M，此时需要分裂。而分裂会导致家长节点的家长节点的子节点变多，矛盾可能上移。
     
     
  3. 删除：首先和查找一样找到待删除的点。直接删除后可能不会直接导致下溢的产生。若可以向兄弟节点(通常先向右兄弟借键)借键，如果兄弟都不足以把键借出，则进行合并操作，并更新父节点。然后就进行非叶节点即索引的判断，如果索引关键字数量不满足且有兄弟节点可借（父节点下移到这个索引中，兄弟节点上移），否则父节点下移合并成新的索引。

• 知识3 左偏堆（lefttist heap）的定义

  1. dist in leftist heap：如果一个结点的左孩子或右孩子为空结点则其dist为零，称为外结点。否则$dist=min(dist_{left child},dist_{right child})+1$
  2. leftist heap:左偏堆是满足结点的左孩子的dist不小于右孩子的dist的堆（这个定义与合并时有关）

• 知识4 左偏堆的操作

  1. 合并（核心操作）：先维护堆的性质，在回溯时维护左偏性质。（实际上是一个自上而下再自下而上的过程）具体操作，先比较当前两个待合并子树的根结点的键值，选择较小（较大）的那个作为根结点，其左子树依然为左子树，右子树更新为「右子树和另一个待合并子树的合并结果」。当然，在递归地更新完后，我们需要检查左子树和右子树是否满足$dist_{left child}>=dist_{right child}$,如果不满足则交换左右子树。
  2. 单点插入：本质上就是可以看作合并只有一个结点的左偏堆
  3. 单点删除：合并需要被删除的结点的两个子结点，将这个新的树的根代替被删除的结点，然后再回溯更新dist调整即可。$O(logn)$

• 知识5 一个lamma
  For a leftist heap with n nodes,its right path from the root to null has most $log_{2}(n+1)$ nodes

• 知识6 斜堆(skew heap)的操作
  斜堆也需要满足大根堆（小根堆）的性质，而它的合并和左偏堆的合并也十分类似，只不过我们这次无条件的交换左右子树，换句话来说，不管左偏性质如何变化，我们都会选择交换参与合并的左右子树，这样我们就不需要在回溯的时候才进行左右子树的交换，于是就实现了完全的自上而下。

• 知识7 摊还分析skew heap

  1. $\Phi(Heap)=number of heavy node in Heap$
  2. 对于一个子堆H，如果$size(H.right_descendant)>=\frac{1}{2}size(H)$则H为heavy node，否则为light node
  3. 如果一个节点是 heavy node，并且在其右子树发生了合并（包括翻转），那么它一定变为一个 light node；如果一个节点是 light node，并且在其右子树发生了合并（包括翻转），那么它可能变为一个 heavy node；合并过程中，如果一个节点的 heavy/light 发生变化，那么它原先一定在堆的最右侧路径上；
  4. $c^{1}=c+\phi(H_{merged})-\phi(H_{x})-\phi(H_{y})$,记录$l_{x}为H_{x}最右侧的light node的数量，h_{x}为最右侧heavy node数量,h_{x}^{0}为H_{x}所有不在最右侧路
     径上的heavy node数量$,我们可以得到$c=l_{x}+h_{x}+l_{y}+h_{y},\phi(H_{merged})<=h_{x}^{0}+h_{y}^{0}+l_{x}+l_{y}$
     $c^{1}<=l_{x}+h_{x}+l_{y}+h_{y}+l_{x}+l_{y}+h_{x}^{0}+h_{y}^{0}-h_{x}-h_{x}^{0}-h_{y}-h_{y}^{0}=2(l_{x}+l_{y})$
     最后可以得到为$O(logN)$

• 知识8 ppt中存在的代码实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  PriorityQueue Merge(PriorityQueue H1,PrioorityQueue H2) { if(H1==NULL) return H2; if(H2==NULL) return H1; if(H1->Element<H2->Element) return Merge1(H1,H2);//以前面的树的根为根,H2和H1的右子树合并成为新树的右子树 else return Merge1(H2,H1); } static PriorityQueue Merge1(PriorityQueue H1,PrioorityQueue H2) { if(H1->Left==NULL) H1->Left=H2; else{ H1->Right=Merge(H1->Right,H2); if(H1->Left->NPL<H1->Right->NPL) SwapChildren(H1); H1->NPL=H1->Right->NPL+1; } return H1; }

• 从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。

• 零距离(英文名NPL，即Null Path Length)则是从一个节点到一个”最近的不满节点”的路径长度。不满节点是指该该节点的左右孩子至少有有一个为NULL。叶节点的NPL为0，NULL节点的NPL为-1,也就是我们前文定义的dist

• ex1
  

解释：现在我们考虑b+树中的插入操作，因为题目的前提条件是leaf node没有发生分裂，则不需要更新internal node中的key。

• ex2
  

解释：（我觉得这个问题主要在于我的目光局限于2-3B+树）因为没有underflow操作。期中再编：因为没有发生underflow操作，

hw4 倒序查找与二向堆

倒排索引

• 倒排索引（inverted file index）是一种常见的文本检索技术，用于快速查找包含特定单词或短语的文档。它通过将单词或短语作为关键字，并将它们出现在文档中的位置记录在一个索引中，从而支持快速的文本检索

• 知识1 relevance

  1. 解释：主要是一些概念的明晰。 relevant irrelevant
     retrieved(检索) RR IR
     not retrieved RN IN
     precision=RR/（RR+IR）(针对检索到的文档的精确性)
     recall=RR/（RR+RN）（针对相关文档的能否检索的能力）
  2. relevance(相关性) measurement:a benchmark document of collection,a benchmark suite of queries,a binary assessment（二元评估） of either Relevant or Irrelevant for each query-doc pair

• 知识2 thresholding(阈值)
  注意document分布和query分布的评判标准
  

• 知识3 分布式索引与动态索引

  1. distributed indexing(分布式索引)中，each node contains index of a subset of collection
  2. 动态索引，docs come in over time，docs get deleted

• 知识4 measurement
  主要研究我们的搜索引擎判断标准评判标准（fast index,fast search,query language），注意区分data(response time,index space)和information(how relevant)的检索
  

• 知识5
  对于单词的访问存取(access)（采用哈希还是其他树）
  哈希的速度更快，但是但是range searches are expensive

• 知识6 改进
  首先是在文档中频繁出现的停用词(stop words),我们并不需要将它们记录下来；其次使用word stemming，将单词转化为母词根从而来减小倒排索引的规模。

二向队列(binomial queue)

• 知识1 二向队列的定义与性质
  1. 本质式是一系列二项树的集合
  2. k阶二项树是两个k-1阶二项树合并（直接令其中一颗树成为另外一颗树的新的child）得到
• 知识2 二向队列的操作
  1. 首先我们可以利用特征比特向量来理解二向队列的系列操作（1011就可以对应$B_{3}B_{1}B_{0}$）
  2. 合并：其实合并的结果可以通过前面我们所谓的两个队列的特征比特向量相加来得到。合并的过程也是和二进制加法有异曲同工之妙（即先低位合并，再高位合并）
  3. 查询队首：分别找各棵树的最小值
  4. 删除队首：先查询，再删除，再合并（也可以通过特征比特向量的计算提前确认结果）

hw5 回溯

选填小题

• 知识1 tic-tac-toe 题目

1. 一般做这个题的时候就直接把所有空全部填满，然后分别查看人与电脑获胜的情况的数目,记为$W_{computer},W_{Human}$
2. 定义：the goodness of a position $f(P)=W_{computer}-W_{Human}$
3. 所以human尽可能使f(P)小

• 知识2 阿尔法贝塔剪枝问题

总结：当利用阿尔法贝塔剪枝时解题顺序：左子树–根–右子树（基于深度优先搜索）
解释：在这道题目中，因为剪枝的情况是不会选用它的父亲则它被剪枝，当我们遍历知道它的父亲不选择时，此时它父亲的左孩子已经完成遍历，则右孩子被剪枝。

• 知识3 Eight Queens problem

1. 8皇后问题，我们只需要在每一行中选择一个皇后，然后判断是否和之前的皇后有冲突，如果有冲突则换一个皇后，直到找到一个不冲突的皇后，然后继续在当前行的下一列中寻找下一个皇后，直到找到一个不冲突的皇后…..
2. 也可以画game tree来理解解决这个问题的回溯过程。

• 知识4 the turnpike reconstruction problem

1. 给定N(N-1)/2 distances,然后重构n个点的坐标

2. 解决：step1:find the N;step2:x1=0,x6=10;step3:find the next largest distance and check

3. coding

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

   bool Reconstruct ( DistType X[ ], DistSet D, int N, int left, int right ) { /* X[1]...X[left-1] and X[right+1]...X[N] are solved */ bool Found = false; if ( Is_Empty( D ) ) return true; /* solved */ D_max = Find_Max( D ); /* option 1：X[right] = D_max */ /* check if |D_max-X[i]|D is true for all X[i]’s that have been solved */ OK = Check( D_max, N, left, right ); /* pruning */ if ( OK ) { /* add X[right] and update D */ X[right] = D_max; for ( i=1; i<left; i++ ) Delete( |X[right]-X[i]|, D); for ( i=right+1; i<=N; i++ ) Delete( |X[right]-X[i]|, D); Found = Reconstruct ( X, D, N, left, right-1 ); if ( !Found ) { /* if does not work, undo */ for ( i=1; i<left; i++ ) Insert( |X[right]-X[i]|, D); for ( i=right+1; i<=N; i++ ) Insert( |X[right]-X[i]|, D); } } if ( !Found ) { /* if option 1 does not work */ /* option 2: X[left] = X[N]-D_max */ OK = Check( X[N]-D_max, N, left, right ); if ( OK ) { X[left] = X[N] – D_max; for ( i=1; i<left; i++ ) Delete( |X[left]-X[i]|, D); for ( i=right+1; i<=N; i++ ) Delete( |X[left]-X[i]|, D); Found = Reconstruct (X, D, N, left+1, right ); if ( !Found ) { for ( i=1; i<left; i++ ) Insert( |X[left]-X[i]|, D); for ( i=right+1; i<=N; i++ ) Insert( |X[left]-X[i]|, D); } } /* finish checking option 2 */ } /* finish checking all the options */ return Found; }

• ex1 dfs与bfs加剪枝的速度
  

解释：

1. good path其实是寻找由所有good节点构成的一条路（每个节点可能为good或者bad）
2. 其实这道题可以从老师的hint中看，假设一个例子左边的叶子的深度十分深而右侧的叶子深度较浅，则我们一定存在这样的例子，当使用bfs时并没有像dfs一样遍历完那么深的深度就已经提前进行剪枝操作，则我们的时间就比dfs要短。

hw6 贪心

• 知识1
  贪心算法的基本概念
  只有当局部优解等于全局优解时可以使用；贪心算法的使用是一个逐步逼近最佳方法的过程

• 知识2（activity selection problem）

1. 这是一个常见的贪心问题，在一定的时间内有一系列活动安排，但是两个活动的进行时间不能有交叉，需要求的这个时间内所能举行的最多的活动数量。
2. 寻找贪心法则：每次寻找结束时间最早的活动
3. 我们想要证明我们理论的正确性，我们利用反证法，若A是按照理论取得的解，若存在一个S，但是S比A更优，我们假设A和S前t个活动都相同，那么在t+1个活动时，因为A按照最优则$f_{i(t+1)}<=f_{j(t+1)}$，则我们再后面遇到不一样时都可以用i替换j，但是最终我们会发现S不可能比A会多出活动，则假设矛盾，则我们得证。
4. 时间复杂度$O(nlogn)$

• 知识2（haffuman coding）

1. 这一道题目我们需要寻找到一个最优的编码映射满足：the cost of $\sum_{}{}d_{a}*f_{a}$ is mininum（分别为霍夫曼树对应字符的深度和字符在字符串中出现的频次）;且没有一个字符的编码是另一个字符编码的前缀（也就是说，每一个字符都在叶子上面）
2. 霍夫曼解决此问题的算法如下：首先创造一系列单节点的树，然后找到两颗频次最小的树进行合并，这两颗小树则被森林删除，取而代之的是他们合并的结果，这颗大树的频次则是两颗小树频次之和。重复上述操作直到森林只有一颗树。
   下面有一个ppt的样例，我觉得是频次小的放在合并的左子树
   
3. 时间复杂度为O（NlogN）
4. 证明算法的正确性：首先有一个lamma，如果a和b是频次最低的两个字符，那么a和b在霍夫曼树中一定是兄弟。利用归纳假设加上反证法：即假定存在一棵树A，不满足霍夫曼算法但是是最优的，我们将最下层的两个结点合并得到A1，同理对霍夫曼树我们也能得到H和H1，但是在k-1个节点时我们已经知道H1是最优的，所以A不可能是最优的。

• ex1（greedy）
  

解释：其实C也很容易举出反例，因为可能存在d很大但是p很小，并且这种情况很多时当我们去到ddl很靠近的事件时已经早已逾期ddl了。我们再来正面思考情况，很容易知道

hw7 分治

• 知识1 counting inversion

  1. 定义一个数组，如果$A[i]>A[j]，i<j,(i,j) is a inversion$
  2. output #inversion（inversion的数量）
  3. 若采用枚举$O(n^2)$,分治$O(nlogn)$
  4. 将这个数组左右等分为两半,那么所有的inversion分为三种情况(leftinversion,rightinversion,splitinversion),前两种情况的结果都可以使用递归得到,第三种情况如果使用暴力枚举其实时间还是n的平方的数量级=》优化：假如此时左右两侧都是排好序的,我们直接利用归并的merge将两侧合并，每次数量都加上左侧剩余的数量即可，那么就能在O(n)时间内解决问题。
  5. 总结(sort-and-countinv)

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  if n<=1: return (A,0); else L=lefthalf of A; R=righthalf of A; (B,leftINv)=sort-and-countinv(L); (C,rightInv)=sort-and-countinv(R); (D,spiltInv)=merge-and-countInv(B,C); return (D,leftInv+rightINv+spiltInv); Merge-and-countInv(B,C): i=1,j=1,splitinv=0; int D[n]; for k=1 to n: if B[i]<C[j] D[k]=B[i]; i=i+1; else D[k]=C[j]; j=j+1; splitInv+=n/2-i+1; return (D,splitInv);

  6. 时间T(n)=2T(n/2)+O(n);->T(n)=O(nlogn)

• 知识2 closest pair(这个例子还没有特别熟悉)

  1. 首先根据横坐标分为两部分(leftpair,rightpair,splitpair)
  2. 当分治时，左右两侧的最小值我们都可以通过递归得到，所以现在就能产生一个较小的距离记作$\delta$，接着我们按照上述的中轴线在水平位置$\delta$的距离形成一条带子，再对里面的每一个点以$\delta$\2为半径形成8个正方形，则每个正方形都至多有一个点(因为如果有两个点就与我们前面递归得到的结果相矛盾)
  3. 伪代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

  Px:sort P by x-cord Py:sort P by y-cord closest pair(Px,Py) if n<=3 final Lx=pts on the lefthalf plane,sorted by x-cord Ly=pts on the lefthalf plane,sorted by y-cord 在Rx和Ry的前提下都能以o(n) Rx=pts on the righthalf plane,sorted by x-cord Ry=pts on the righthalf plane,sorted by y-cord (l1,l2)=closest pair(Lx,Ly) (r1,r2)=closest pair(Rx,Ry) $\delta$=min(d(l1,l2),d(r1,r2)) (s1,s2)=closest split pair(Px,Py,$\delta$) return min($\delta$,d(s1,s2)) closeSplitPair(Px,Py,$\delta$): x1=largest x-cord of the lefthalf plane; Sx={points q1,q2.....with x1-delta<=qi.x<=x1+delta} sorted by y-cord mindist=$\infty$; colset=null; for i=1 to k for j=1 to 8 if(d(qi,q(i+j))<delta) delta=d(qi,q(i+j)) closet=(qi,q(i+j))

  • 知识3 分析divide and conquer的时间复杂度

    1. $T（1）=1$；

    2. $T（n）=a*T（n/b）$+$n^c$

    3. recursion tree method:$T(n)=2*T(n/2)+n,T(1)=1$
       上面是已知条件，下面我们画出递归树，我们发现在递归的深度为 $( k )$ 时，在前面每一层所有节点花的时间之和为 $( n )$，而最终降到最底层时的深度为 $( \log n )$，所以时间复杂度为 $( O(n \log n) )$。而我们不同的题目可能每一个节点所花费的时间有所不同，每一层的总时间可能相同 $(( n ))$，可能递减，可能递增 $(( \sqrt{n} ))$。更一般的情况：我们记根节点为第 0 层，每一个节点数量为 $( \frac{n}{b^i} )$，节点数目为 $( a^i )$，每个节点花费时间 $( a^i \left(\frac{n}{b^i}\right)^c )$。

    4. master method: 首先定义$T(N)=aT(\frac{n}{b})+f(n)$
       形式一
       
       主方法(master method)之所以叫“主”，是因为它分析的是 combine 和 conquer 部分孰为主导」，观察三种情况的区分条件都是比较 f(N)（每一次的 combine 开销） 和 $N^{log_{b}a}$（即求和式中的 conquer 的开销），当 f(N) 足够小时，以 conquer 开销为主（i.e. case 1）；当足够大时，以 combine 为主（i.e. case 3）；而其中还有一个中间状态（i.e. case 2）。
       形式二
       
       另外更复杂的形式,其实是f(n)的特殊形式的情况（最好能够记忆下来）
       

    5. 第三种方法（详情见毛老师的手写笔记）代换法：
       首先大眼猜测最终的复杂度，然后利用归纳假设进行证明即可

hw8 动态规划

• 知识1 weighted independent set on paths

  1. 考虑在一条路上，输入一系列带有权值的点，输出一系列独立(两个点之间没有公共的边)的权值之和最大的解
  2. 对于在n点的考虑，$S_{n}=Math.max{S_{n-1},S_{n-2}+v_{n}}$
  3. let c[i] be the total weight of the optical solutions of the vertcal i
  4. 伪代码:c[0]=0,c[1]=v[1],c[i]=max(c[i-1],c[i-2]+v[i])
  5. 实现方式:递归 $T(n)=T(n-1)+T(n-2)+O(1)$会存在重复计算，所以时间最终所用时长较长,或者用一个全局数组来记录c[i]，每次递归我们只针对未被计算的c[i]进行计算，这样时间复杂度就为$O(n)$。若使用循环，则直接从前向后计算即可。
  6. 怎么计算我们是否选择v[n]呢？只需判断c[n]与c[n-1]是否相同，若相同则未选(复制c[n-1])，若不同则(c[n]=c[n-2]unionv[n]) 实现时利用递归实现即可

• 知识2 ordering matrix multiplication

  1. 输入：一系列矩阵，输出：对这一系列矩阵进行乘法，使得最少的运算次数

  2. bi=#possible ways to multiply i matrixes,当我们考虑的时候通常考虑最后一次乘法时的两个矩阵的组成结构，例如四个矩阵相乘时分为：$b_{2}*b_{2};b_{1}*b_{3};b_{3}*b_{1}$。那我们此时对bn进行拆分：$\sum_{1}^{n-1}b_{i}b{n-i}$

  3. 拆分子问题：$c[i][j]$ be the minimun cost of $m_{i}*m_{i+1}….m_{j}$
     $c[i][j]=min[{c[i][k]+c[k+1][j]+r_{i-1}*r_{k}*r_{j}}]$

  4. 运算顺序：

     1 2 3 4 5 6 7

     for i=1 to n c[i][i]=0 for t=1 to n for i=1 to n-t j=i+t c[i][j]=min(c[i][k]+c[k+1][j]+r[i-1]*r[k]*r[j]) return c[1][n]

• 知识3 dp的小题主要要观察状态转移时是否前面有未知量

• 知识4 背包问题

  1. n items 每一个都有weight和对应的价值，然后有一个容量的背包。

• 知识5 optimal bst

  1. 输入n keys并且具有相对应的频率，output:a bst with mininum average search time

hw10 np-completeness

• 知识1 haltting problem

  1. 描述：given a programme P，an input x.Does P halt on input x?
  2. assume 存在 a programme Halt,Halt(P,x) return true if P halts on input x,false otherwise.
     构造：Diagonal(P):if Halt(P,P)==true looping else terminate.
  3. 我们再把构造出的diagonal展开:looping if p halts on p;halt if p loops on p;
  4. 但是当我们用diagonal替换P时就会发现我们前面的第二个式子的前后矛盾。则我们的假设不成立。那么这个problem不可计算。

• 知识2 complexity classes

• 知识3 最短路径

  1. given a weighted graph G=(V,E),(1)find the shortest path from s to t (2)length of shortest path? (3) given a integer k,是否存在s到t有一个路径的长度小于等于k
  2. 难度:(1)>=(2)>=(3)

• 知识4 多项式时间的算法
  An algorithm A has a polynomial-time running time if there exists a polynomial p(n) such that the running time of A on an input of length n is bounded by p(n).

• 知识5 P class and NP class

  1. P is the set of all decision problems that can be solved in polynomial time.
  2. NP(Non-deterministic polynomial)<->(polynomial-time verfiable)（所有多项式时间可验证的判定问题的集合）
  3. V(x,t)=1,if t certifies x;0,otherwise.

• 知识6 多项式时间可验证

  1. we say V is an efficient verfier from problem x if
  2. V is a polynomial-time algorithm that takes two arguments:an instance I of x and t
  3. for any instance I of x ,I is a yes-instance if and only if there exists a proof t with $|t|<=poly(|I|)$ and V(I,t)=1
  4. 则problem多项式时间可验证

• 知识7 汉密尔顿圈问题

  1. Given a graph G=(V,E),is there a Hamiltonian cycle（恰好经过每个顶点一次） in G.
  2. $t=v_{i1},v_{i2},…,v_{in}$
  3. V(I,t):test每个顶点是否都在t中出现一次，if no return;再看每个顶点相邻两边是否有边，都满足 return 1
  4. 我们再对照前面的多项式时间可验证的定义，则hamiltonian cycle NP-complete

• 知识8 np与p

  1. 我们已知p含于np，但是p与np是否相等呢？
  2. 假如现在有两个problem x,y 若任意的实例$I_{x}$我都可以在多项式时间内映射到实例$I_{y}$,并且我的映射能保证映射前后的yes-instance性质不变
  3. 如果存在一个多项式时间的算法B for y,则我可以设计一个算法A for x，使得$A(I_{x})=B(F(I_{x}))$ $T<=poly(poly(I_{x}))$（因为数据规模不会超过多项式级所以我们能得到这个不等式）那么我们认为yproblem更困难，并把映射叫作规约(reduction)函数

• 知识9 TSP问题

  1. Given a complete graph G=(V,E) with edge weights and k,is there a cycle that visits each vertex exactly once and total cost is less than k?
  2. 我们现在尝试按照知识8，寻找一个规约联系汉密尔顿圈与TSP问题：首先TSP问题基于完全图，我把汉密尔顿原图存在的边设为1，补的红边设为2.$k=|V|$。解释:如果G有一个汉密尔顿圈，在$G^{.}$中的cost肯定不超过k，否则$G^{.}$的cost肯定超过k，所以不存在。所以左右两侧的yes-instance属性满足，我们的规约没有问题。

• 知识10 clique problem and vertex cover problem

  1. clique problem:Given a graph G=(V,E) and k,is there a subset of V with size >=k such that every two vertices in the subset are connected by an edge?
  2. vertex cover problem:Given a graph G=(V,E) and k,is there a subset of V with size <=k such that each edge in E is incident to at least one vertex in the subset?
  3. 我们现在尝试规约团问题与顶点覆盖问题。如果在左边的实例$V^{.}$是一个团，那么右边$V-V^{.}$是一个顶点覆盖。

• 知识11 np-complete

  1. x属于np
  2. for any y属于np,$y<=px$，那么X为np完全problem
  3. 结论：3SAT为np完全problem，而如果另外的np问题Z也可以被3SAT归约，那么z也是np完全问题
  4. 结论：如果np完全问题也能被多项式解决那么，P=NP

• 知识12 图灵机

  1. $\delta(p,a)=(q,b)$ where p(now),q(next) are states and a,b(move left/right,write) are symbols
  2. 如果是确定性的图灵机则读到现在的字符，下一个状态是固定的。

• 知识13 language

  1. 给定问题X，集合L{“I”(编码)：I is a yes-instance of X}

期中刷题的一些记录

16-17期中模拟（-3-6）

• ex1 关于旋转
  
  解释：首先zig zag zig-zag操作就是针对于splay树而言，当进行多次旋转时，节点深度通常会大约减半。

• ex2 b+树的相关知识
  
  解释：首先是b+树的order理解不足，在我们前面基础知识部分提到的M就是order

• 知识1
  在红黑树中，内部红节点的度数不可能为1.

• 知识2 AVL（薄弱）

  1. AVL树中height的定义:ppt中the height of an empty tree is defined to be -1.
  2. The balance factor BF(node)=$h_{L}-h_{R}$
  3. 调整平衡时的具体操作有一点点忘却啦.（尤其是两次旋转时都是对于发现出错的下面最近的两个节点与其操作）

• 知识3 二向队列合并的具体代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

  BinQueue BinQueue_Merge( BinQueue H1, BinQueue H2 ) { BinTree T1, T2, Carry = NULL; int i, j; H1->CurrentSize += H2-> CurrentSize; for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 ) { T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i]; switch( 4*!!Carry + 2*!!T2 + !!T1 ) { case 0: case 1: break; case2: H1->TheTrees[i]=T2;H2->TheTrees[i]=NULL;Carry=NULL;break; case 4: H1->TheTrees[i] = Carry; Carry = NULL; break; case 3: Carry = CombineTrees( T1, T2 ); H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;11111111111 case 5: Carry = CombineTrees( T1, Carry ); H1->TheTrees[i] = NULL; break; case 6: Carry = CombineTrees( T2, Carry ); H2->TheTrees[i] = NULL; break; case 7: H1->TheTrees[i] = Carry; Carry = CombineTrees( T1, T2 ); H2->TheTrees[i] = NULL; break; } /* end switch */ } /* end for-loop */ return H1; } CombineTrees( BinTree T1, BinTree T2 ) { /* merge equal-sized T1 and T2 */ if ( T1->Element > T2->Element ) /* attach the larger one to the smaller one */return CombineTrees( T2, T1 ); /* insert T2 to the front of the children list of T1 */ T2->NextSibling = T1->LeftChild; T1->LeftChild = T2; return T1; }

15-16期中模拟（-3-3-5-4）

• 知识1 动态规划与多项式解决问题并不存在相关性
• 知识2 红黑树的插入后调整的三种情况
  1. LL:左左，此时只需要对u进行右旋即可，然后两个儿子均为红
  2. LR：旋转后转化为第一种情况
  3. 父亲和父亲兄弟与自己：先把父亲和父亲兄弟染黑，父亲父亲染红再观察。
• 知识3 一个操作的均摊操作与平均时间：
  平均时间 是针对算法在所有可能输入上的平均性能，考虑了输入分布或随机性的影响。它是一种概率性分析，往往需要假设输入的分布是已知的
  均摊时间 则是针对一系列操作的总时间进行分析，并通过分摊成本得出单个操作的平均时间。它不依赖于输入的概率分布，而是通过考虑整体操作序列的代价，来平均每次操作的开销。
• ex1 红黑树的黑高
  
  解释：在红黑树中我们存在一个结论$bh(u)>=\frac{1}{2}h(u)$,$2^{2*bh(u)}>=2^{h(u)}>=u$，$sizeof(x)>=2^{bh(x)}-1$ 与题目描述不符
• ex2 分治的时间复杂度
  
  解释：$T(N)=4*T(N/5)+O(logN)$,$T(N)=aT(N/b)+O(N^{k}(logN)^{p})$,$a>b^{k},O(N^{log_{b}a}),a=b^{k},O(N^{k}(logN)^{p+1}),else,O(O(N^{k}(logN)^{p}))$

王灿期中 24-25秋冬

• 知识1 $\alpha,\beta$剪枝操作
• 知识2 红黑树的删除操作（之前复习未覆盖）
• 知识3 b+树的时间复杂度（确实是容易被忽视的一个点）
• 知识4 有关动态规划的一道题目
  
  解释：这一道dp也是leetcode上面经典的一道二维dp的题目，我们的状态转化方程其实本质上基于题干上面的三个操作，按照题干进行定义，when $word1[i]=word2[j],dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]-1)$
  $word1[i]!=word2[j],dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])$
• 错误点1 对于堆的均摊操作的考虑
  
  解释：只有先记结论（lz暂时没有给出严格证明）
• 错误点2 分治的主方法未能记住并灵活运用(正如15-16期中模拟一样)
  
  解释：$T(n)=4*T(n/4)+log(n)$,we can get $a=4,b=4,k=0,p=1,a=b^{k},O(N^{k}(logN)^{p})$
• 错误点3 程序填空题（个人认为这个题的难度在期中应该是T0存在）
  
  解释：首先我认为我们需要弄明白各个数组的含义，首先在main函数中可以知道，cost[]代表在这个n的情况下，对应的$i^{n}$;current为当前待判断的数看它是否是n-narcissistic number;t[]则是存储current的各个位数的相应数字;

bjj 期中24-25秋冬

• 错误点1 二向队列的构建
  
  解释：这道题我觉得最主要的是概念问题，首先binomial queue是由binomial tree组成，而subtree又是组成binomial tree，在形成一颗binomial tree时是按照层次结构，并不能简单的说是按照increasing number。
• 错误点2 二向队列的删除
  
  解释：首先我觉得这道题出错最可能的原因是不太清楚二向队列的各个参数的具体含义。首先currentsize代表是整个二向队列的所有的节点数量，而不是binomial tree的数量！,并且这一道题不知道是否存在math库所以我们采用移位操作$Ind<<1-1$,而在下面的一个空主要是对于二向树的结构的了解不够深，我们的最左的子树其实是size最大的则我们的循环语句$for(i=Ind-1;i>=0;i–)$
• 知识点1 渐进上限
  
  解释：首先对于题干中的中文解释其实就是渐进上限，就我自己思考而言，当n足够大时在一定程度上可以减弱“17”的效果，这样可以运用主方法，但是较为严谨的还是利用递归树来看待这个分治复杂度，$T(n_{i})<=n+17$（递归树中每一层的时间复杂度的上限）

$\tau$