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
oferecido por
Princeton University
Programa - O que você aprenderá com este curso
Semana
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 vídeos (total de (Total 76 mín.) min), 2 leituras, 1 teste
4 videos
A Scientific Approach 16min
Example: Quicksort 30min
Resources 17min
2 leituras
Getting Started10min
Exercises from Lecture 110min
1 exercício prático
Analysis of Algorithms4min
Semana
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 vídeos (total de (Total 71 mín.) min), 1 leitura, 3 testes
5 videos
Computing Values10min
Telescoping15min
Types of Recurrences 12min
Mergesort 18min
Master Theorem 14min
1 leituras
Exercises from Lecture 210min
3 exercícios práticos
Pop Quiz on Telescoping2min
Pop Quiz on the Master Theorem2min
Recurrences4min
Semana
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 vídeos (total de (Total 84 mín.) min), 1 leitura, 1 teste
5 videos
Counting with Generating Functions27min
Catalan Numbers14min
Solving Recurrences18min
Exponential Generating Functions7min
1 leituras
Exercises from Lecture 310min
1 exercício prático
Generating Functions6min
Semana
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 vídeos (total de (Total 83 mín.) min), 1 leitura, 1 teste
4 videos
Standard Scale18min
Manipulating Expansions 19min
Asymptotics of Finite Sums 16min
Bivariate Asymptotics 28min
1 leituras
Exercises from Lecture 410min
1 exercício prático
Asymptotics4min
Instrutores
Robert Sedgewick
William O. Baker *39 Professor of Computer ScienceComputer 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
Quando terei acesso às palestras e às tarefas?
Ao se inscrever para um Certificado, você terá acesso a todos os vídeos, testes e tarefas de programação (se aplicável). Tarefas avaliadas pelos colegas apenas podem ser enviadas e avaliadas após o início da sessão. Caso escolha explorar o curso sem adquiri-lo, talvez você não consiga acessar certas tarefas.
O que recebo ao adquirir o Certificado?
Quando você adquire o Certificado, ganha acesso a todo o material do curso, incluindo avaliações com nota atribuída. Após concluir o curso, seu Certificado eletrônico será adicionado à sua página de Participações e você poderá imprimi-lo ou adicioná-lo ao seu perfil no LinkedIn. Se quiser apenas ler e assistir o conteúdo do curso, você poderá frequentá-lo como ouvinte sem custo.
Mais dúvidas? Visite o Central de Ajuda ao Aprendiz.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
