Design and Analysis of Algorithms

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:

 

 

Programming Languages Part B + C- Dan Grossman (2016)

Esta es la parte B y C del curso comentado acá. En esta parte usamos Racket, un dialecto de Lisp (para la parte B) y Ruby para la parte C.

Racket es un lenguaje funcional y dinámico (a diferencia de ML que es funcional pero estático). Ruby es orientado a objetos y dinámico. El mensaje más importantes del curso es el contraste entre lenguajes estáticos y funcionales y entre descomposición de problemas funcional o en objetos.

Esta parte del curso es relativamente corta pero difícil. No pude mirar los videos enteros pero repasé las notas para hacer los problemas. Los comentarios generales son iguales a los de la parte A: en líneas generales la calidad del curso es altísima.

La segunda parte no busca revisar las ideas que vimos en ML en otro lenguaje, sino seguir agregando conceptos.

Como es habitual en este tipo de curso, me dediqué sobre todo a los programming assignments (repo).

ASSIGNMENT 4: Streams y lazy evaluation (97%)

En este Assignment practicamos con streams y lazy evaluation. No es muy complicado, aunque la idea de tener colecciones infinitas está bastante ligada a la recursión y puede ser un poco mind bending.

ASSIGNMENT 5: MUPL (93%)

Este es el assignment más difícil del curso. La idea es implementar un lenguaje de programación (Made Up Programming Language). Si bien el lenguaje es relativamente sencillo, incluye first class functions y soporta recursión, todo lo cual hay que implementar usando Racket como metalenguaje.

El problema principal es implementar una función que interprete el código escrito en MUPL. MUPL tienen varios tipos de expresiones (funciones, listas, etc.) y de valores.

Este Assignment me pareció tremendamente difícil. Como al final me fue relativamente bien puedo decir que es bastante gratificante. Siguen pendientes los challenge exercises y los community exercises, que prometen ser interesante, pero recién terminé el básico y estoy muerto.

ASSIGNMENT 6: Tetris (100%)

En este assignment, tenemos que extender una implementación de Tetris que nos dan. Está bueno para aprender a navegar una base de código pre existente. La solución usa una librería de Gráficos (Qt) y un wrapper escrito en Ruby. Tuve bastantes problemas para hacerla andar en Linux, así que terminé haciendo el assignment en una máquina virtual Win XP (!).

Lo que tenemos que hacer es agregar algunas al juego y una funcionalidad nueva que permite hacer trampa. Muy interesante, sobre todo para entender programas escritos por otros (es difícil adquirir experiencia en esto en este tipo de cursos). La solución de Dan es (esperablemente) bastante elegante, aunque hay partes que no entendí del todo.

 

ASSIGNMENT 7: a language for arithmetic expressions (99%)

En este assignment tenemos que implementar un lenguaje de aritmética en SML y en Ruby. Nos dan la versión de SML bastante avanzada y nosotros tenemos que completarla. La de Ruby implica portar las soluciones desde SML.

El lenguaje tiene líneas y puntos, y permite moverlos e intersectarlos. También tiene lets y variables. La principal lección del assignment es ilustrar como se descompone el problema en el caso funcional en operaciones sobre datatypes.

Así, Point, Line, Shift, Var, etc. son datatypes, y el programa consiste en definiciones de funciones que permiten preprocesarlas y evaluarlas. En el caso de Ruby, Point, Line, etc, son classes, con métodos que implementan las operaciones.

Esto se refiere a una de las clases, donde Dan habla de como hay una tabla de doble entrada entre entidades (Point, Line, etc.) y operaciones (eval_exp, preprocess, print, simplify). De esta forma, un lenguaje funcional nos va a permitir agregar operaciones fácilmente sin tocar otras partes del programa. Por otro lado, un lenguaje basado en clases nos permite agregar entidades sin impactar el resto del programa.

El problema es agregar entidades en el caso funcional (por ejemplo, un rectángulo). Eso implicaría agregar un branch en todos los pattern matches de las funciones en el caso de SML. O, si queremos agregar una operación nueva (dibujar) en la implementación de Ruby. En este caso, tendríamos que agregar un método a todas las clases.

La otra lección importante de este assignment es sobre el dynamic dispatch de Ruby. Dan no nos permite usar los métodos #is_a? ni #class. Según el , eso sería un híbrido con los pattern match de sml. Entonces, nos obliga a usar dynamic dispatch para implementar Intersect.

