下载文档原格式
算法导论课程作业答案Introduction to AlgorithmsMassachusetts Institute of Technology 6.046J/18.410J Singapore-MIT Alliance SMA5503 Professors Erik Demaine,Lee Wee Sun,and Charles E.Leiserson Handout10Diagnostic Test SolutionsProblem1Consider the following pseudocode:R OUTINE(n)1if n=12then return13else return n+R OUTINE(n?1)(a)Give a one-sentence description of what R OUTINE(n)does.(Remember,don’t guess.) Solution:The routine gives the sum from1to n.(b)Give a precondition for the routine to work correctly.Solution:The value n must be greater than0;otherwise,the routine loops forever.(c)Give a one-sentence description of a faster implementation of the same routine. Solution:Return the value n(n+1)/2.Problem2Give a short(1–2-sentence)description of each of the following data structures:(a)FIFO queueSolution:A dynamic set where the element removed is always the one that has been in the set for the longest time.(b)Priority queueSolution:A dynamic set where each element has anassociated priority value.The element removed is the element with the highest(or lowest)priority.(c)Hash tableSolution:A dynamic set where the location of an element is computed using a function of the ele ment’s key.Problem3UsingΘ-notation,describe the worst-case running time of the best algorithm that you know for each of the following:(a)Finding an element in a sorted array.Solution:Θ(log n)(b)Finding an element in a sorted linked-list.Solution:Θ(n)(c)Inserting an element in a sorted array,once the position is found.Solution:Θ(n)(d)Inserting an element in a sorted linked-list,once the position is found.Solution:Θ(1)Problem4Describe an algorithm that locates the?rst occurrence of the largest element in a?nite list of integers,where the integers are not necessarily distinct.What is the worst-case running time of your algorithm?Solution:Idea is as follows:go through list,keeping track of the largest element found so far and its index.Update whenever necessary.Running time isΘ(n).Problem5How does the height h of a balanced binary search tree relate to the number of nodes n in the tree? Solution:h=O(lg n) Problem 6Does an undirected graph with 5vertices,each of degree 3,exist?If so,draw such a graph.If not,explain why no such graph exists.Solution:No such graph exists by the Handshaking Lemma.Every edge adds 2to the sum of the degrees.Consequently,the sum of the degrees must be even.Problem 7It is known that if a solution to Problem A exists,then a solution to Problem B exists also.(a)Professor Goldbach has just produced a 1,000-page proof that Problem A is unsolvable.If his proof turns out to be valid,can we conclude that Problem B is also unsolvable?Answer yes or no (or don’t know).Solution:No(b)Professor Wiles has just produced a 10,000-page proof that Problem B is unsolvable.If the proof turns out to be valid,can we conclude that problem A is unsolvable as well?Answer yes or no (or don’t know).Solution:YesProblem 8Consider the following statement:If 5points are placed anywhere on or inside a unit square,then there must exist two that are no more than √2/2units apart.Here are two attempts to prove this statement.Proof (a):Place 4of the points on the vertices of the square;that way they are maximally sepa-rated from one another.The 5th point must then lie within √2/2units of one of the other points,since the furthest from the corners it can be is the center,which is exactly √2/2units fromeach of the four corners.Proof (b):Partition the square into 4squares,each with a side of 1/2unit.If any two points areon or inside one of these smaller squares,the distance between these two points will be at most √2/2units.Since there are 5points and only 4squares,at least two points must fall on or inside one of the smaller squares,giving a set of points that are no more than √2/2apart.Which of the proofs are correct:(a),(b),both,or neither (or don’t know)?Solution:(b)onlyProblem9Give an inductive proof of the following statement:For every natural number n>3,we have n!>2n.Solution:Base case:True for n=4.Inductive step:Assume n!>2n.Then,multiplying both sides by(n+1),we get(n+1)n!> (n+1)2n>2?2n=2n+1.Problem10We want to line up6out of10children.Which of the following expresses the number of possible line-ups?(Circle the right answer.)(a)10!/6!(b)10!/4!(c) 106(d) 104 ·6!(e)None of the above(f)Don’t knowSolution:(b),(d)are both correctProblem11A deck of52cards is shuf?ed thoroughly.What is the probability that the4aces are all next to each other?(Circle theright answer.)(a)4!49!/52!(b)1/52!(c)4!/52!(d)4!48!/52!(e)None of the above(f)Don’t knowSolution:(a)Problem12The weather forecaster says that the probability of rain on Saturday is25%and that the probability of rain on Sunday is25%.Consider the following statement:The probability of rain during the weekend is50%.Which of the following best describes the validity of this statement?(a)If the two events(rain on Sat/rain on Sun)are independent,then we can add up the twoprobabilities,and the statement is true.Without independence,we can’t tell.(b)True,whether the two events are independent or not.(c)If the events are independent,the statement is false,because the the probability of no rainduring the weekend is9/16.If they are not independent,we can’t tell.(d)False,no matter what.(e)None of the above.(f)Don’t know.Solution:(c)Problem13A player throws darts at a target.On each trial,independentlyof the other trials,he hits the bull’s-eye with probability1/4.How many times should he throw so that his probability is75%of hitting the bull’s-eye at least once?(a)3(b)4(c)5(d)75%can’t be achieved.(e)Don’t know.Solution:(c),assuming that we want the probability to be≥0.75,not necessarily exactly0.75.Problem14Let X be an indicator random variable.Which of the following statements are true?(Circle all that apply.)(a)Pr{X=0}=Pr{X=1}=1/2(b)Pr{X=1}=E[X](c)E[X]=E[X2](d)E[X]=(E[X])2Solution:(b)and(c)only。
研究生计算机科学教案：算法设计与分析1. 引言本课程教案旨在帮助研究生计算机科学专业的学生深入理解算法设计与分析的基本原理和方法。
通过系统学习和实践，学生将能够掌握常见的算法设计技巧，理解并应用各种算法的时间复杂度和空间复杂度分析方法。
2. 教学目标本教案旨在让学生达到以下几个方面的教学目标：•理解常见的算法设计技巧，包括递归、贪心、动态规划等；•掌握各种排序、查找和图算法的设计原理及实现；•能够使用大O符号来评估和比较不同算法的时间复杂度；•能够进行基础数据结构（如栈、队列、链表等）及其应用场景的分析；•能够运用所学知识解决实际问题，并进行正确性和效率上的评估。
3. 教学内容3.1 算法设计基础•递归与分治策略•贪心策略•动态规划策略3.2 排序和查找算法•冒泡排序•快速排序•归并排序•二分查找3.3 图算法设计与分析•深度优先搜索（DFS）•广度优先搜索（BFS）•最短路径算法：Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法•最小生成树算法：Prim算法、Kruskal算法3.4 大O符号和时间复杂度分析•时间复杂度的定义与计算方法•常见算法时间复杂度的比较和分析•最好情况、最坏情况和平均情况下的时间复杂度4. 教学方法与评估方式本课程将采用以下教学方法：1.理论讲解：通过教师授课、案例演示等方式，介绍各种算法的设计思想和实现原理。
2.实践练习：通过编写程序，解决实际问题，加深对所学知识的理解和应用能力。
3.小组讨论：学生自主组成小组，共同研究和探讨课程中的难点问题，并提交一份小组报告。
4.课堂互动：教师引导学生进行课堂互动，提问和回答问题，加强学生对知识的理解和记忆。
评估方式包括：•平时作业：包括理论题目、编程练习和小组讨论报告。
•期中考试：笔试形式，测试学生对算法设计与分析原理的掌握程度。
•期末项目：要求学生编写一个程序解决一个实际问题，并进行正确性和效率上的评估。
Introduction to Algorithms第三版教学设计一、课程概要1.1 课程名称本课程名称为Introduction to Algorithms，是计算机科学专业必修课程。
1.2 学时安排本课程总共为72学时，每周3学时，共计24周。
1.3 教材《算法导论(原书第3版)》（英文版）（Introduction to Algorithms, Third Edition）。
1.4 教学目的本课程旨在使学生掌握算法与数据结构的基本概念、常用算法设计技巧和分析方法，并培养学生独立思考和解决问题的能力。
1.5 先修课程本课程的先修课程包括数据结构、离散数学、算法分析与设计等。
1.6 课程内容简介本课程包括以下内容：•算法基础知识•分治算法和递归•动态规划•贪心算法•图论算法•字符串匹配•NP完全性理论二、课程教学设计2.1 教学方法本课程采用理论讲授、实验操作、课堂讨论等多种教学方法相结合的方式，重视学生自主学习和动手实践的能力培养。
2.2 教学内容和教学进度本课程的教学内容和教学进度如下：第一讲：算法基础知识讲授主要内容包括算法的概念、算法的正确性和复杂度分析。
第二讲：分治算法和递归讲授主要内容包括分治算法的适用场景、递归的概念和应用。
第三讲：动态规划讲授主要内容包括动态规划的基本思想、常用动态规划算法和实践应用。
第四讲：贪心算法讲授主要内容包括贪心算法的基本思想、贪心算法设计和分析方法。
第五讲：图论算法讲授主要内容包括最短路径算法、最小生成树算法、网络流算法等。
第六讲：字符串匹配讲授主要内容包括朴素算法、KMP算法、Boyer-Moore算法等字符串匹配算法。
第七讲：NP完全性讲授主要内容包括P和NP问题的概念、NP完全性理论、NP问题求解方法等。
2.3 课堂互动与实践本课程还将开展相关实践项目，包括算法设计实验、算法实现与优化、算法竞赛和创新项目等，以培养学生动手实践和解决实际问题的能力。
数据结构经典书籍摘要：一、数据结构的重要性二、数据结构的经典书籍介绍1.《数据结构与算法分析》2.《大话数据结构》3.《数据结构与算法》4.《算法导论》5.《数据结构与算法之美》三、如何选择适合自己的数据结构书籍四、结论正文：数据结构是计算机科学中至关重要的一个领域，掌握数据结构有助于编写高效、可读和可维护的代码。
在众多数据结构书籍中，有几本被广泛认为是经典之作。
本文将介绍其中的五本，并讨论如何选择适合自己的数据结构书籍。
1.《数据结构与算法分析》(Data Structures and Algorithm Analysis in Java)作者：Mark Allen Weiss这本书以Java 语言为例，详细讲述了数据结构和算法的基本概念、原理和实现。
书中包含大量实例和习题，适合初学者入门。
2.《大话数据结构》作者：程云本书采用轻松幽默的语言和丰富的图解，讲解了数据结构的基本原理和常用算法。
内容通俗易懂，适合编程初学者。
3.《数据结构与算法》(Data Structures and Algorithms)作者：Alfred V.Aho, John E.Hopcroft, and Jeffrey D.Ullman这本书是数据结构和算法的经典教材，详细介绍了各种数据结构及其操作，以及排序、查找等基本算法。
内容较为深入，适合已经掌握基本编程技能的读者。
4.《算法导论》(Introduction to Algorithms)作者：Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, and Clifford Stein本书全面讲述了算法设计与分析的基本概念，涵盖了许多经典算法和数据结构。
书中包含大量实例和习题，适合对算法有一定了解的读者深入学习。
5.《数据结构与算法之美》(The Art of Computer Programming, Volume 1: Fundamental Algorithms)作者：Donald E.Knuth本书是计算机编程艺术的卷一，讲述了计算机科学的基本算法。
有关于计算机科学与技术专业的书籍English Answer：1. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: This classic textbook provides a comprehensive introduction to the fundamental algorithms used in computer science. It covers topics such as sorting, searching, dynamic programming, and graph algorithms.2. The Art of Computer Programming by Donald E. Knuth: This multi-volume series is considered a masterpiece of computer science literature. It covers a wide range of topics, including algorithms, data structures, and programming techniques.3. Computer Architecture: A Quantitative Approach by John L. Hennessy and David A. Patterson: This textbook provides a thorough introduction to computer architecture, covering topics such as processor design, memory systems,and I/O devices.4. Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau: This textbook provides a concise and accessible introduction to operating systems, covering topics such as processes, threads, memory management, and file systems.5. Computer Networks: A Top-Down Approach by James F. Kurose and Keith W. Ross: This textbook provides a comprehensive introduction to computer networks, covering topics such as network protocols, routing algorithms, and network security.6. Database Systems: The Complete Book by HectorGarcia-Molina, Jeffrey D. Ullman, and Jennifer Widom: This textbook provides a comprehensive introduction to database systems, covering topics such as data models, query processing, and transaction management.7. Programming Language Concepts by Robert W. Sebesta: This textbook provides a comprehensive introduction toprogramming language concepts, covering topics such as syntax, semantics, and programming paradigms.8. Software Engineering: A Practitioner's Approach by Roger S. Pressman: This textbook provides a practical introduction to software engineering, covering topics such as software development process models, software design principles, and software testing techniques.9. Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig: This textbook provides a comprehensive introduction to artificial intelligence, covering topics such as search algorithms, machine learning, and natural language processing.10. Machine Learning by Tom M. Mitchell: This textbook provides a comprehensive introduction to machine learning, covering topics such as supervised learning, unsupervised learning, and reinforcement learning.Chinese Answer：1. 算法导论（Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein），这本经典教材全面介绍了计算机科学中使用的基本算法。
