Coursera
Explorar
  • Explorar
  • Buscar
  • For Enterprise
  • Inicia Sesión
  • Regístrarse

Analysis of Algorithms

Un vistazoProgramaPreguntas FrecuentesCreadoresCalificaciones y revisiones
InicioCiencias de la ComputaciónAlgoritmos

Analysis of Algorithms

Universidad de Princeton

Acerca de este curso: 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.


Creada por:  Universidad de Princeton
Universidad de Princeton

  • Robert Sedgewick

    Enseñado por:  Robert Sedgewick, William O. Baker *39 Professor of Computer Science

    Computer Science
NivelAdvanced
Idioma
English
Cómo aprobarAprueba todas las tareas calificadas para completar el curso.
Calificaciones del usuario
4.9 estrellas
Calificación promedio del usuario 4.9Ve los que los estudiantes dijeron
Programa
SEMANA 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 videos, 2 readings
  1. Reading: Getting Started
  2. Vídeo: History and Motivation
  3. Vídeo: A Scientific Approach
  4. Vídeo: Example: Quicksort
  5. Vídeo: Resources
  6. Reading: Exercises from Lecture 1
  7. Discussion Prompt: Exercises from Lecture 1
Calificado: Analysis of Algorithms
SEMANA 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 videos, 1 reading, 2 practice quizzes
  1. Vídeo: Computing Values
  2. Vídeo: Telescoping
  3. Practice Quiz: Pop Quiz on Telescoping
  4. Vídeo: Types of Recurrences
  5. Vídeo: Mergesort
  6. Vídeo: Master Theorem
  7. Practice Quiz: Pop Quiz on the Master Theorem
  8. Reading: Exercises from Lecture 2
  9. Discussion Prompt: Exercises from Lecture 2
Calificado: Recurrences
SEMANA 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 videos, 1 reading
  1. Vídeo: Ordinary Generating Functions
  2. Vídeo: Counting with Generating Functions
  3. Vídeo: Catalan Numbers
  4. Vídeo: Solving Recurrences
  5. Vídeo: Exponential Generating Functions
  6. Reading: Exercises from Lecture 3
  7. Discussion Prompt: Exercises from Lecture 3
Calificado: Generating Functions
SEMANA 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 videos, 1 reading
  1. Vídeo: Standard Scale
  2. Vídeo: Manipulating Expansions
  3. Vídeo: Asymptotics of Finite Sums
  4. Vídeo: Bivariate Asymptotics
  5. Reading: Exercises from Lecture 4
  6. Discussion Prompt: Exercises from Lecture 4
Calificado: Asymptotics
SEMANA 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 videos, 2 readings
  1. Vídeo: The Symbolic Method
  2. Vídeo: Labelled Objects
  3. Vídeo: Coefficient Asymptotics
  4. Reading: Errata
  5. Vídeo: Perspective
  6. Reading: Exercises from Lecture 5
  7. Discussion Prompt: Exercises from Lecture 5
Calificado: Analytic Combinatorics
SEMANA 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 videos, 1 reading
  1. Vídeo: Trees and Forests
  2. Vídeo: Binary Search Trees
  3. Vídeo: Path Length
  4. Vídeo: Other Types of Trees
  5. Reading: Exercises from Lecture 6
  6. Discussion Prompt: Exercises from Lecture 6
Calificado: Trees
SEMANA 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 videos, 1 reading
  1. Vídeo: Basics
  2. Vídeo: Sets of Cycles
  3. Vídeo: Left-Right-Minima
  4. Vídeo: Other Parameters
  5. Vídeo: BGFs and Distributions
  6. Reading: Exercises from Lecture 7
  7. Discussion Prompt: Exercises from Lecture 7
Calificado: Permutations
SEMANA 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 videos, 1 reading
  1. Vídeo: Bitstrings with Restrictions
  2. Vídeo: Languages
  3. Vídeo: Tries
  4. Vídeo: Trie Parameters
  5. Vídeo: Exercises
  6. Reading: Exercises from Lecture 8
  7. Discussion Prompt: Exercises from Lecture 8
Calificado: Strings and Tries
SEMANA 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 videos, 1 reading
  1. Vídeo: Words
  2. Vídeo: Birthday Problem
  3. Vídeo: Coupon Collector Problem
  4. Vídeo: Hash Tables
  5. Vídeo: Mappings
  6. Vídeo: Exercises
  7. Reading: Exercises from Lecture 9
  8. Discussion Prompt: Exercises from Lecture 9
Calificado: Strings and Words

Preguntas Frecuentes
Cómo funciona
Coursework
Coursework

Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.

Help from Your Peers
Help from Your Peers

Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.

Creadores
Universidad de Princeton
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.
Calificaciones y revisiones
Calificado 4.9 de 5 17 calificaciones
Hafidz Jazuli Luthfi

This is great course if you already done some algorithms courses and want to go deeper.



También te podría gustar
Stanford University
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
1 course
Stanford University
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
Ver curso
University of California, San Diego, National Research University Higher School of Economics
Algorithms on Graphs
1 course
University of California, San Diego, National Research University Higher School of Economics
Algorithms on Graphs
Ver curso
University of California, San Diego, National Research University Higher School of Economics
Algorithms on Strings
1 course
University of California, San Diego, National Research University Higher School of Economics
Algorithms on Strings
Ver curso
Stanford University
Graph Search, Shortest Paths, and Data Structures
1 course
Stanford University
Graph Search, Shortest Paths, and Data Structures
Ver curso
Stanford University
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
1 course
Stanford University
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
Ver curso
Coursera
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
Descargar en la App StoreConsíguelo en Google Play
  • Coursera
  • Acerca de
  • Liderazgo
  • Empleo
  • Catálogo
  • Certificados
  • Grados
  • Para negocios
  • For Government
  • Comunidad
  • instituciones
  • Mentores
  • Traductores
  • Desarrolladores
  • Probador beta
  • Conectar
  • Blog
  • Facebook
  • LinkedIn
  • Twitter
  • Google+
  • Blog de Tecnología
  • Más
  • Términos
  • Privacidad
  • Ayuda
  • Accesibilidad
  • Prensa
  • Contacto
  • Directorio
  • Afiliados