Análisis y Diseño de Algoritmos 2020-2

Profesores

  • Camilo Rocha (camilo.rocha *at* javerianacali.edu.co)
  • Carlos Ramírez (carlosalbertoramirez *at* javerianacali.edu.co)

Horario

  • Martes (Palmas - 3.2 Zoom) 09:00 - 11:00
  • Jueves (Palmas - 3.1 Zoom) 09:00 - 11:00

Atención a estudiantes

  • Lunes 15:00 - 16:00 (Carlos)
  • Lunes: 16:00 - 17:00 (Camilo)
  • Jueves: 11:00 - 12:00 (Camilo)
  • Jueves: 16:00 - 18:00 (Juan David)

Monitor

  • Juan David Rengifo (juanrengifo912 *at* javerianacali.edu.co)

Programa del curso

Enlaces

Exámenes pasados

Notas de clase

Proyecto

Design New Capital (UVa 1733) : enunciado original | enunciado extendido | arena | casos de prueba

Entrega 0 (10%)

Esta entrega consta de un documento que describe la naturaleza de la solución del problema. En este documento se debe reflejar qué tanto entiende del problema, cuál es su estrategia de solución y la cantidad de trabajo que ha hecho para el proyecto. En esta entrega no es necesario tener una solución del problema pero sí tener claro cómo se puede resolver.

El documento para esta entrega no tendrá más de 3 páginas y, como mínimo, deberá contener la siguiente información:

    • Especificación del problema (entrada y salida)
    • Algoritmos y estructuras de datos que usará su solución (cada decisión debe ser justificada)
    • Estrategia de solución
    • Análisis (alto nivel) de complejidad temporal y espacial de su solución
    • De ser necesario, citas bibliográficas del material consultado y que será usado en la solución del proyecto

Recuerde que el proyecto es individual.

Entrega 1 (20%)

Esta entrega consta de un único archivo fuente en el lenguaje de programación Python que debe ser aceptado en la arena como correcto en la arena disponible para el proyecto.

El contenido del archivo debe contar con:

    • Un encabezado que declare de forma unívoca la autoría del código: (i) nombre del autor (estudiante quien entrega el proyecto), (ii) su código de estudiante y (iii) la frase de compromiso del código de honor del curso.
    • Documentación de cada una de las funciones usando el estándar de Python.

Cualquier archivo entregado sin seguir los lineamientos anteriores será ignorado para efecto de la calificación del proyecto.

Entrega 2 (70%)

Esta entrega consta de dos partes: (i) solución de casos de prueba y (ii) sustentación.

Los casos de prueba están clasificados como fáciles (PR-B), medios (PR-C) y difíciles (PR-D). Para obtener una puntación perfecta en esta entrega es indispensable que una solución resuelva correctamente todos los casos de prueba disponibles en la arena para PR-B, PR-C y PR-D. Para que una solución sea considerada para puntuar es necesario que el archivo cumpla con las condiciones de la Entrega 1. Tenga en cuenta también que los casos de prueba deben ser resueltos por la misma solución, es decir, no es posible usar dos soluciones distintas para los casos de prueba.

Adicionalmente, para esta entrega se evaluarán durante la sustentación los siguientes requisitos no funcionales:

    • Diseño y uso clases para abstraer elementos de la solución
    • Nombres de variables, funciones/metodos, etc. en inglés
    • Elegancia del código

La sustentación de cada proyecto tomará alrededor de 10 minutos y para ello se abirará una lista de turnos. Para la sustentación es importante estar en capacidad de explicar la estrategia de solución, explicar los algoritmos utilizados (de memoria), describir las estructuras de datos utilizadas, y complejidades temporal y espacial de la solución. Una sustentación insatisfactoria del proyecto puede anular cualquier puntación otrogable por resolver satisfactoriamente casos de prueba.

A continuación se discrimina la puntuación para esta entrega:

PR-B: 5 (1 segundos)

PR-C: 10 (2 segundos)

PR-D: 20 (7 segundos)

PR-E: +10 (8 segundos)

PR-E corresponde a casos de prueba muy díficiles (en inglés evil) y su solución correcta en la arena otorga un bono de 10 puntos.

La sustentación es un factor entre 0 y 1 que pondera la puntuación enumerada anteriormente: entre mejor sea la sustentación, mayor será este factor.