La idea de is_a, es saber de que tipo es el argumento de un método. Para evitar usar ese método, dado, que sabemos cual es la clase de self (ja!), si self es una línea (por ejemplo), hacemos

other.intersectLine self

E implementamos intersectLine en todas las clases. Esto evita tener que preguntar la clase de un objeto. (No sé que implica esto para usar duck typing). Para implementar la intersección de dos segmentos, el algoritmo implica convertir uno de los segmentos en una línea. La forma en que tenemos que implementar esta solución usando inheritance y dynamic dyspatch es mind bending…

Pasé más tiempo de lo que esperaba con este problema, pero en el global fue muy interesante.

Examen

Al final del curso hay un cuestionario bastante teórico. Como no pude repasar los videos con cuidado no traté de hacerlo, pero probablemente lo haga en breve.

 

 

 

Programming Languages Part A – Dan Grossman (2016)

course_logo

Setiembre 2016

La primera vez que intenté hacer este curso me rompió la cabeza, pero me quedé por la mitad. En este post hablo de esa primera experiencia.

En 2016, el curso está disponible en la plataforma nueva de Coursera. Si bien no me gusta mucho, tiene la gran ventaja de que el curso y los assignments están disponibles por mucho más tiempo, y este curso sigue siendo gratis (yay!). 

Además, (siguiendo la tendencia general en Coursera), el curso original está dividido en 3 partes (A, B, C).

Además, hay un montón de problemas creados por la comunidad (hay un señor llamado Charilaos Skiadas que es un fenómeno) y además de estar muy activo en los foros hizo la mayor parte de los problemas extra.

El sistema de peer review está diseñado para poder tomar el curso asincrónicamente, y es una experiencia bastante interesante (aunque debo reconocer que me da un poco de pereza meterle mucha cabeza a leer las soluciones de otros). 

ASSIGNMENT 1: FUNCIONES CON FECHAS (98%) (100%)

Implementar un montón de funciones en ML para trabajar con fechas sin mutabilidad. Básicamente sirve mucho para acostumbrarse a escribir funciones recursivas.

ASSIGNMENT 2: MAS EJERCICIOS FUNCIONALES (81%) (99%)

Datatypes y case expressions. Implementamos un juego de cartas muy simple tipo solitario.

ASSIGNMENT 3: UN LENGUAJE DE PROGRAMACION (80%) (96%)

En este assignment empezamos a ver cosas que pueden ser útiles para implementar un lenguaje de programación. Implementamos funciones para procesar datatypes que representan patterns y values de un lenguaje.

Los patterns pueden ser variables, Tuples, Constants of Int o Constructores. Los values pueden ser Tuples, Constantes, Constructores, etc. La función match devuelve los bindings que resultan de matchear un pattern con un value.

MOCK EXAM: (100%) Y EXAM: (93%)

Al final del curso hay un examen de 15 preguntas, y un mock para probar. Las preguntas son sobre todo el curso (centrado en el último módulo que no tiene assignment) bastante interesantes, vale la pena hacerlo.

Conclusion: 

Estoy super emocionado con seguir en la Parte B y C de este curso.

Curso de STATA

Este es un curso que preparé estos meses para URSEC. La idea es que los participantes tengan conocimientos básicos de estadística, y traté de enfocar el curso para cubrir aspectos prácticos de análisis de datos (sobre todo manejo de datos, que es el gran punto débil de la educación formal que reciben).

La principal fuente que usé fue Statistics with STATA, de Lawrence C. Hamilton.  sws12-thumbEl libro está muy bueno, demostrando con ejemplos muchísimas técnicas para aplicar los comandos básicos de Stata.  El autor parece particularmente preocupado por el calentamiento global, y hay bastantes ejemplos con datos sobre ese tema. Lo mejor es que todos los datos que usa en los ejemplos estan disponibles en el sitio de STATA.

 

Tema 1: Introducción (Slides) (1 clase)

Un tour por las principales funciones de Stata, con énfasis en la estimación de un modelo lineal.

Tema 2: Manejo de Datos (Slides) (4 clases)

Uso intensivo de las funcionalidades de Stata para manipular data sets (importar datos desde varios formatos, merge, reshape, keep, drop, etc.)

Tema 3: Gráficos (Slides) (2 clases)

Repasamos los gráficos más usados en Stata: (Caja, Series de Tiempo, Scatterplots). También hice bastante énfasis en la sintaxis para construir gráficos superpuestos. Al final hay dos ejercicios con datos de precios de supermercados.

