This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings.
All the features of this course are available for free. It does not offer a certificate upon completion.
Analysis of Algorithms
提供方
Princeton University
教学大纲 - 您将从这门课程中学到什么
周
1Analysis of Algorithms
We begin by considering historical context and motivation for the scientific study of algorithm performance. Then we consider a classic example that illustrates the key ingredients of the process: the analysis of Quicksort. The lecture concludes with a discussion of some resources that you might find useful during this course.
4 个视频 （总计 76 分钟）, 2 个阅读材料, 1 个测验
2 个阅读材料
Getting Started10分钟
Exercises from Lecture 110分钟
1 个练习
Analysis of Algorithms4分钟
周
2Recurrences
We begin this lecture with an overview of recurrence relations, which provides us with a direct mathematical model for the analysis of algorithms. We finish by examining the fascinating oscillatory behavior of the divide-and-conquer recurrence corresponding to the mergesort algorithm and the general "master theorem" for related recurrences.
5 个视频 （总计 71 分钟）, 1 个阅读材料, 3 个测验
1 个阅读材料
Exercises from Lecture 210分钟
3 个练习
Pop Quiz on Telescoping2分钟
Pop Quiz on the Master Theorem2分钟
Recurrences4分钟
周
3Generating Functions
Since the 17th century, scientists have been using generating functions to solve recurrences, so we continue with an overview of generating functions, emphasizing their utility in solving problems like counting the number of binary trees with N nodes.
5 个视频 （总计 84 分钟）, 1 个阅读材料, 1 个测验
5 个视频
Counting with Generating Functions27分钟
Catalan Numbers14分钟
Solving Recurrences18分钟
Exponential Generating Functions7分钟
1 个阅读材料
Exercises from Lecture 310分钟
1 个练习
Generating Functions6分钟
周
4Asymptotics
Exact answers are often cumbersome, so we next consider a scientific approach to developing approximate answers that, again, mathematicians and scientists have used for centuries.
4 个视频 （总计 83 分钟）, 1 个阅读材料, 1 个测验
4 个视频
Standard Scale18分钟
Manipulating Expansions 19分钟
Asymptotics of Finite Sums 16分钟
Bivariate Asymptotics 28分钟
1 个阅读材料
Exercises from Lecture 410分钟
1 个练习
Asymptotics4分钟
讲师
Robert Sedgewick
William O. Baker *39 Professor of Computer ScienceComputer Science
关于 Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. It is one of the eight universities of the Ivy League, and one of the nine Colonial Colleges founded before the American Revolution.
常见问题
我什么时候能够访问课程视频和作业？
注册以便获得证书后，您将有权访问所有视频、测验和编程作业（如果适用）。只有在您的班次开课之后，才可以提交和审阅同学互评作业。如果您选择在不购买的情况下浏览课程，可能无法访问某些作业。
我购买证书后会得到什么？
您购买证书后，将有权访问所有课程材料，包括评分作业。完成课程后，您的电子课程证书将添加到您的成就页中，您可以通过该页打印您的课程证书或将其添加到您的领英档案中。如果您只想阅读和查看课程内容，可以免费旁听课程。
还有其他问题吗？请访问 学生帮助中心。