Sesiones

  1. Bienvenida (08/11) [grabación]
  2. Dividir, conquistar y combinar (08/13) [grabación]
    • Ordenamiento de arreglos con algoritmo cuadrático
  3. Análisis asintótico (08/18) [grabación]
  4. Dividir, conquistar y combinar (08/20) [grabación]
    • Ordenamiento con MergeSort
    • Búsqueda binaria
  5. Programacion dinámica (08/25) [grabación]
    • Máxima longitud de una subsecuencia común (en inglés, Longest Common Subsequence - LCS)
      • Repaso
  6. Programación dinámica (08/27) [grabación]
    • Conceptos básicos
      • principio de optimalidad
      • memorización y tabulación
      • cálculo de Fibonacci
      • metodología
    • Repaso de LCS usando la metodología propuesta con reducción de espacio (notas, código)
  7. Programación dinámica (09/01) [grabación]
    • El Problema del Morral (en inglés, Knapsack)
  8. Programación dinámica (09/03) [grabación]
  9. Programación dinámica (09/08) [grabación]
  10. Conversatorio con César Muñoz (NASA Langley)
  11. Algoritmos voraces (09/15) [grabación]
  12. Algoritmos voraces (09/17) [grabación]
  13. Algoritmos voraces (09/23) [grabación]
    • Cubrimiento mínimo de intervalos [transparencias] (por Carlos Ramírez)
    • Árboles de cubrimiento mínimo
    • Los algoritmos de Kruskal y Prim [vídeo] (por Carlos Ramírez)
  14. Algoritmos voraces (09/25) [grabación]
    • Repaso de demostraciones voraces
    • Cubrimiento mínimo de intervalos [notas de clase]
  15. Algoritmos voraces (09/29) [grabación]
    • Single-source shortest path(s) y el Algoritmo de Dijkstra [transparencias, código] (por Carlos Ramírez)
    • El Algoritmo de Dijkstra [vídeo] (por Carlos Ramírez)
  16. Reintento (10/01) [grabación: parte1, parte2]
    • Búsqueda y enumeración exhaustivas: el problema de las 8 reinas
  17. Reintento (10/06) [grabación]
    • Enumeración en el problema de las 8 reinas [código] (por Carlos Ramírez)
    • Enumeración en subset sum [código] (por Carlos Ramírez)
    • Decisión en segmentación de texto [código] (por Carlos Ramírez)
  18. Reintento (10/08) [grabación, monitoría]
    • Segmentación de texto: diseño y corrección de un algoritmo [notas de clase]
  19. Receso (10/13)
    • día de receso
  20. Reintento (10/15) [grabación]
    • Generación de todas las subsecuencias ascendentes de longitud máxima [notas de clase, código]
    • Scheduling to minimize average completion time - parte (a) (Tarea 3, conceptual) [solución]
  21. Reintento (10/20) [grabación]
  22. Teoría de números computacional (10/22) [grabación]
  23. Teoría de números computacional (10/27) [grabación]
    • no hubo clase
  24. Teoría de números computacional (10/29) [grabación]
    • Criba de Eratóstenes y Teorema Fundamental de la Aritmética [notas, código] (por Carlos Ramírez)
  25. Teoría de números computacional (11/03) [grabación]
    • Máximo común divisor [notas] (por Carlos Ramírez)
    • El Algoritmo de Euclides [código] (por Carlos Ramírez)
  26. Teoría de números computacional (11/05) [grabación]
    • Funciones multiplicativas [notas] (por Carlos Ramírez)
  27. Clases polinomiales determinística (P) y no determinística (NP) (11/10) [grabación]
    • Conceptos básicos de problemas de decisión
    • Decidibilidad vs indecidibilidad
    • Tratabilidad vs intratabilidad
  28. Clases polinomiales determinística (P) y no determinística (NP) (11/12) [grabación]
  29. Clases polinomiales determinística (P) y no determinística (NP) (11/17) [grabación]
  30. Clases polinomiales determinística (P) y no determinística (NP) (11/19) [grabación]
    • Repaso de las clases P, NP, NP-hard y NP-complete; reducciones [notas de clase]
  31. Problemas NP-Completos (11/24) [grabación]
    • CIRCUIT-SAT, SAT y 3-CNF-SAT son NP-Completos
  32. Problemas NP-Completos (11/26) [grabación]

Tareas