Tema 4: Inferencia y Modelización (Slides)  (3 Clases)

Pruebas de hipótesis e intervalos de confianza. Modelos lineales simples y mútliples. Variables Dummy, especificación log/log y log lineal.

Tema 5: Sistemas de Ecuaciones y Endogeneidad (Slides)  (2 Clases)

Los participantes estan interesados en estimar modelos AIDS, por lo que también presenté varios ejemplos de Sistemas de ecuaciones (2sls) y variables instrumentales (ivreg)

Tema 6: Varios

Este tema quedó un poco pendiente por falta de tiempo. Los temas que estaban planificados eran: Otros modelos (Regresión Logística y truncada). Programación (macros y bucles para ahorrar tiempo y mejorar la legibilidad del código).

Nand2Tetris – Part I

Este curso tiene como objetivo desmitificar como funciona una computadora.
Para eso, construimos en 14 proyectos (6 en la parte I del curso y 8 en la
parte 2) una computadora de uso general.

¿Con qué materiales? Este no es un curso de electrónica, asi que la
parte de Hardware del curso la hacemos en un simulador, donde
construimos chips en un lenguaje específicamente creado para diseñar hardware (Hardware
Design Language – HDL) y luego los testeamos.

De esta manera, a partir del un chip Nand, que tomamos como dado,
vamos construyendo una jerarquía de chips (logic gates, ALU, CPU) hasta
construir una computadora (HACK computer). De ahí viene el concepto del curso, que es que a partir de un solo chip podemos construir una computadora arbitrariamente compleja.

En la segunda parte del curso, se construye una máquina virtual, un
lenguaje de programación orientado a objetos (JACK) y un compilador para
traducirlo a HACK, el lenguaje assembler de la computadora.

Hay que decir que es uno de los cursos mejor diseñados en los que participé
(como los cursos de Rice de Rixner y Warren también en Coursera) por lo
bien pensados que están desde el punto de vista de la experiencia del
alumno, y el cuidado que ponen en darnos todas las herramientas conceptuales para resolver los ejercicios.

Shimon Schocken, uno de los instructores del curso, tiene un paper sobre las ideas que tuvo en cuenta para diseñar el curso. Obviamente le puso mucha cabeza al tema, y los resultados lo demuestran.

Los primeros 4 Homeworks son relativamente simples, hay que diseñar los chips usando HDL. De esta manera, construimos una jerarquía de los chips que componen la computadora. El primer problema lo tuve en el Assignment 5, donde hay que construir una CPU, y me di por vencido antes de terminar.

CPUDiag

 

Este es el diagrama del chip, lo único que hay que hacer es implementarlo. Lo complicado es ver como los bits de control entran a cada chip.

El Homework 6 también es relativamente simple, requiere implementar un programa que traduce del lenguaje simbólico a binario. Lo podemos implementar en cualquier lenguaje (yo elegí Ruby). Mi programa and básicamente bien, salvo por un pequeño problema con los comments. Debería aprender algo más de Regular Expressions para solucionarlo bien.

Este repo tiene todo el código que escribí para el curso.

 

Sobre la nueva política de Coursera

Un comentario aparte merece la nueva política de Coursera de cobrar por los assignments que llevan nota. Esta política parece aplicarse a algunos cursos (los de Rice por ejemplo). Los cursos originales merecen una mención especial: Cryptography, Design and Analysis of Algorithms (Stanford), Algorithms (Princeton) siguen siendo gratis.

Gregor Ulm tiene un post sobre esto. La primera vez que lo leí me pareció un poco excesivo, pero empecé a prestar atención y estoy bastante triste. Obviamente Coursera y las universidades tienen que recaudar para justificar el esfuerzo que hacen en producir el contenido. Cada vez parece más claro que la época dorada de los MOOCs llegó a su fin.

Nand2Tetris requiere pagar para enviar los Homeworks, pero los scripts para testear tu código estan disponibles en el sitio web del libro, así que no hay problema!

 

Engineering Software as a Service, Part II

Esta es una review de la segunda parte del curso de Berkeley. La primera parte está acá.

La segunda parte de este curso empezó a mitad de Enero. En realidad es el mismo curso partido en dos, por lo que las impresiones generales son muy similares. Sobre los assignments:

HW1) Oracle of Bacon

