Informações sobre o curso
4.8
37 classificações
5 avaliações
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....
Globe

cursos 100% online

Comece imediatamente e aprenda em seu próprio cronograma.
Calendar

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.
Advanced Level

Nível avançado

Clock

Approx. 25 hours to complete

Sugerido: 7 hours/week...
Comment Dots

English

Legendas: English...
Globe

cursos 100% online

Comece imediatamente e aprenda em seu próprio cronograma.
Calendar

Prazos flexíveis

Redefinir os prazos de acordo com sua programação.
Advanced Level

Nível avançado

Clock

Approx. 25 hours to complete

Sugerido: 7 hours/week...
Comment Dots

English

Legendas: English...

Programa - O que você aprenderá com este curso

Week
1
Clock
2 horas para concluir

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....
Reading
4 vídeos (Total de 76 min), 2 leituras, 1 teste
Video4 videos
A Scientific Approach 16min
Example: Quicksort 30min
Resources 17min
Reading2 leituras
Getting Started10min
Exercises from Lecture 110min
Quiz1 exercício prático
Analysis of Algorithms4min
Week
2
Clock
2 horas para concluir

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....
Reading
5 vídeos (Total de 71 min), 1 leitura, 3 testes
Video5 videos
Telescoping15min
Types of Recurrences 12min
Mergesort 18min
Master Theorem 14min
Reading1 leituras
Exercises from Lecture 210min
Quiz3 exercícios práticos
Pop Quiz on Telescoping2min
Pop Quiz on the Master Theorem2min
Recurrences4min
Week
3
Clock
2 horas para concluir

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....
Reading
5 vídeos (Total de 84 min), 1 leitura, 1 teste
Video5 videos
Counting with Generating Functions27min
Catalan Numbers14min
Solving Recurrences18min
Exponential Generating Functions7min
Reading1 leituras
Exercises from Lecture 310min
Quiz1 exercício prático
Generating Functions6min
Week
4
Clock
2 horas para concluir

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....
Reading
4 vídeos (Total de 83 min), 1 leitura, 1 teste
Video4 videos
Manipulating Expansions 19min
Asymptotics of Finite Sums 16min
Bivariate Asymptotics 28min
Reading1 leituras
Exercises from Lecture 410min
Quiz1 exercício prático
Asymptotics4min

Instrutores

Robert Sedgewick

William O. Baker *39 Professor of Computer Science
Computer Science

Sobre 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....

Perguntas Frequentes – FAQ

  • Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.

  • When you purchase a Certificate you get access to all course materials, including graded assignments. Upon completing the course, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.

  • No. As per Princeton University policy, no certificates, credentials, or reports are awarded in connection with this course.

Mais dúvidas? Visite o Central de Ajuda ao Aprendiz.