small-icon.hover

(8/2/2015-2/4/2015)

Este curso está dividido en dos partes en la primera vemos las dos primeros capítulos del libro  (Searching, Sorting) y en la segundo los dos últimos (Graphs, Strings). Cada semana se liberan los videos de las clases, ejercicios múltiple opción para verificar que entendemos como funcionan los algoritmos y un Programming Assignment.

[UPDATE Julio/2015]: El curso se volvió a abrir y estoy aprovechando para rehacer algunas cosas. Volví a hacer Percolation y Randomized Queues and Deques. Estoy terminando Kd-Trees. Esta vez estoy usando Eclipse y escribiendo tests. También estoy tratando de usar git pero en eclipse es bastante feo. Esta vez estoy tratando de implementar los principales algoritmos que se dan en clase: QuickUnionFind, MergeSort, QuickSort, Binary Search Trees, Hash Tables (tratando de mirar el código de clase lo menos posible). También voy a usar mis implementaciones para contestar los ejercicios porque correr los algoritmos a mano es una tortura.

En general me noto un poco mejor al abordar los ejercicios. Siento que aprendí un par de cosas que me permiten mantener el proceso. El problema que sigo teniendo es trato de dedicar un día por semana a un ejercicio, y cuando no logro terminarlo en ese tiempo me empiezo a poner de mal humor.

Me subí un poco tarde porque estaba enganchado haciendo una app en Ruby on Rails, pero estoy tratando de ponerme a tiro.

El año pasado di con este curso de y me pareció que podía ser una buena manera de convertirme en un programador tout courtEsto es lo que escribí en Quora sobre esa experiencia:


Sedgewick claims that:
 
"the course doesn't go into any advanced or tricky Java syntax".

I don't agree. You'll need to understande Generics, Interfaces, 
Iterators, and a few other things to get the assignments done. 
That's pretty interesting stuff, but you'll to learn it. 
But that's fair because it was pretty interesting and sort 
of well explained in the lectures. As for the syntax, 
it's not that hard, after a day or two on CodingBat 
you should be ok.

The biggest problem was configuring an environment. 
That's where I hit a wall. You'll need a Java compiler 
and a console to run the programs from the course. 

O sea, fue un fracaso porque no pude hacer los Programming Assignments en Java. Entonces me compré el libro de Sedgewick de Java y, ya que estaba, el de Algoritmos para irme preparando para la próxima edición del curso.

Los ejercicios no requieren implementar los algoritmos que estudiamos (estan todos disponibles online), sino que plantean un problema que se puede resolver usando los algoritmos vistos en clase.

Semana 1: Introduction to algorithms

Esto es una intro al tema. Hay un módulo describiendo el enfoque de Sedegewick (por que está en contra de la Big-O notation, etc.). Otro módulo es de análisis de algoritmos, donde habla de como estimar el exponente de un algoritmo cuadrático usando la doubling-rule y una regresión log-log. Otro es sobre el uso de memoria en Java.

El cuarto es el primer algoritmo propiamente dicho, es Union-Find, un algoritmo que permite encontrar strong components en una red en tiempo logarítmico. El enfoque es interesante porque va refinando una solución básica poco a poco.

Assignment: Percolation(100 %)

Este es el primer problema del curso, es bastante interesante. EXPLICAR PROBLEMA Y PONER IMAGEN.

Para resolverlo usamos el algoritmo Quick-Union Find, para calcluar los strong components de una matriz de puntos. La solución es interesante porque demuestra un efecto llamado phase transition. El objetivo es estimar que proporción de celdas debe estar abierta para que el agua llegue desde el techo al piso de la matriz.

Para eso hacemos un experimento Monte Carlo en el que abirmos una posición y chequeamos si la matriz percola o no iterativamente hasta que percola. Esto nos permite estimar un “umbral” para la proporción de sitios que debe haber abiertos para que la matriz percole.

Semana 2:  Stacks & queues

Estas son estructuras de datos bastante básicas. Se usan como base para implementar otros algoritmos.

Assignment: Randomized Queues and Deques (98%)

Este problema fue relativamente sencillo.

Una Randomized Queue tiene la API de una Queue normal, pero además permite extraer un ítem al azar. Parece fácil pero los requerimientos de performance para el iterador complicaban un poquito las cosas. Un Deque es como una Queue de la que se pueden sacar items de adelante y de atrás. Relativamente sencillo, pero hay un detalle que nunca pude sacar, y me quedé en 98%.

Semana 3: Sorting Algorithms: Mergesort & Quicksort

Estos algoritmos son de los grandes éxitos de la historia de la computación. La segunda vuelta del curso los voy a intentar implementar. PONER LINK A PUBLIC REPO.

Dificil: Quicksort.

Assignment: Collinear Points (84%)(93.78%)

Acá empecé a decaer. El problema es detectar líneas de cuatro o más puntos en una nube de puntos. Implementamos una solución por fuerza bruta y después un algoritmo basado en ordenar los puntos.

La solución final tenía algunos problemas de performance, y el diseño me quedó bastante desastroso. Creo que esto es lo que más me falta, aprender a planificar los objetos y los métodos que tiene cada uno antes de implementarlos.