Hay que usar una API que calcula el grado de separación entre dos actores, y lo devuelve como XML. Un caso de uso interesante para XPATH, y el tema de las APIs parece ser muy importante en la vida real.

HW2) Fix a bug in typo

Typo es un CMS para armar blogs. En este assignment hay que arreglar un bug. Al final el código para arreglar el bug era fácil de escribir (una línea de application code + el test) Pero trabajar sobre una app complicada que se usa en la vida real es un ejercicio muy original para un Mooc. Ver adelante. Me atrasé para entregarlo y me bajaron el puntaje.

HW3) Agregarle una feature a Typo.

En este assignment hay que agregarle una feature a Typo (mergear dos artículos) Hay que escribir los user stories, los specs y la implementación. La verdad es que es bastante complicado trabajar sobre una codebase que no conozco (y me parece que es imposible conocer en detalle todo el código que estoy viendo).
No terminé el curso. El úitimo assignment era optimizar unas consultas SQL y una quiz sobre chaching.

Engineering Software as a Service, Part I

Engineering Software as a Service

Parte 1

La primera parte de este curso fue un poco decepcionante. No porque el curso no sea bueno, sino porque tenía demasiadas expectativas. La primera vez que lo vi no lo pude seguir, y empecé a investigar sobre Ruby on Rails para la siguiente iteración. Al final terminé aprendiendo bastante sobre Rails con dos tutoriales excelentes (Pragmatic Programmer y Rails Tutorial de Michael Hartl), así que los Homeworks de este fueron relativamente sencillos. Igual es importante resaltar que el foco del curso no es aprender Rails, sino buenas prácticas para hacer aplicaciones Saas (Agile, TDD, etc.).

Aparte de eso, el curso tiene bastantes puntos de quizzes y un examen. Como quería sacar el certificado, hice todos los requerimientos y me saqué 90%.  A continuación algunos detalles de cada assignment:

HW0) Intro to Ruby

Algunos ejercicios bastante simples para familiarizarse con Ruby. Nada del otro mundo, problemas chicos a nivel de cualquier sitio interactivo (Code School, Codewars, etc.)

HW1) Hangman

Esto es una app en Sinatra. La parte de las sessions fue un poco más compleja de lo que esperaba, porque no conocia Sinatra. Armando tiene un video donde explica algunas cosas que hubiera sido bueno saber antes de empezar a programar. Me di la cabeza contra la pared más de lo necesario por no leer la documentación.

HW2) Rotten Potatoes

Esta app se usa en varios Assignments del curso, es una base de datos con reviews de pelis. Para este problema implementamos la funcionalidad de ordenar la lista de películas por dos criterios. La idea es enfocarse en hacer que la API siga la arquitectura REST, codificando todo el estado de la aplicación en la URL.

HW3) BDD and Cucumber

En este Homework, nos presentan a Cucumber, una dsl para escribir User Stories que se parezcan lo más posible a lenguaje humano. Esto permite que los clientes no técnicos esten más involucrados en el desarrollo de la aplicación. El ejercicio es una modificación sencilla a la aplicación Rotten Potatoes.

HW4) TDD CyclE

En este assignment, la idea es familiarizarse con el ciclo TDD (Red, Green, Refactor) usando Rspec. Si bien el ejercicio es bastante fácil, no es trivial adaptarse al ritmo de escribir tests primero.

Varias veces empecé a escribir programas que no parecían suficientemente complicados para hacerlos con TDD, e invariablemente se complica. La regla que estoy tratando de adoptar es: si no vale la pena programarlo con TDD,  no vale la pena programarlo.

 

Sudoku Solver

Para hacer un curso de gráficos 3D tengo que aprender C++ así que salí a buscar materiales. Lo mejor que encontré fue este curso de Stanford.

El curso es el segundo curso de computación que tienen los alumnos de Stanford, (el primero es en Java). Como tal, es interesante porque no se detiene mucho en la sintaxis de C++ (es bastante similar a Java y a C) sino en aspectos más conceptuales (el énfasis es en programar abstracciones (queues, vector, map, stack)). Sin ser un curso de algoritmos, es una buena intro.

La profe se llama Julie Zelenski y es excelente: graciosa, inteligente, casi linda… Como no pude usar las librerías que le dan a los alumnos no pude hacer los assignments. Lo que si pude hacer es tratar de hacer andar el código que tratan en clase. Un ejemplo interesante es este Sudoku Solver.

