下载文档原格式
第一课课程细节；绪论：算法分析，插入排序法(Insertion Sort)，归并排序(Merge Sort) 阅读：1-2章发测验02 演示课1 算法的正确性发《作业1》3 第二课渐进记号(Asymptotic Notation)。
递归公式(Recurrences)：置换法，迭代法，主方法阅读：3-4 章，除了§4.44 第三课分治法：Strassen 算法，费氏数列，多项式乘法。
阅读：28 章第2 节，30章第1节5 演示课2 递归公式，松散性阅读：Akra-Bazzi 的讲义6 第四课快速排序法，随机化算法阅读：5 章1 到 3 节，7 章收《作业1》发《作业2》7 演示课3 排序法：堆排序，动态集合，优先队列阅读：6 章8 第五课线性时间的排序法：时间下界，计数排序法，基数排序法阅读：8 章第1 到3 节收《作业2》发《作业3》9 第六课顺序统计学，中位数阅读：9 章10 演示课4 中位数的应用，桶排序阅读：8 章第 4 节11 第七课散列，全域散列阅读：11 章1 到3 节收《作业3》发《作业4》12 第八课散列函数，完美散列阅读：11 章第5 节13 演示课5 测验1 复习收《作业4》14 评分后的作业4可以在中午拿到15 测验116 演示课6 二叉搜索树，树的遍历阅读：12 章1 到 3 节17 第九课二叉搜索树和快速排序法之间的关系；随机二叉搜索树的分析阅读：12 章4 节发《作业5》18 第十课红黑树，旋转，插入，删除阅读：13 章19 演示课7 2-3树，B-树阅读：18 章1 到 2 节20 第十一课高级数据结构，动态顺序统计，线段树（区间树）阅读：14 章收《作业5》发《作业6》21 第十二课计算几何，区间查询阅读：33 章1 到 2 节22 演示课8 凸多边形阅读：33 章3 节23 第十三课van Emde Boas树，优先队列阅读：van Emde Boas 的讲义收《作业6》发《作业7》24 第十四课平摊分析，表的复制，可能法阅读：17 章25 演示课9 竞争分析，自我排序列26 第十五课动态规划，最长公共子序列，最优二叉搜索树阅读：15 章收《作业7》发《作业8》27 第十六课贪婪算法，最小生成树阅读：16 章1 到 3 节，23 章28 演示课10 贪婪算法和动态规划的范例29 第十七课最短路径1，Dijkstra算法，广度优先搜索阅读：22 章1， 2 节；第580 - 587 页，24章 3 节收《作业8》发《作业9》30 演示课11 深度优先搜索，拓扑排序阅读：22 章3 到 5 节31 第十八课最短路径2，Bellman-Ford算法，DAG最短路径，差分约束阅读：24 章1, 2, 4, 5 节32 第十九课所有点对最短路径，Floyd-Warshall，Johnson 的算法阅读：25 章收《作业9》33 第二十课不相交集合的数据结构阅读：21 章34 评分后的作业9可以在中午拿到35 第二十一课带回家发下测验2 ; 道德，解决问题(强制参加)发测验236 没有演示课- 解答测验2!37 没有课算法程序比赛开始(非强制参加)收测验238 第二十二课网络流，最大流最小割切定理阅读：26 章1 - 2 节发《作业10》(选答)39 演示课12 图的匹配算法(注：最大二分匹配)阅读：26 章3 节40 第二十三课网络流，Edmonds-Karp 算法参赛答案截止41 第二十四课随堂测验；比赛颁奖；后续课程的讨论《作业10》解答。
算法导论（第三版）－复习－第六部分图论22-26［转］22习题22.1-5 有向图G(V, E)的平⽅图。
链表表⽰时，对每结点u的Adj[u]中所有v加⼊队列，后边出队边将Adj[v]加⼊Adj[u]中。
矩阵表⽰时，若w[i, j]、w[j, k]同时为1则将w[i, k]置1.习题22.1-6 O(V)的时间寻找通⽤汇点。
汇点的特征是邻接矩阵的第j列除[j, j]外所有元素为1. 可将每⾏调整[j ,j]后作为⼀个整数，所有整数与运算，为1的位是汇点。
习题22.1-7 有向⽆环图的关联矩阵B，BB’每个元素C[i, j]=∑B[i, k]*B’[k, j]=∑B[i, k]*B[j, k]，即同时进i, j两结点与同时出i, j的结点总数-⼀进⼀出i, j两结点的结点总数。
习题22.2-7 类似BFS，d mod2为0则标为B（娃娃脸），d mod2为1则标为H（⾼跟鞋）。
但若有边连接相同类的结点，则⽆法划分。
wrestler(G){for each u in G{(u,v)=Adj[u];if(v.mark==u.mark){throw error;}if(v.d==NIL) {v.d=u.d+1; v.mark=v.d mod 2;}}}习题22.2-8 任意点之间的最短路径。
重复的Dijktra算法或Floyd-Warshall算法习题22.2-9 ⽆向图扩展为有向图。
问题变成要遍历所有边⼀次。
访问结点u时，将u的⼦结点v的其他边都可视为⼦集v，问题等价于u到v，访问v的集合，v到u。
u标为visiting⼊列，然后访问v，v标为visiting⼊列，然后访问v的后继结点，访问过的边标为visited，返回到visiting的点时，如果该点所有连接的边都标为visited只剩⼀条返回上级的边，则返回上级结点并将点标为visited，v出列，访问u的其他⼦结点，最终u出列。
全部结点出列后达到遍历所有边⼀次。
一、基础知识部分1. 算法的复杂性有时间复杂性和空间复杂性之分。
2. 算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。
3. 快速排序算法是基于分治策略的一种排序算法。
4. 矩阵连乘问题的算法可由动态规划设计实现。
5、算法是指解决问题的一种方法或一个过程。
6、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。
7、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
8、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
9. 贪心算法的基本要素是贪心选择质和最优子结构性质。
10. 动态规划算法的两个基本要素是最优子结构性质和重叠子问题性质。
11、合并排序算法是利用（A ）实现的算法A、分治策略B、动态规划法C、贪心法D、回溯法12、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解13．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法B动态规划法C、贪心法D回溯法14. 备忘录方法是那种算法的变形。
（B ）A、分治法B动态规划法C、贪心法D回溯法15．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B动态规划法C贪心法D回溯法16．贪心算法与动态规划算法的主要区别是（ B ）。
A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解17. （D ）是贪心算法与动态规划算法的共同点。
A、重叠子问题B、构造最优解C、贪心选择性质D最优子结构性质18. 矩阵连乘问题的算法可由（B ）设计实现。
A、分支界限算法 B 、动态规划算法C、贪心算法D、回溯算法19、使用分治法求解不需要满足的条件是（ A ）。
A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解20．下列是动态规划算法基本要素的是（ D ）。
第8次作业答案16.1-116.1-2543316.3-416.2-5参考答案：16.4-1证明中要三点：1.有穷非空集合2.遗传性3.交换性第10次作业参考答案16.5-1题目表格：解法1：使用引理16.12性质（2），按wi单调递减顺序逐次将任务添加至Nt（A），每次添加一个元素后，进行计算，{计算方法：Nt（A）中有i个任务时计算N0 (A),…,Ni(A)，其中如果存在Nj (A)>j,则表示最近添加地元素是需要放弃地，从集合中删除}；最后将未放弃地元素按di递增排序，放弃地任务放在所有未放弃任务后面，放弃任务集合内部排序可随意.解法2：设所有n个时间空位都是空地.然后按罚款地单调递减顺序对各个子任务逐个作贪心选择.在考虑任务j时，如果有一个恰处于或前于dj地时间空位仍空着，则将任务j赋与最近地这样地空位，并填入; 如果不存在这样地空位，表示放弃.答案（a1，a2是放弃地）：<a5, a4, a6, a3, a7,a1, a2>or <a5, a4, a6, a3, a7,a2, a1>划线部分按上表di递增地顺序排即可，答案不唯一16.5-2（直接给个计算例子说地不清不楚地请扣分）题目：本题地意思是在O(|A|)时间内确定性质2（性质2：对t=0，1，2，…，n，有Nt(A)<=t,Nt(A)表示A中期限不超过t地任务个数）是否成立.解答示例：思想：建立数组a[n],a[i]表示截至时间为i地任务个数，对0=<i<n，如果出现a[0]+a[1]+…+a[i]>i,则说明A不独立，否则A独立.伪代码：int temp=0;for(i=0;i<n;i++) a[i]=0; ******O(n)=O(|A|)for(i=0;i<n;i++) a[di]++; ******O(n)=O(|A|)for(i=0;i<n;i++) ******O(n)=O(|A|) {temp+=a[i];//temp就是a[0]+a[1]+…+a[i]if（temp>i）//Ni(A)>iA不独立；}17.1-1（这题有歧义，不扣分）a) 如果Stack Operations包括Push Pop MultiPush,答案是可以保持,解释和书上地Push Pop MultiPop差不多.b) 如果是Stack Operations包括Push Pop MultiPush MultiPop,答案就是不可以保持,因为MultiPush,MultiPop交替地话,平均就是O(K).17.1-2本题目只要证明可能性，只要说明一种情况下结论成立即可17.2-1第11次作业参考答案17.3-1题目：答案：备注：最后一句话展开：采用新地势函数后对i 个操作地平摊代价：)1()())1(())(()()(1''^'-Φ-Φ+=--Φ--Φ+=Φ-Φ+=-Di Di c k Di k Di c D D c c i i i i i i17.3-2题目：答案：第一步：此题关键是定义势能函数Φ,不管定义成什么首先要满足两个条件 对所有操作i ，)(Di Φ>=0且)(Di Φ>=)(0D Φ比如令k j+=2i ，j,k 均为整数且取尽可能大，设势能函数)(Di Φ=2k;第二步：求平摊代价，公式是)1()(^-Φ-Φ+=Di Di c c i i 按上面设置地势函数示例：当k=0，^i c =…=2当k ！=0,^i c =…=3 显然，平摊代价为O(1)17.3-4题目：答案：结合课本p249，p250页对栈操作地分析很容易有下面结果17.4-3题目：答案：αα=(第i次循环之后地表中地entry 假设第i个操作是TABLE_DELETE, 考虑装载因子:inum size数)/(第i次循环后地表地大小)=/i i第12 次参考答案19.1.1题目：答案：如果x不是根，则degree[sibling[x]]=degree[child[x]]=degree[x]-1如果x是根，则sibling为二项堆中下一个二项树地根，因为二项堆中根链是按根地度数递增排序，因此degree[sibling[x]]>degree[x]19.1.2题目：答案：如果x是p[x]地最左子节点，则p[x]为根地子树由两个相同地二项树合并而成，以x为根地子树就是其中一个二项树，另一个以p[x]为根，所以degree[p[x]]=degree[x]+1;如果x不是p[x]地最左子节点，假设x是p[x]地子节点中自左至右地第i个孩子，则去掉p[x]前i-1个孩子，恰好转换成第一种情况，因而degree[p[x]]=degree[x]+1+（i-1）=degree[x]+i;综上,degree[p[x]]>degree[x]19.2.2题目：题目：19.2.519.2.6第13次作业参考答案20.2-1题目：解答：20.2-3 题目：解答：20.3-1 题目：答案：20.3-2 题目：答案：第14次作业参考答案这一次请大家自己看书处理版权申明本文部分内容，包括文字、图片、以及设计等在网上搜集整理.版权为个人所有This article includes some parts, including text, pictures, and design. Copyright is personal ownership.6ewMy。
《算法导论》读书笔记（⼀） 本章是本书的开篇，介绍了什么是算法，为什么要学习算法，算法在计算机中的地位及作⽤。
算法（algorithm）简单来说就是定义良好的计算机过程，它取⼀个或⼀组值作为输⼊，并产⽣出⼀个或⼀组值作为输出。
即算法就是⼀系列的计算步骤，⽤来将输⼊数据转换成输出数据。
书中有⼀句话⾮常好： Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices. 是否具有扎实的算法知识和技术基础，是区分真正熟练的程序员与新⼿的⼀项重要特征。
以这句话激励⾃⼰要努⼒学习算法，夯实基础，成为真正熟练的程序员。
本章通过介绍插⼊排序和归并排序两种常见的排序算法来说明算法的过程及算法分析，在介绍归并排序算法过程中引⼊了分治（divide-and-conquer）算法策略。
1、插⼊排序 输⼊：n个数（a1,a2,a3,...,an） 输出：输⼊序列的⼀个排列（a1',a2',a3',...an'）使得（a1'≤a2'≤a3'≤...≤an'）。
插⼊排序的基本思想是：将第i个元素插⼊到前⾯i-1个已经有序的元素中。
具体实现是从第2个元素开始（因为1个元素是有序的），将第2个元素插⼊到前⾯的1个元素中，构成两个有序的序列，然后从第3个元素开始，循环操作，直到把第n元素插⼊到前⾯n-1个元素中，最终使得n个元素是有序的。
该算法设计的⽅法是增量⽅法。
书中给出了插⼊排序的为代码，并采⽤循环不变式证明算法的正确性。
我采⽤C 语⾔实插⼊排序，完整程序如下：1 void insert_sort(int *datas,int length)2 {3 int i,j;4 int key,tmp;5 //判断参数是否合法6 if(NULL == datas || 0==length)7 {8 printf("Check datas or length.\n");9 exit(1);10 }11 //数组下标是从0开始的，从第⼆个元素（对应下标1）开始向前插⼊12 for(j=1;j<length;j++)13 {14 key = datas[j]; //记录当前要插⼊的元素15 i = j-1; //前⾯已经有序的元素16 //寻找待插⼊元素的位置，从⼩到到排序，如果是从⼤到⼩改为datas[i]<key17 while(i>=0 && datas[i] > key)18 {19 /×tmp = datas[i+1];20 datas[i+1] = datas[i];21 datas[i] = tmp;×/ 这个过程不需要进⾏交换，因为要插⼊的值保存在key中，没有被覆盖掉，在此感谢”两⽣花“指出问题所在datas[i+1] = datas[i];22 i--; //向前移动23 }24 datas[i+1] = key; //最终确定待插⼊元素的位置25 }26 }插⼊排序算法的分析 算法分析是对⼀个算法所需的资源进⾏预测，资源是指希望测度的计算时间。
算法导论标准答案————————————————————————————————作者：————————————————————————————————日期：2第二章算法入门由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。
另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。
给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。
插入排序算法伪代码INSERTION-SORT(A)1 for j ←2 to length[A]2 do key ←A[j]3 Insert A[j] into the sorted sequence A[1..j-1]4 i ←j-15 while i > 0 and A[i] > key6 do A[i+1]←A[i]7 i ←i − 18 A[i+1]←keyC#对揑入排序算法的实现:public static void InsertionSort<T>(T[] Input) where T:IComparable<T>{T key;int i;for (int j = 1; j < Input.Length; j++){key = Input[j];i = j - 1;for (; i >= 0 && Input[i].CompareTo(key)>0;i-- )Input[i + 1] = Input[i];Input[i+1]=key;}}揑入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将元素A[ j]揑入，形成排好序的子数组A[1..j]这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个不伪代码认为的数组的数是第1个有所丌同，一般要注意有几个关键值要比伪代码的小1.如果按照大部分计算机编程语言的思路，修改为：INSERTION-SORT(A)1 for j ← 1 to length[A]2 do key ←A[j]3 i ←j-112 31 41 59 26 41 584 while i ≥ 0 and A[i] > key5 do A[i+1]←A[i]6 i ← i − 17A[i+1]←key循环丌变式(Loop Invariant)是证明算法正确性的一个重要工具。
《算法导论》摘记经典算法题集锦分治策略Diogenes教授有n个被认为是完全相同的VLSI芯⽚，原则上它们是可以互相测试的。
教授的测试装置⼀次可测⼆⽚，当该装置中放有两⽚芯⽚时，每⼀⽚就对另⼀⽚作测试并报告其好坏。
⼀个好的芯⽚总是能够报告另⼀⽚的好坏，但⼀个坏的芯⽚的结果是不可靠的。
这样，每次测试的四种可能结果如下： A芯⽚报告 B芯⽚报告 结论 B是好的 A是好的 都是好的，或都是坏的 B是好的 A是坏的 ⾄少⼀⽚是坏的 B是坏的 A是好的 ⾄少⼀⽚是坏的 B是坏的 A是坏的 ⾄少⼀⽚是坏的Q:1.证明如果超过n/2个芯⽚是坏的，使⽤任何基于这种逐对检测操作的策略，教授都不能确定哪些芯⽚是好的。
2.如果超过n/2个芯⽚是好的，如何O(n)找出所有好的芯⽚？解：对于问题2，只需找出1个好的芯⽚，就能确定所有的芯⽚的好坏。
粗暴的⽅法是拿⼀个芯⽚与其他所有芯⽚配对，因为好的⽐坏的多，就可以根据多的确定该芯⽚的好坏，直到找到⼀个好芯⽚为⽌。
复杂度是O(n2)的。
同时也说明了Q1(否则⽆法确定好坏) O(n)怎么做？递归缩⼩问题规模。
假设有偶数个芯⽚。
两两配对，有a对检测结果为都是好的，b对检测结果为⼀好⼀坏，c对检测结果为都是坏的。
取a对中每对的任意⼀个芯⽚，组成a个芯⽚的⼦问题。
易证明该⼦问题依然满⾜好的芯⽚数量多于坏的芯⽚。
(因为b+c对中坏的 >= 好的)如果有奇数个芯⽚。
两两配对，有a对检测结果为都是好的，b对检测结果为⼀好⼀坏，c对检测结果为都是坏的。
还有⼀个零头。
1.如果零头是坏的，则a对中好的芯⽚ > 坏的芯⽚，⽤a对去检测零头，发现有⼀半以上的检测结果是坏的，反⾔之⼩于⼀半的检测结果是好的。
2.如果零头是好的，则a对中好的芯⽚ >= 坏的芯⽚，⽤a对去检测零头，发现⼤于等于⼀半的检测结果是好的。
根据结果判断零头是好是坏。
如果是1，把零头弃掉；如果是2，把零头加进来，这样该⼦问题依然满⾜好的芯⽚数量多于坏的芯⽚。
