Este es mi segundo intento con este curso. En la primer iteración hice algunos assignments y vi todos los videos. Roughgarden es espectacular para dar las clases. Las primeras clases son sobre algoritmos divide and conquer y el master method. El tratamiento matemático es fantástico, muy claro (mejor que Sedgewick).

Los assignments son bastante distintos a los de Sedgewick. En general, nos da un dataset y tenemos que implementar alguno de los algoritmos y en base  a eso contestar una pregunta. La ventaja de esto es que no te obliga a usar un lenguaje determinado (en el curso de Sedgewick submitimos código java).

Esto me vino bien para aprender un poco de Javascript.

Esta vez vengo mejor con los assignments, pero todavía no avancé con los quizzes. Acá está el repo del código.

 

Inversions

En este assignment hay que implementar un algoritmo para contar inversiones basado en mergesort.

Quicksort

El desafío de este assignment es comparar distintas estrategias para elegir pivotes para quicksort. La velocidad del algoritmo depende de que tan balanceado sea el split, por lo que las distintas estrategias afectan la velocidad.

El más complicado es median of three, que implica tomar el primero, el del medio y el segundo. Después tomamos el mediano de estos tres items, y usamos ese como pivot.

El objetivo es contar la cantidad de comparaciones que hace el algoritmo con las rutinas alternativas.

Kargers contraction algorithm

Después de terminar me di cuenta que ya había hecho este ejercicio. Mi solución functiona pero es tremendamente lenta. (Me toma aproximadamente 10 horas calcular la respuesta).

Dijkstra’s shortest paths

Este problema es muy simple. Nos dan un archivo con un grafo con Directed Edges de 200 nodos, y tenemos que encontrar los Shortest Paths entre el nodo 1 y un conjunto de 10 nodos. Para hacerlo usé una IndexMinPQ (basada en esta implementación de Sedgewick y Wayne).

Una vez que tenemos esto, el algoritmo es bastante sencillo de implementar. De todoas formas repasé un par de veces el trace que aparece en el libro de Sedgewick y es bastante complejo.

Para entender un algoritmo es imprescindible ver como funciona sobre datos reales, la metáfora de “leer código” te puede confundir en esto. EL código de este es tremendamente sencillo, pero implementarlo en tu cabeza puede ser difícil.

Esto también puede ser debido al uso de la PQ, porque al repasar el algoritmo a mano estamos corriendo en nuestras cabezas el código de la PQ más el de Dijkstra…

 

 

 Otras reviews

Acá hay otras reviews de este curso:

 

 

Anuncios