2018春问题求解笔记
2-1 算法正确性(2018.3.7)
程序和算法不等同
算法正确性是基础
“Program testing can be used to show the presence of bugs, but never to show their absence!”
封闭环境内同一个输入会产生同样的错误，但网络环境以及并行下不一定。错误的难重现
部分正确性(if terminates)和完全正确性(indeed terminates)
循环不变式
show converge
assertion和checkpoint：我们可以在算法的任意位置，设置assertion，这个“位置”就是check point
证明就是断言的序列
一条链
递归：数学归纳法
证明多个变量的数学归纳法：$\forall$ m, 对n做归纳
习题讲解(2018.3.12)
totalwork = workdone + worktodo
(1)->(2)->(2')->(3)->(4)
open topic
1.证明插入排序的完全正确性
两层循环 内层 外层
2.证明旋转汉诺塔的完全正确性
状态数 操作数：操作数>状态数，则非最优解
2-2 算法的效率
open topic
Algorithmic Gap
Decision Tree
Adversary Argument
2-3 组合与计数
计数在算法分析中很重要
抽象
加法原理 乘法原理
kth falling factorial power of n
Pascal’s triangle
Pascal relationship
multiset：放入k个后取
等价关系用于计数 等价类 商集
2-4 分治法与递归
Divide-and-Conquer: 3steps(Divid -> Conquer -> Combine)
递归中subproblem出现的两种case:recursive case, base case
three methods for solving recurrences:
- substitution method
- recursion-tree method
- master method
maximum-subarray problem
consider the daily change in price
divide-and-conquer解法: 把序列一分为二，然后最长的有三种情况，全在左边一半，全在右边一半，横跨中点。然后重点如何处理第三种情况，在中点向两边分别找，然后合并。复杂度为O(nlogn).
有O(n)算法 类似于DP
Strassen’s algorithm for matrix multiplication
$O(n^3) -> O(n^{2.81})[O(n^{lg7})]$
substituition method
Guess and then prove. Mathematical Induction.
- Guess the form of the solution.
- Use mathemarical induction to find the constants and show that the solution works.
一些证明中的小技巧:改变起始项，更换变量
Recursion-tree method
A recursion-tree is best used to generate a good guess.
Analyse and then sum.
master method
prove
为什么分治法能降低时间复杂度？
2-5 递归及其数学基础
求解精确解
Mathematical Induction
- base case
- inductive hypothesis
- inductive step
- inductive conclusion
The terms weak and strong arise from what is assumed in the inductive hypothesis. Adding more restrictions strengthens an assertion, while removing restrictions weakens the assertion
recursion和mathematical induction有密切联系 一个自上而下(分解问题) 一个自下而上(组合问题)
structural induction
triangulated polygon Ear Lemma
等比数列
first-order linear recurrence ：T(n) = f (n)T(n − 1) + g(n)
巧用微积分知识
解一阶线性：直接展开
解线性齐次：解特征方程
2-6 算法方法
问题求解：压缩解空间
Maximal Polygon Distance问题
Minimal Spanning Tree
Greedy DP(本质上还是穷竭搜索 但空间换时间)
DFS BFS
Bin packing NPC问题
2-7 离散概率
Complementary Probabilities
The Uniform Probability Distribution
(Principle of Inclusion and Exclusion for Probability) Proof1: 算P(x)的系数 用二项式定理 Proof2:待理解
Conditional probability: P(E|F)=P(E \cap F) / P(F) [P(E|F)=P(E) when P(F)=0]
We say E is independent of F if P(E|F) = P(E). 我认为P(E|F)不是由公式导出的。存疑
Bayes’ Theorem：P(E|F)P(F) = P(F|E)P(E).
product principle for independent probabilities: P(E \cap F) = P(E)P(F)
independent trials process
our model of hashing is an independent trials process.
probability tree
A random variable for an experiment with a sample space S is a function that assigns a number to each element of S.
Bernoulli trials process
expected value
indicator random variable
The Number of Trials until the First Success
指示器随机变量提供了一个便利的工具实现事件A发生的概率和期望之间的转换：求某个随机变量的期望往往可以简化为若干个和该随机变量相关的事件的概率之和
2-8 概率分析与随机化算法
conditional expected value
Randomized Algorithms
Quicksort分析
normal curve
variance
Central limit theorem.
normal distribution
2-9 排序与选择
The Coupon Collector’s Problem
$n log n + (m-1)nloglogn + nC_m + o(n), n \rightarrow \infty, m fixed$
Tony Hoare: Quicksort, Hoare Logic: {P}S{Q}, null pointer “I call it my billion-dollar mistake”.
证明下界：1. decision tree 2. adversary strategy
Adversary Argument：证下界
检测01、同时找最大最小、找第二小，k=3 is still open， 找中间值
2-10 基本数据结构
tail指向最后一个元素的后一个 为什么
Why Numbering Should Start at Zero(EWD831)
2-11 堆与堆排序
2-12 Hashing方法
2-13 搜索树
A tree is a recursive abstract data type
Binary Search Tree
Operations: Search(用while), Minimum(当子节点不为nil一直下去), Maximum, Predecessor(分两种情况:有右子树 无右子树), Successor, Insert and Delete(分三种情况). Transplant(不管子节点)
The expected height of a randomly built binary search tree is $O(\lg{n})$.
B-trees are particularly good for maintaining databases on secondary(disk) storage
Binary-search-tree property
If y is a node of left subtree of x, then $y.key \le x.key$.
If x is a node of right subtree of x, then $y.key \ge x.key$
tree walk
inorder tree walk Inorder-tree-walk(T.root)
INORDER-TREE-WALK(x)
if x!=NIL
INORDER-TREE-WALK(x.left)
print x.key
INORDER-TREE-WALK(x.right)
如何证明其正确性 效率$\Theta(n) 用master直观 用替代法证明$
preorder tree walk
postorder tree walk.
Tree-Search and Tree-Insert
Minimum and maximum
Successor and Predecessor
Tree-Successor(x)
if x.right!=NIL
return Tree-Minimum(x.right)
y=x.p
while y!=NIL && x=y.right
x=y
y=x.p
return y
Insertion and Deletion
插入找空位就可
删除分三种情况：没有孩子(直接删除)、有一个孩子(直接登基)、有两个孩子(找后继)
Transplant(T,u,v)
if u.p==NIL
T.root=v
elseif u==u.p.left
u.p.left=v
else
u.p.right=v
if v!=NIL
v.p=u.p
Tree-Delete(T,z)
if z.left==NIL
Transplant(T,z,z.right)
elseif z.right==NIL
Transplant(T,z,z.left)
else
y=Tree-Minimum(z.right)
if y.p!=z
Transplant(T,y,y.right)
y.right=z.right
y.right.p=y
Transplant(T,z,y)
y.left=z.left
y.left.p=y
Red Black Tree
red-black properties
- Every node is either red or black
- The root is black
- Every leaf(NIL) is black
- If a node is red, then both its children are black.
- For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
A red-black tree with n internal nodes has height at most $2\lg{n+1}$
Rotations
Left-Rotate(T,x)
y=x.right
x.right=y.left
if y.left!=T.nil
y.left.p=x
y.p=x.p
if x.p==T.nil
T.root=y
elseif x==x.p.left
x.p.left=y
else
x.p.right=y
y.left=x
x.p=y
In every n-node binary search tree, there are exactly n-1 possible rotations.
Insertion
RB-INSERT(T,z)
y=T.nil
x=T.root
while x!=T.nil
y=x
if z.key<x.key
x=x.left
else x=x.right
z.p=y
if y==T.nil
T.root=z
elseif z.key<y.key
y.left=z
else y.right=z
z.left=T.nil
z.right=T.nil
z.color = RED
RB-INSERT-FIXUP(T,z)
RB-INSERT-FIXUP(T,z)
while z.p.color==RED
if z.p==z.p.p.left
y=z.p.p.right
if y.color==RED
z.p.color=BLACK //case1
y.color=BLACK //case1
z.p.p.color=RED //case1
z=z.p.p //case1
else if z==z.p.right
z=z.p //case2
LEFT-ROTATE(T,z) //case2
z.p.color=BLACK //case3
z.p.p.color=RED //case3
RIGHT-ROTATE(T,z.p.p) //case3
else (same as then clause with "right" and "left" exchanged)
T.root.color=BLACK
2-14 B树
Appendix C
Binomial bounds: C_n^k >= (n/k)^k
对于自然数集N: E[X]=\sum_{i=0}^{\infty} i*Pr{X=i} =\sum_{i=0}^{\infty} i*(Pr{X>=i}-Pr{X>=i+1}) = \sum_{i=1}^{\infty} Pr{X>=i}
Var[X]=E[X^2]-E^2[X]
Var[aX]=a^2Var[X]
Var[X+Y]=Var[X]+Var[Y]