算法设计分析基础_教材纠错.doc

《算法设计分析基础》教材纠错
课程马上就结束了，今天来把在上课过程中发现的教材错误汇总一下。还真不少，现在想要找一本好点的教材可真不容易啊！

第2章 算法效率分析基础
1、第43页，定义2中的“t(n)<=cg(n)”应该是“t(n)>=cg(n)”
2、第50页，例2算法中的第一个循环“for i<-1 to n-2 do”应该是“for i<-0 to n-2 do”
3、第62页，习题9中算法描述的第3行“temp1<-Min1(A[l..[(l+r)/2])”中少了一个“]”，应为“temp1<-Min1(A[l..[(l+r)/2]])”，同时第4行的“temp2<-Min2(A[[(l+r)]+l..r)”应为“temp2<-Min2(A[[(l+r)]+1..r])”
第3章 蛮力法
1、第80页的算法SelectionSort(A[0...n-1])中的if A[j]<[min] min<-j中的[min]有错，应该是if A[j]<A[min]
2、第85页的算法BruteForceStringMatch(T[0..n-1],P[0..m-1])中的if i=m return i中的i=m有错，应该是if j=m return i

第4章 分治法
1、第100页，倒数第4行的“对上面的例子来说，a=1”中的“a=1”应该为“a=2”。
2、第102页的图4.2中最终的结果“1 2 3 4 5 6 7 8”应该是“1 2 3 4 5 7 8 9”，这个错误在影印版中也存在。
3、第117页，顺数第12行中的“当b=2^k时”应为“当n=2^k”。
4、第121页，倒数第6行的最后一句话“合并较小的子问题所化的时间...”应为“合并较小的子问题所花的时间..”。

第5章 减治法
第133页，顺数第5行中的“...那个这个图是连通的...”应为“...那么这个图是连通的...”。

第7章 时空权衡
1、第200页，算法DistrbutionCountingt中的顺数第8行“j<-A[j]-l”应为“j<-A[i]-l”。
2、第202页，第2自然段的顺数第2行的后部，“而Boyer-Moore算法从左到右比较”应为“而Boyer-Moore算法从右到左比较”。
3、第206页，在第3自然段的最后说“对于模式ABCBAB来说，在k=1和k=2时，这个距离分别是4和6”，而在下面的表中给出的却是2和4，同样在207页表中给出的也是2和4，按照作者的定义应该是2和4。这个问题在影印版中也是如此。
第9章 贪婪技术
第257页，Dijkstra算法实例演示中第2步的余下节点“c(d,3+4) d(b,3+2) e(-,-)”应为“c(b,3+4) d(b,3+2) e(-,-)”