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.
Анализ алгоритмов
от партнера
Принстонский университет
Программа курса: что вы изучите
Неделя
12 ч. на завершение
Analysis 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 тест
4 видео
A Scientific Approach 16мин
Example: Quicksort 30мин
Resources 17мин
2 материала для самостоятельного изучения
Getting Started10мин
Exercises from Lecture 110мин
1 практическое упражнение
Analysis of Algorithms4мин
Неделя
22 ч. на завершение
Recurrences
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 тестов
5 видео
Computing Values10мин
Telescoping15мин
Types of Recurrences 12мин
Mergesort 18мин
Master Theorem 14мин
1 материал для самостоятельного изучения
Exercises from Lecture 210мин
3 практического упражнения
Pop Quiz on Telescoping2мин
Pop Quiz on the Master Theorem2мин
Recurrences4мин
Неделя
32 ч. на завершение
Generating 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мин
Неделя
42 ч. на завершение
Asymptotics
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мин
4.7
Рецензии: 6Лучшие рецензии
This course is more about mathematic than algorithms, it teaches how to solve tricky combinatorial problems
This is great course if you already done some algorithms courses and want to go deeper.
Преподаватели
Robert Sedgewick
William O. Baker *39 Professor of Computer ScienceComputer Science
О Принстонский университет
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.
Часто задаваемые вопросы
Когда я получу доступ к лекциям и заданиям?
Зарегистрировавшись на сертификацию, вы получите доступ ко всем видео, тестам и заданиям по программированию (если они предусмотрены). Задания по взаимной оценке сокурсниками можно сдавать и проверять только после начала сессии. Если вы проходите курс без оплаты, некоторые задания могут быть недоступны.
Can I earn a certificate in this course?
No. As per Princeton University policy, no certificates, credentials, or reports are awarded in connection with this course.
Остались вопросы? Посетите Центр поддержки учащихся.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2019 Все права защищены.
