Esta es la segunda parte del curso de Sedgewick. Esta es mi review de la primera parte. La segunda parte del curso se mete con algoritmos para procesar grafos y texto.

Sedgewick no es de esos profesores que hacen que todo parezca fácil. Ya metí bastantes horas con el libro, vi varias veces los videos, y todavía no me siento para nada cómodo con estos temas. El libro es bastante grande y tiene muchos ejercicios que no tengo ni idea de como encarar, miles de ejemplos interesantes que no pude ver con detalle.

Una cosa que aprendí mirando estos cursos es que a veces es importante cambiar las formas de estudio, y para estudiar algoritmos hay muchas formas de estudio: programar los assignments, analizar los ejemplos de código del libro, estudiar las demostraciones, correr ejemplos de los algoritmos a mano, etc.

Al principio las preguntas múltiple opción no me gustaban pero aprendí que es importante hacerlas. En general implican correr los algoritmos a mano y son buenos ejercicios para entenderlos.

Por otro lado estan los Programming Assignments. En general me parecen bastante difíciles, siempre me queda algo para corregir y nunca llegué a sacarme 100%. Ni hablar de instrumentar las optimizaciones que se sugieren en los foros.

Básicamente mis programas tienen dos problemas: mal diseño de los objetos y métodos y/o mala performance. Supongo que para ser la primera vez que los hago no están tan mal. En una segunda iteración del curso podría tratar de mejorarlos. El problema es que en general me tengo que dar por vencido porque no tengo más tiempo para seguir el ritmo del curso.

Semana 1: Undirected Graphs

Graph API: Un montón de código sencillo para procesar grafos. Breadth First Search y Depth First Search son dos formas de recorrer un grafo, son la base de los algoritmos que vienen después.

Assignment: WordNet(88.18 %) (91.89%)

En este ejercicio nos dan un Directed Edge Graph de palabras. Los edges representan relaciones tipo “es un”. Por ejemplo, hay un edge que va de pelícano a pájaro porque un pelícano es un pájaro.

Lo que hay que hacer es parsear el grafo y armar una clase para encontrar el ancestro más cercano de dos palabras. Por ejemplo, el ancestro de pinguino y pelícano es ave. Para esto hay que diseñar un algoritmo que funcione.

Después usamos este algoritmo para detectar los outcasts en una lista de palabras. Por ejemplo, en la lista: { tenedor, cuchara, cuchillo, piedra}, El outlier es piedra. Para detectarlo calculamos la distancia de cada palabra al resto y las sumamos. La que tenga una suma de distancias al resto máxima es el outcast.

[Edit Abril 2016] Para esta iteración del curso no me acordaba como había solucionado esto la vez pasada, así que empecé de cero. Mi approach fue ir recorriendo los ancestros de la fuente tirando Breadth First Searches desde cada nodo. Si bien esto funcionó bien para nodos individuales, no veo como generalizarlo para colecciones de nodos.

Así que recurrí a la solución anterior (no tenía la menor idea de cómo había resuelto esto la vez pasada). La solución es bastante elegante, hace un BFS desde la fuente y otra desde el destino, y después itera por todos los nodos para encontrar la mejor. Creo que esta iteración podría optimizarse.

Todo el resto del ejercicio es bastante sencillo. Lo único complicado es parsear los datos correctamente. Al principio parecía sencillo y lo hice a pulmón y me entreveré. Entonces empecé de nuevo escribiendo tests y quedó bien.

La clase Outcast se beneficiaría de un refactor (en el método outcast). Lo que hace es crear una array de dos dimensiones que guarda las distancias entre cada par de nouns que le pasan a la función. Después suma por columna, calcula el índice máximo y devuelve el noun correspondiente para hallar el que tiene una suma de distancias mayor al resto. Esto habría que refactorearlo, voy a tratar de hacerlo un día que esté aburrido.

 

Semana 2: Directed Graphs, Edge Weighted Graphs, Minimum Spanning Trees

Ahora los edges tienen direcciones. BFS y DFS son en realidad pensados para recorrer directed graphs, en un undirected graph toman cada edge como uno que va y otro que viene.

 

Assignment: Seam Carving (75%)(93.7%)

En este ejercico implementamos un programa que reduce el tamaño de una imagen teniendo en cuenta el contenido. Para esto, calculamos cuales son las partes de la imágen “menos importantes” y las vamos eliminando. Cada pixel tiene un valor asociado que mide su importancia. Si es muy diferente a los pixeles que lo rodena es importante, pero si es igual lo podemos borrar sin precuparnos mucho por la información perdida.

El algoritmo consiste en encontrar un hilo de  pixeles “poco importantes” que va desde el borde superior al borde inferior de la imagen. Este hilo se encuentra resolviendo un problema de Shortest Path. Luego copiamos la imágen sin esos pixels, et voilá! la imágen tiene una columna menos.

Para implementar el algoritmo armé una class (Grid) que es facilita trabajar con las coordenadas de los colores de las imágenes. Después hay un método (relax), que calcula el camino más corto entre un pixel imaginario arriba de la imágen y cada pixel en la imágen.

 

Semana 3: Min-Cut/Max-Flow

Acá la matemática se pone complicada. Hay algunas demostraciones de teoremas referidos al problema min-cut max-flow.

Assignment: BASEBALL ELIMINATION (87%)

En este ejercicio, el objetivo es determinar que equipos no tienen chance de ganar un campeonato sabiendo cuantos partidos lleva ganados, y cuantos le quedan contra cada equipo. Obviamente, si hay un equipo que ganó mas partidos que los que ganó otro más los que le restan por jugar, este equipo estará eliminado.

Pero hay una condición más complicada, que depende de contra quién son los partidos que le restan a los otros equipos.

                w[i] l[i] r[i]        g[i][j]
i  team         wins loss left   Atl Phi NY  Mon
------------------------------------------------
0  Atlanta       83   71    8     -   1   6   1
1  Philadelphia  80   79    3     1   -   0   2
2  New York      78   78    6     6   0   -   0
3  Montreal      77   82    3     1   2   0   -

En este caso, Atlanta no puede salir campéon. Este problema se puede reducir a uno de Max-Flow en una Flow Network determinada. Tengo que reconocer que no entiendo bien el algoritmo.

Sin embargo, armé un programa que lee los inputs, y después simplemente uso el código del libro para resolver el problema con Ford Fulkerson. Suficiente para llegar a una buena nota, pero debería entender mejor el problema.

Semana 4: Raddix sorts

ASSIGNMENT: Boggle
Para este problema tenemos hacer un programa que juega al Boggle. Para eso, armamos un Trie customizado.

Semana 4: Minumum spanning trees

ASSIGNMENT: Burrows-Wheeler

Anuncios