En vez de hacer esto, mi forma de trabajo es pensar una posible solución, implementarla y ver que falla. Lo más normal es que la primera solución no sea viable, y creo que debería ser posible anticiparse a esto. Otra cosa que pasa es que la solución no es suficiente, entonces la empezás a emparchar, lo que resulta en implementaciones y APIs espantosas. Esto es lo que me pasó con este problema (y otros tantos…).

Una feature de Java importante para este assignment fue implementar la Interfaz Comparable para los Puntos y las líneas, pero, como decía antes, no me quedó del todo bien.

[Julio] Esta vez levanté un poquito la nota pero no quedé conforme con el código principal. La nota que perdí es por Brute.java, Fast.java pasa todos los tests, pero la lógica del algoritmo debería mejorarse. Descubrí algunos casos límites (cuando los puntos colineales quedan al final). Probablemente lo mejore en estos días.

 

Semana 4: Priority Queues

En este módulo estudiamos las Binary Heaps, el último algoritmo para ordenar (Heapsort) y una estructura de datos super útil: Priority Queue.

DIFICIL:

Sacar 100% en el assignment.

Assignment: 8 Puzzle (70%)(92.07%)

Este problema está en Principles Of Computing de Rice. Es un juego en el que hay que ordenar 15 fichas numeradas del 1 al 15 en una grilla de 16 piezas (una en blanco).

El análisis matemático es interesante. La solución es usar el algoritmo de búsqueda A*, que genera todos los movimientos posibles a partir de una posición inicial y explora todos los escenarios posibles a partir de cada movimiento usando “Best First Search”.

Best first search se sirve de una Priority Queue para “priorizar” los mejores nodos y procesarlos antes que los primeros. Para decidir que nodos son mejores que otros, usamos una herurística (en este caso la suma de las distancias de los bloques a sus posiciones finales).

[Marzo 2015] Creo que la nota que me dieron por este problema es injusta. Mi programa andaba bien con todos los casos salvo uno, que tenía una grilla de 14 * 14. No supe como debugear a mano un caso tan grande así que entregué así.

[Julio 2015] Esta vez me fue mejor, el código es mucho más limpio pero no llegué a 100% porque estoy insertando demasiados nodos en la queue. Este es de los assignments donde más ideas hay para optimizar la performance. Hay una que es obligatoria de implementar, que es no poner el nodo previo en la Queue cuando calculo los vecinos.

Traté de cachear los cálculos de hamming() y manhattan() pero el resultado fue peor. Otra que parece prometedora es representar las tiles como un char[] en vez de un int[][]. También hay que refactorear el código que enqueues los neighbors.

 

Semana 5: Symbol Tables

dificil:

Implementación recursiva de get() e insert() en un BST.

Assignment: KD-Trees (100%)

La primera vez que tomé el curso, el fracaso en el problema 4 me desanimó y no pude juntar el valor para empezar este Assignment. La segunda vez lo hice y salió bastante bien.

Los K-dimensional Trees son árboles binarios en varias dimensiones. En 2 dimensiones, los nodos se pueden usar para almacenar puntos en el plano. Cada nivel del árbol particiona una dimensión, en el caso de ser binarios el root particiona el eje x, los dos hijos del root particionan el eje Y.

Esto permite implementar rápidamente operaciones como encontrar el punto más cercano en una nube de puntos a un punto exterior y encontrar todos los puntos de un conjuntos que caen adentro de un rectángulo.

El único problema que tuve fue algo que era relativamente sencillo pero era totalmente clave para que el resto saliera bien. Pensé que lo tenía bien pero en realidad había dos errores que hicieron que pareciera que andaba bien al dibujar el árbol:

kdtree

Para implementarlos hay que adaptar un BST. El ejercicio requiere implementar las dos operaciones anteriores. Para hacerlas rápido, hay que implementar dos optimizaciones que se pueden poner un tanto complejas.

Fin

Bueno, ahora terminó y tengo una semana libre para empezar la segunda parte (ver mi review de como me fue en la segunda parte acá). En el medio me fui de vacaciones con el libro y aproveché para estudiar algo. Una cosa que aprendí de pasar tiempo con el libro es lo importante de “correr” los algoritmos a mano para entender como funcionan. Los ejemplos del libro están muy bien para hacer eso, de manera que estoy aprendiendo los algoritmos un poco mejor esta vez.

La segunda vez que hice el curso también valió totalmente la pena. No solo porque aprendo más cosas sino porque los programas que hago son mejores. Esto se debe a que al tener más familiaridad con las features de Java es más sencillo implementar las soluciones mas idiomáticas.

También resuelvo los problemas más rápido, aunque es probable que esto se deba a que ya los hice hace unos meses. En todo caso el proceso es más agradable, lo que resulta en mejor aprendizaje.

También estoy más cómodo con las herramientas (que no son las que se recomiendan en el curso). Estoy usando Eclipse, Junit y Git. (Aunque Git me sigue dando problemas). El código que escribí para el curso está repos privados en Bitbucket.

Quedan pendientes los ejercicios. Probablemente los haga programando en vez de a mano.

Otra cosa interesante es escribir los programas que Sedgewick muestra en clase. Si bien esto es más natural en otro estilo de curso, es una actividad que vale bastante la pena.

 

Anuncios