sudoku300

El algoritmo explora recursivamente el árbol de posibilidades hasta encontrar una solución. Es similar  al pset5 de MIT 6.00. El principal problema consiste en manejar correctamente la memoria del stack. Acá está el código [link al gist].

Aparte de eso implementamos varias ADTs (Queue, Stack, Map, Vector), lo que es una forma bastante interesante de conocer como funciona C++. Obviamente que me distraje un poco de los gráficos 3D.

Otra cosa totalmente nueva que estoy aprendiendo son los pointers. Creo que eso vale la pena entenderlo en detalle por lo que estoy pasando más tiempo de lo esperado en este material. También hay otro curso de Stanford en Youtube que tiene unas cuantas clases sobre pointers y como programar funciones genéricas en C.

Cómo en C no hay templates, es necesario manipular la memoria a nivel de bits para hacer funciones genéricas (un linear search que sirva para un array de ints o un array de strings). Todas esas cosas que damos por obvias los que usamos lenguajes de alto nivel como Python y Ruby, hay que hacerlas a pedal en lenguajes más rústicos como C.

En otro post entraré más en detalle sobre estas clases, porque me parecen bastante interesantes y probablemente las mire con atención.

MIT 6.00

Este curso es una versión en dos partes del primer curso de computación en MIT. Usan Python. El curso lo toman todos los estudiantes de carreras técnicas de MIT, por lo que no está enfocado como los típicos CS 101, sino como un panorama de como resolver problemas con computadoras en varias áreas.

 

Introduction to Computer Science and Programming Using Python

Como los deadlines son bastante estrictos y ya conozco bastante los temas no me lo tomé muy en serio, hice algunos de los ejercicios para trabajar con Emacs.

De todas formas me topé con algunas complicaciones y aprendí algunas cosas nuevas.

 

Introduction to Computational Thinking and Data Science

 

Cuando me di cuenta que este curso tenía problem sets interesantes era un poco tarde, pero lo más probable es que en la próxima iteración haga alguno más y actualice este post.  En esta iteración pude hacer solo es 5.

Pset 5 – Finding Shortest paths

Este fue bastante complicado. El problema consiste en procesar un graph con la información de una mapa del campus de MIT. Hay que encontrar el camino más corto entre un lugar  y otro, con la particularidad que hay caminos techados y caminos al aire libre, y hay una restricción de cuanto puedo recorrer al aire libre.

Esto hace que el algoritmo estándar no funcione. La solución es un algoritmo recursivo que explora el grafo y recuerda cual es mejor solución de las que ya recorrió. El bug más difícil que tuve fue por manejar mal la memoria en el stack, porque había que tener en la memoria y accesible para todo el stack cual era el camino más corto, y para cada stack tenía que tener la memoria del camino que había seguido hasta llegar ahí. Una vez que llegaba a un dead end, tenía que backtrack hasta un nodo válido, y recuperar ahí el camino. Esto fue un poco complicado. [Referencia a Sudoku Solver].

 

 

Amaestrando Emacs

Siempre quise saber usar bien un editor de texto. La mayor parte de los nerds hardcore usan Vim o Emacs. Después de leer bastante sobre las idiosincracias de cada uno, me parece que Emacs es para mi. Además, lo usé un poco en el curso de Dan Grossman sobre Programming Languages a fines de 2014 para la parte de SML.

El mejor material que encontré es el libro de Mickey Petersen Mastering Emacs. En Youtube hay bastante material, pero en general es aburridísimo. Sasha Chua tiene un montón de entrevistas donde hablan usuarios legendarios de Emacs. Además Steve Yegge tiene un montón de posts sobre Emacs.

En conclusión, Emacs es genial si ya sos un capo, pero es bastante difícil de hincarle el diente. En general siempre me vuelco por este tipo de herramientas, creo que es preferible que algo sea cada vez mejor a medida que te volvés mejor, y no al revés (se me ocurre que es el caso de MS Excel) que cuanto mejor sabés usarlo más lo odias.

Básicamente, diría que el uso básico de todo editor de texto incluye las siguientes funcionalidades:

  • Cortar y Pegar Texto
  • Moverse adentro de un archivo
  • Moverse entre archivos
  • Snippets
  • Macros
  • Autocomplete

Después de un añó de usar Emacs y un par de meses de tratar de aprenderlo activamente, creo que soy aceptable en todas menos Autocomplete.