1 第一课课程细节；绪论：算法分析，插入排序法(Insertion Sort)，归并排序(Merge Sort) 阅读：1-2章
发测验0
2 演示课1 算法的正确性
发《作业1》
3 第二课渐进记号(Asymptotic Notation)。递归公式(Recurrences)：置换法，迭代法，主方法
阅读：3-4 章，除了§4.4
4 第三课分治法：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 测验1
16 演示课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 ; 道德，解决问题(强制参加)
发测验 2
36 没有演示课- 解答测验2!
37 没有课
算法程序比赛开始(非强制参加)
收测验 2
38 第二十二课网络流，最大流最小割切定理
阅读：26 章 1 - 2 节
发《作业10》(选答)
39 演示课12 图的匹配算法(注：最大二分匹配)
阅读：26 章 3 节
40 第二十三课网络流，Edmonds-Karp 算法
参赛答案截止
41 第二十四课随堂测验；比赛颁奖；后续课程的讨论
《算法导论》复习笔记 Chapter 22 基本图算法 有向图邻接链表，计算节点出度和入度的时间复杂度 O(V+E) 开一个degree[]数组，大小为结点个数，复杂度O(V); 遍历邻接链表，经过边uv时，计算出度degree[u]+=1,计算入度degree[v]+=1,复杂度O(E) 将一个多图变成等价无向图，用邻接链表表示，时间复杂度O(V+E) 多图是允许重复边和自循环边的图。 开一个bool数组mark[],大小为节点个数，初始化为false。复杂度O(V)。 对每个顶点u的邻接链表，遍历，令v为u的边所指向的顶点；如果mark[v]=false，将uv加入新图，并将mark[v]设置为true；否则就跳过。复杂度O(E) 再次遍历u的连边，将mark[v]初始化 整体复杂度O(V+E) 伪代码: SOLVE(G,G’) 1 for each vetex u∈G 2 for each v∈ [u] 3 if mark[v]==false 4 mark[v]==true 5 Addedge(G’,u,v) 6 for each v∈[u] 7 mark[v]=false 图G的邻接矩阵表示，给出一个O(V)的算法来判断有向图G中是否存在一个通用汇点。 通用汇点指的是入度|V|-1，但出度为0。 等价问题：给定有向图G的V×V邻接矩阵G，在O(V)时间内判断是否存在一个数k，使得对所有的i有A[i][k]=1,对所有的j有A[k][j]=0,(i≠k,j≠k)
令i和j初值为1，若G[i][j]=0,说明i到j无边，j不可能是通用汇点，令j=j+1;若G[i][j]=1,说明i 到j有边，i不可能是通用汇点，令i=i+1，循环直到i>|V|或者j>|V|;若i>|V|，则不存在通用汇点，若j>|V|，则检查顶点i是否满足要求。 伪代码： 判断是否存在通用汇点 O(V) HAS_UNIVERSL_SINK(G) 1 i=j=1 2 while i≤V and j≤V 3 if G[i][j]==1 4 i=i+1 5 else j=j+1 6 if i>V 7 return false 8 else return CHECK(G,i) CHECK(G,u) 1 for each vertex v∈ 2 if G[u][v]=1 3 return false 4 for each vertex v ∈ 5 if G[v][u]==0& u!=v 6 return false 7 return true 检查点u是否是通用汇点 【宽度优先搜索】 计算无向图BFS后的d值和π值 简单，注意初始节点u的π值写NIL或者写-1
Chapter2 Michelle Bodnar,Andrew Lohr April12,2016 Exercise2.1-1 314159264158 314159264158 314159264158 263141594158 263141415958 263141415859 Exercise2.1-2 Algorithm1Non-increasing Insertion-Sort(A) 1:for j=2to A.length do 2:key=A[j] 3://Insert A[j]into the sorted sequence A[1..j?1]. 4:i=j?1 5:while i>0and A[i] 一、基础知识部分 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 ）。 A、定义最优解B构造最优解C、算出最优解D子问题重叠性质 二、分析解答部分 1 、堆的高度与元素个数之间的关系 2、散列表技术中碰撞的定义与解决方法是什么 3、平摊分析的方法有哪些？重点是势能法的应用。例、对某个数据结构执行一个n 个操作的序列。如果i 为2的整数次幂，则第i 个操作的代价为i ，否则为 1.请用势能分析来确定每次操作的平摊代价。 解：不妨设i 2j k，其中k和j均为非负整数，且j取满足等式最大的整数。 第二章算法入门 由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题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-1 5 while i > 0 and A[i] > key 6 do A[i+1]←A[i] 7 i ←i ? 1 8 A[i+1]←key C#对揑入排序算法的实现: public static void InsertionSort 2.1-2 重写过程INSERTION-SORT，使之按非升序（而不是按非降序）排序。 伪代码如下： INSERTION-SORT(A) for j←to length[A] do key←A[J] i←j-1 while i>0 and A[i] 初始化：首先，先来证明在第一轮迭代之前，它是成立的。此时，flag初始化为0，表示未找到这样一个小标i，使得A[i]=V.若为1，则表示已找到一个或多个这样的下标。那么，很显然，在还未开始之前flag=0是正确的，也就证明了循环不变式在循环的第一轮迭代开始之前是成立的。 保持：接下来证明每一轮循环都能使循环不变式保持成立。我们看到，在第一个for循环体内，随着i逐个从1到遍历完整个数列的过程中，只要有一个下标i，使得A[i]等于V，那么在输出i的同时，将flag重新标记为1，表示已找到。无论接下来是否还有这样满足条件的i出现，flag的值不变，仍为1，反之，若遍历完之后，没有找到这样的一个i，那么flag 在这个for循环中未做任何改变，仍为0。所以，循环不变式的第二个性质也成立。 终止：对此线性查找算法来说，当i大于length[A]的值（即遍历完整个A数列后），for 循环结束。这时，如果flag未改变（即flag=0），则说明未能找到这样的下标i，输出NIL；反之，若已在for循环中被修改为1，则不会运行此步语句，这也就意味着该算法是正确的。 2.1-4 有两个各存放在数组A和B中的n位二进制整数，考虑它们的相加问题。两个整数的和以二进制形式存放在具有(n+1)个元素的数组C中。请给出这个问题的形式化描述，并写出伪代码。 形式化描述如下： 首先，初始化数组C，使其n+1各元素的值都为0。接着，利用for循环用i同时从n到1反向遍历A、B数组，每遍历一步，作一个判断：若A[i]+B[i]>1，则C[i]=C[i]+1；反之，C[i+1]=A[i]+B[i]。最后，当i=0时，for循环结束，此时C数组中存储的即是所求的结果。 伪代码如下： BINRARY-SUM(A,B,C) for i←1 to n+1 do C[i]←0 for i←n to 1 do if A[i]+B[i]>1 then C[i]=C[i]+1 else C[i+1]=A[i]+B[i] 一、基础知识部分 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 ）。 A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质 二、分析解答部分 1、堆的高度与元素个数之间的关系 2、散列表技术中碰撞的定义与解决方法是什么 3、平摊分析的方法有哪些？重点是势能法的应用。 例、对某个数据结构执行一个n个操作的序列。如果i为2的整数次幂，则第i 个操作的代价为i，否则为1.请用势能分析来确定每次操作的平摊代价。 第一课课程细节；绪论：算法分析，插入排序法(Insertion Sort)，归并排序(Merge Sort) 阅读：1-2章 发测验0 2 演示课1 算法的正确性 发《作业1》 3 第二课渐进记号(Asymptotic Notation)。递归公式(Recurrences)：置换法，迭代法，主方法 阅读：3-4 章，除了§4.4 4 第三课分治法：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 测验1 16 演示课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 贪婪算法和动态规划的范例 Chapter2 Getting Start 2.1 Insertion sort 2.1.2 将Insertion-Sort 重写为按非递减顺序排序 2.1.3 计算两个n 位的二进制数组之和 2.2 Analyzing algorithms 当前n-1个元素排好序后，第n 个元素已经是最大的元素了. 最好时间和最坏时间均为2()n Θ 2.3 Designing algorithms 2.3.3 计算递归方程的解 22()2(/2)2,1k if n T n T n n if n for k =?=?+ = >? （1） 当1k =时，2n =，显然有()lg T n n n = （2） 假设当k i =时公式成立，即()lg 2lg 22i i i T n n n i ===?， 则当1k i =+，即12i n +=时， 2.3.4 给出insertion sort 的递归版本的递归式 2.3-6 使用二分查找来替代insertion-sort 中while 循环内的线性扫描，是否可以将算法的时间提高到(lg )n n Θ？ 虽然用二分查找法可以将查找正确位置的时间复杂度降下来，但 是移位操作的复杂度并没有减少，所以最坏情况下该算法的时间复杂度依然是2()n Θ 2.3-7 给出一个算法，使得其能在(lg )n n Θ的时间内找出在一个n 元素的整数数组内，是否存在两个元素之和为x 首先利用快速排序将数组排序，时间(lg )n n Θ，然后再进行查找： Search(A,n,x) QuickSort(A,n); i←1; j←n; while A[i]+A[j]≠x and i “算法分析与优化”教学大纲 [2009年版] 课程定位 《算法分析与优化》是软件开发人员必修专业课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和软件类专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。 课程总体目标 通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。鼓励学生运用算法知识解决各自学科的实际问题，培养学生的独立科研的能力和理论联系实践的能力。 课程内容简介 课程共分9章，首先在第1章介绍了算法的基本概念，接着对算法的计算复杂性和算法的描述做了简要介绍。 第2章介绍了递归与分治策略，这是设计有效算法的常用策略。 第3章介绍了动态规划算法，以具体实例详述了动态规划算法的设计思想，适用性已经算法的设计要点。 第4章介绍了贪心算法，这也是一种重要的算法设计策略，它与动态规划算法有一定的联系，但效率更高。按贪心算法设计出的许多算法能产生最优解。其中有许多经典问题和典型算法可供学习和使用。 第5章和第6章分别介绍了回溯法和分支限界法。这两章内容适合于求解难解的问题，其解题思想各具特色。 第7章介绍了概率算法，为许多难解问题提供了高效的解决途径。 第8章介绍了NP完全性理论，首先介绍了计算模型，确定性和非确定性图灵机，然后进一步深入介绍NP完全性理论。 第9章则是通过实例介绍算法设计中常用的算法优化策略。。 课程总学时 48学时 教材 《算法设计与分析》（第2版），王晓东编著，清华大学出版社，2008年 参考书 《算法导论》（第2版），Thomas H.Cormen，Charles E.Leiserson 等著，潘金贵顾铁成等译，机械工业出版社 算法导论第四章 摘自：百度文库 https://www.doczj.com/doc/4613532975.html,/link?url=QunHIQ6sgLN_uMads3Llc8mtkAKSkrn4OI9SuM_g3Tj_0a5N 2fkRVV03F9-iiPOgdcm7zAj54KToWqfeFvNffHr-WaJpeqXzWkDRzewxuhm https://www.doczj.com/doc/4613532975.html,/tanky-woo/archive/2011/04/12/144020.html 这一章讲的是递归式(recurrence)，递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值来定义的。 本章讲了三种方法来解递归式，分别是代换法，递归树方法，主方法。 1.代换法(Substitution method)(P38~P40) 定义：即在归纳假设时，用所猜测的值去代替函数的解。 用途：确定一个递归式的上界或下界。 缺点：只能用于解的形式很容易猜的情形。 总结：这种方法需要经验的积累，可以通过转换为先前见过的类似递归式来求解。 2.递归树方法(Recursion-tree method) 起因：代换法有时很难得到一个正确的好的猜测值。 用途：画出一个递归树是一种得到好猜测的直接方法。 分析(重点)：在递归树中，每一个结点都代表递归函数调用集合中一个子问题的代价。将递归树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。 总结：递归树最适合用来产生好的猜测，然后用代换法加以验证。 递归树扩展过程：①.第二章2.3.2节分析分治法时图2-5(P21~P22)的构造递归树过程；②.第四章P41图4-1的递归树构造过程；这两个图需要好好分析。 3.主方法(Master method) 优点：针对形如T(n) = aT(n/b) + f(n)的递归式 缺点：并不能解所有形如上式的递归式的解。 具体分析： Chapter35 Michelle Bodnar,Andrew Lohr April12,2016 Exercise35.1-1 We could select the graph that consists of only two vertices and a single edge between them.Then,the approximation algorithm will always select both of the vertices,whereas the minimum vertex cover is only one vertex.more generally,we could pick our graph to be k edges on a graph with2k vertices so that each connected component only has a single edge.In these examples,we will have that the approximate solution is o?by a factor of two from the exact one. Exercise35.1-2 It is clear that the edges picked in line4form a matching,since we can only pick edges from E ,and the edges in E are precisely those which don’t share an endpoint with any vertex already in C,and hence with any already-picked edge. Moreover,this matching is maximal because the only edges we don’t include are the ones we removed from E .We did this because they shared an endpoint with an edge we already picked,so if we added it to the matching it would no longer be a matching. Exercise35.1-3 We will construct a bipartite graph with V=R∪L.We will try to construct it so that R is uniform,not that R is a vertex cover.However,we will make it so that the heuristic that the professor(professor who?)suggests will cause us to select all the vertices in L,and show that|L|>2|R|. Initially start o?with|R|=n?xed,and L empty.Then,for each i from 2up to n,we do the following.Let k= n i .Select S a subset of the vertices of R of size ki,and so that all the vertices in R?S have a greater or equal degree.Then,we will add k vertices to L,each of degree i,so that the union of their neighborhoods is S.Note that throughout this process,the furthest apart the degrees of the vertices in R can be is1,because each time we are picking the smallest degree vertices and increasing their degrees by1.So,once this has been done for i=n,we can pick a subset of R whose degree is one less than the rest of R(or all of R if the degrees are all equal),and for each vertex in 1 《算法导论》CLRS算法C++实现（一）P11 插入排序 过几个月要面试了，最近在看《算法导论》，想把里面的算法都用C++实现一遍。今天是第一个算法，比较简单。 第二章算法入门 插入排序 伪代码实现 INSERTION-SORT(A) 《算法导论》P10 1for j ← 2 to length[A] 2do key ← A[j] 3//Insert A[j] into the sorted sequence A[1 ‥ j - 1]. 4i ← j - 1 5while i > 0 and A[i] > key 6do A[i + 1] ← A[i] 7i ← i - 1 8 A[i + 1] ← key C++代码实现 1 #include MIT-算法导论读书笔记-第二章给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。插入排序算法伪代码 INSERTION-SORT(A) 1for j←2 to length[A] 2do key←A[j] 3//Insert A[j] into the sorted sequence A[1..j-1] 4i←j-1 5while i>0 and A[i]>key 6do A[i+1] ←A[i] 7i←i-1 8A[i+1] ←key C#对插入排序算法的实现: public static void InsertionSort { key=A[j]; i=j-1; while(i>0 && A[i]>key) { A[i+1]=A[i]; i=i-1; } A[i+1]=key; } printf("the sort is:\n"); for(i=0;i<=9;++i) printf("%d\n",A[i]); } 插入算法的设计使用的是增量（incremental）方法：在排好子数组A[1..j-1]后，将元素A[j]插入，形成排好序的子数组A[1..j] 这里需要注意的是由于大部分编程语言的数组都是从0开始算起，这个与伪代码认为的数组的数是第1个有所不同，一般要注意有几个关键值要比伪代码的小1. 如果按照大部分计算机编程语言的思路，修改为： INSERTION-SORT(A) 1for j←1 to length[A] 2do key←A[j] 3i←j-1 4while i>=0 and A[i]>key 5do A[i+1] ←A[i] 6i←i-1 7A[i+1] ←key 循环不变式(Loop Invariant)是证明算法正确性的一个重要工具。对于循环不变式，必须证明它的三个性质： 初始化(Initialization)：它在循环的第一轮迭代开始之前，应该是正确的。 保持(Maintenance)：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也是正确的。 终止(Termination)：当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。 运用循环不变式对插入排序算法的正确性进行证明： 初始化：j=2，子数组A[1..j-1]只包含一个元素A[1],显然它是已排序的。 保持：若A[1..j-1]是已排序的，则按照大小确定了插入元素A[j]位置之后的数组A[1..j]显然也是已排序的。 终止：当j=n+1时，退出循环，此时已排序的数组是由A[1],A[2],A[3]…A[n]组成的A[1..n]，此即原始数组A。 练习 2.1-1：以图2-2为模型，说明INSERTION-SORT在数组A=<31,41,59,26,41,58>上的执行过程。 （2.1-1 麻省理工学院-算法导论 关于课本的介绍如下： 本书自第一版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考手册。本书全面论述了算法的内容，从一定深度上涵盖了算法的诸多方面，同时其讲授和分析方法又兼顾了各个层次读者的接受能力。各章内容自成体系，可作为独立单元学习。所有算法都用英文和伪码描述，使具备初步编程经验的人也可读懂。全书讲解通俗易懂，且不失深度和数学上的严谨性。第二版增加了新的章节，如算法作用、概率分析与随机算法、线性编程等，几乎对第一版的各个部分都作了大量修订。 学过计算机的都知道，这本书是全世界最权威的算法课程的大学课本了，基本上全世界的名牌大学用的教材都是它。这本书一共四位作者，Thomas H. Cormen，Charles E. Leiserson和Ronald L. Rivest是来自MIT的教授，Clifford Stein是MIT出来的博士，现在哥伦比亚大学做教授，四人姓氏的首字母联在一起即是此书的英文简称(CLRS 2e)，其中的第三作者Ronald L. Rivest是RSA算法的老大(算法名字里面的R即是指他)，四个超级大牛出的一本书，此书不看人生不能算完整。 再介绍一下课堂录像里面授课的两位MIT的老师，第一位，外表“绝顶聪明”的，是本书的第二作者Charles E. Leiserson，以逻辑严密，风趣幽默享誉MIT。第二位，留着金黄色的络腮胡子和马尾发的酷哥是Erik Demaine，21岁即取得MIT教授资格的天才，1981出生，今年才25岁，业余爱好是俄罗斯方块、演戏、琉璃、折纸、杂耍、魔术和结绳游戏。 另外，附上该书的中文电子版，pdg转pdf格式，中文版翻译自该书的第一版，中文书名没有使用《算法导论》，而使用的是《现代计算机常用数据结构和算法》，1994年出版时没有得到国外的授权，属于“私自翻译出版”，译者是南京大学计算机系的潘金贵。 课程重点 算法导论是麻省理工学院电机工程与计算机科学系“理论计算机科学”集中选修课程的先导科目。课程几乎将所有资料放到线上，包括了完整的课堂讲义和习题。课本“算法导论，第二版”，是由Charles Leiserson 教授副笔。 课程描述 本课程教授高效率算法的设计及分析技巧，并着重在有实用价值的方法上。课程主题包含了：排序、搜寻树、堆积及散列；各个击破法、动态编程、偿还分析、图论算法、最短路径、网络流、计算几何、数字理论性算法；多项式及矩阵的运算；高速缓存技术及并行运算。 一般资讯 讲师： Erik Demaine Partial Solutions for Introduction to algorithms second edition Professor: Song You TA: Shao Wen ACKNOWLEDGEMENT CLASS ONE: JINZI CLASS TWO: LIUHAO, SONGDINMIN, SUNBOSHAN, SUNYANG CLASS FOUR:DONGYANHAO, FANSHENGBO, LULU, XIAODONG, CLASS FIVE:GAOCHEN, WANGXIAOCHUAN, LIUZHENHUA, WANGJIAN, YINGYING CLASS SIX: ZHANGZHAOYU, XUXIAOPENG, PENGYUN, HOULAN CLASS: LIKANG,JIANGZHOU, ANONYMITY The collator of this Answer Set, SHAOWen, takes absolutely no responsibility for the contents. This is merely a vague suggestion to a solution to some of the exercises posed in the book Introduction to algorithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the solutions are wrong. If you have found an error, have a better solution or wish to contribute in some constructive way please send an Email to shao_wen_buaa@https://www.doczj.com/doc/4613532975.html, It is important that you try hard to solve the exercises on your own. Use this document only as a last resort or to check if your instructor got it all wrong. Have fun with your algorithms and get a satisfactory result in this course. Best regards, SHAOWen Solution to Exercise2.2-2 S ELECTION-S ORT.A/ n D A:length for j D1to n 1 smallest D j for i D j C1to n if A?i 2-2Selected Solutions for Chapter2:Getting Started A?low::high contains the value .The initial call to either version should have the parameters A; ;1;n. I TERATIVE-B INARY-S EARCH.A; ;low;high/ while low high mid D b.low C high/=2c if ==A?mid return mid elseif >A?mid low D mid C1 else high D mid 1 return NIL R ECURSIVE-B INARY-S EARCH.A; ;low;high/ if low>high return NIL mid D b.low C high/=2c if ==A?mid return mid elseif >A?mid return R ECURSIVE-B INARY-S EARCH.A; ;mid C1;high/ else return R ECURSIVE-B INARY-S EARCH.A; ;low;mid 1/ Both procedures terminate the search unsuccessfully when the range is empty(i.e., low>high)and terminate it successfully if the value has been found.Based on the comparison of to the middle element in the searched range,the search continues with the range halved.The recurrence for these procedures is therefore T.n/D T.n=2/C?.1/,whose solution is T.n/D?.lg n/. 算法导论复习资料 一、选择题：第一章的概念、术语。 二、考点分析： 1、复杂度的渐进表示，复杂度分析。 2、正确性证明。 考点：1）正确性分析（冒泡，归并，选择）；2）复杂度分析（渐进表示O，Ｑ，?，替换法证明，先猜想，然后给出递归方程）。 循环不变性的三个性质： 1）初始化：它在循环的第一轮迭代开始之前，应该是正确的； 2）保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也应该保持正确； 3）当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。 插入排序算法： 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 - 1 5 while i > 0 and A[i] > key 6 do A[i + 1] ←A[i] 7 i ←i - 1 8 A[i + 1] ←key 插入排序的正确性证明：课本11页。 归并排序算法：课本17页及19页。 归并排序的正确性分析：课本20页。 3、分治法（基本步骤，复杂度分析）。——许多问题都可以递归求解 考点：快速排序，归并排序，渐进排序，例如：12球里面有一个坏球，怎样用最少的次数找出来。（解：共有24种状态，至少称重3次可以找出不同的球） 不是考点：线性时间选择，最接近点对，斯特拉算法求解。 解：基本步骤： 一、分解：将原问题分解成一系列的子问题； 二、解决：递归地解各子问题。若子问题足够小，则直接求解； 三、合并：将子问题的结果合并成原问题的解。 复杂度分析：分分治算法中的递归式是基于基本模式中的三个步骤的，T(n)为一个规模为n的运行时间，得到递归式 T(n)=Q(1) n<=c T(n)=aT(n/b)+D(n)+C(n) n>c 附加习题：请给出一个运行时间为Q(nlgn)的算法，使之能在给定的一个由n个整数构成的集合S 和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。(完整版)算法导论复习要点
算法导论第二章答案
算法导论第二章第一节答案
算法导论复习要点
算法导论文档
算法导论习题答案
“算法分析与优化”教学大纲
算法导论第四章
算法导论 第三版 第35章 答案 英
《算法导论》CLRS算法C++实现
MIT-算法导论-第二章-读书笔记
麻省理工学院-算法导论
算法导论 课后题答案
算法导论第三版答案
算法导论复习资料
相关主题
文本预览