Explore
For Enterprise
Join for Free
Log In

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

Overview

Loading...

Algorithmic Toolbox

Universidad de California en San Diego

4.7 (5,218 calificaciones) | 160K estudiantes inscritos

Curso 1 de 6 en Estructuras de datos y algoritmos Programa Especializado

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second). Do you have technical problems? Write to us: coursera@hse.ru

Destrezas que aprenderás

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

Revisiones

4.7 (5,218 calificaciones)

5 stars
3,886 ratings
4 stars
1,057 ratings
3 stars
187 ratings
2 stars
38 ratings
1 star
50 ratings

MM

Sep 29, 2017

good course, I like the fact you can use a lot of languages for you programming exercises, the content is really helpful, I would like to have more indications from the grading system to save time.

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

De la lección

Divide-and-Conquer

In this module you will learn about a powerful algorithmic technique called Divide and Conquer. Based on this technique, you will see how to search huge databases millions of times faster than using naïve linear search. You will even learn that the standard way to multiply numbers (that you learned in the grade school) is far from the being the fastest! We will then apply the divide-and-conquer technique to design two efficient algorithms (merge sort and quick sort) for sorting huge lists, a problem that finds many applications in practice. Finally, we will show that these two algorithms are optimal, that is, no algorithm can sort faster!

Random Pivot13:04

Running Time Analysis (optional)15:32

Equal Elements6:31

Final Remarks8:12

Impartido por:

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

Transcripción

Hello, and welcome to the next lesson in the Divide-and-Conquer model. This lesson is going to be devoted to the quick sort algorithm, which is one of the most efficient and commonly used in practice sorting algorithms. Well, as usual, we start with the overview of this algorithm. The algorithm is comparison based, meaning that it sorts the n given elements by comparing pairs of them. Its running time is also asymptotically n log n, but not in the worst case, as was with the merge sort algorithm, for example, but on the average case. This is because this algorithm is randomized, so it uses random numbers to sort the given n objects. Well, we will explain later in this lesson what this means. Finally, as I said before, this algorithm is very efficient in practice and, at the same time, not so difficult to implement. This is a toy example explaining the main idea of the quick sort algorithm. So given an array, in this case of size 11, let's take its first element. In this case it is 6. And let's do the following. Let's rearrange all the elements in this array such that the element 6 stays in its final position. All the elements that go before it are actually at most 6. And all the elements that go after 6, after this element, are greater than 6. Well, we will show that this can be done by a single scan of the initial array. This is how the resulting array looks like. So once again, 6 stays in its final position. All the elements before it are at most 6. All the elements after it are greater than 6. So we do not need to move 6 anymore. It is already in its final position. So what remains to be done is to sort all the elements that go before 6 and all the elements that go after 6. And this can be done just with two recursive calls to the same algorithm, to the quick sort algorithm. So we do this, and immediately after these two recursive calls, we have a sorted array. Well, in the next video we will explain all the details of this algorithm.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

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.

Coursera

Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government
Para el campus

Comunidad

Estudiantes
Socios
Desarrolladores
Probador beta
Traductores
Blog
Blog de Tecnología

Más

Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados

© 2019 Coursera Inc. Todos los derechos reservados.