Об этом курсе: 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.
Автор: Princeton University
Преподаватели: Robert Sedgewick, William O. Baker *39 Professor of Computer Science
Computer Science
| Уровень | Продвинутые функции |
| Язык | English |
| Как пройти курс | Чтобы пройти курс, выполните все оцениваемые задания. |
| Оценки пользователей |
Программа курса
НЕДЕЛЯ 1
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 видео, 2 материала для самостоятельного изучения
- Reading: Getting Started
- Видео: A Scientific Approach
- Видео: Example: Quicksort
- Видео: Resources
- Reading: Exercises from Lecture 1
- Discussion Prompt: Exercises from Lecture 1
Оцениваемый: Analysis of Algorithms
НЕДЕЛЯ 2
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 видео, 1 материал для самостоятельного изучения, 2 тренировочных теста
- Видео: Telescoping
- Practice Quiz: Pop Quiz on Telescoping
- Видео: Types of Recurrences
- Видео: Mergesort
- Видео: Master Theorem
- Practice Quiz: Pop Quiz on the Master Theorem
- Reading: Exercises from Lecture 2
- Discussion Prompt: Exercises from Lecture 2
Оцениваемый: Recurrences
НЕДЕЛЯ 3
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 видео, 1 материал для самостоятельного изучения
- Видео: Counting with Generating Functions
- Видео: Catalan Numbers
- Видео: Solving Recurrences
- Видео: Exponential Generating Functions
- Reading: Exercises from Lecture 3
- Discussion Prompt: Exercises from Lecture 3
Оцениваемый: Generating Functions
НЕДЕЛЯ 4
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 видео, 1 материал для самостоятельного изучения
- Видео: Manipulating Expansions
- Видео: Asymptotics of Finite Sums
- Видео: Bivariate Asymptotics
- Reading: Exercises from Lecture 4
- Discussion Prompt: Exercises from Lecture 4
Оцениваемый: Asymptotics
НЕДЕЛЯ 5
Analytic Combinatorics
Analytic Combinatorics. With a basic knowledge of recurrences, generating functions, and asymptotics, you are ready to learn and appreciate the basic features of analytic combinatorics, a systematic approach that avoids much of the detail of the classical methods that we have been considering. We introduce unlabeled and labelled combinatorial classes and motivate our basic approach to studying them, with numerous examples.
4 видео, 2 материала для самостоятельного изучения
- Видео: Labelled Objects
- Видео: Coefficient Asymptotics
- Reading: Errata
- Видео: Perspective
- Reading: Exercises from Lecture 5
- Discussion Prompt: Exercises from Lecture 5
Оцениваемый: Analytic Combinatorics
НЕДЕЛЯ 6
Trees
The quintessential recursive structure, trees of various sorts are ubiquitous in scientific enquiry, and they arise explicitly in countless computing applications. You can find broad coverage in the textbook, but the lecture focuses on the use of analytic combinatorics to enumerate various types of trees and study parameters.
4 видео, 1 материал для самостоятельного изучения
- Видео: Binary Search Trees
- Видео: Path Length
- Видео: Other Types of Trees
- Reading: Exercises from Lecture 6
- Discussion Prompt: Exercises from Lecture 6
Оцениваемый: Trees
НЕДЕЛЯ 7
Permutations
The study of sorting algorithms is the study of properties of permutations. We introduce analytic-combinatoric approaches to studying permutations in the context of this relationship.
5 видео, 1 материал для самостоятельного изучения
- Видео: Sets of Cycles
- Видео: Left-Right-Minima
- Видео: Other Parameters
- Видео: BGFs and Distributions
- Reading: Exercises from Lecture 7
- Discussion Prompt: Exercises from Lecture 7
Оцениваемый: Permutations
НЕДЕЛЯ 8
Strings and Tries
From DNA sequences to web indices, strings (sequences of characters) are ubiquitous in modern computing applications, so we use analytic combinatorics to study their basic properties and then introduce the trie, an essential and fundamental structure not found in classical combinatorics.
5 видео, 1 материал для самостоятельного изучения
- Видео: Languages
- Видео: Tries
- Видео: Trie Parameters
- Видео: Exercises
- Reading: Exercises from Lecture 8
- Discussion Prompt: Exercises from Lecture 8
Оцениваемый: Strings and Tries
НЕДЕЛЯ 9
Words and Mappings
We view strings as sets of characters or as functions from [1..N] to [1..M] to study classical occupancy problems and their application to fundamental hashing algorithms. Functions from [1..N] to [1..N] are mappings, which have an interesting and intricate structure that we can study with analytic combinatorics.
6 видео, 1 материал для самостоятельного изучения
- Видео: Birthday Problem
- Видео: Coupon Collector Problem
- Видео: Hash Tables
- Видео: Mappings
- Видео: Exercises
- Reading: Exercises from Lecture 9
- Discussion Prompt: Exercises from Lecture 9
Оцениваемый: Strings and Words
Часто задаваемые вопросы
Как это работает
Coursework
Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.
Help from Your Peers
Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.
Авторы
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.
Рейтинги и отзывы
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.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
IF
This course offers an extensive coverage of mathematical material like tools and techniques, putting special emphasis on simple principles and never losing its focus on the general perspective of the topic.
Developing insight on analytic functions together with combinatorics and the practical applications of theory into code gives a significant advantage over using naive approaches.
A special appreciation to Prof. Sedgewick's endless efforts for disseminating mathematical knowledge among programmers, over this platform and even outside!
Thank you very much.