Análisis y Diseño de Algoritmos 2023-1
Profesores
Carlos Ramírez (carlosalbertoramirez *at* javerianacali.edu.co)
Camilo Rocha (camilo.rocha *at* javerianacali.edu.co)
Horario
Martes (Palmas 3.1) 09:00 - 11:00
Jueves (Palmas 3.1) 09:00 - 11:00
Atención a estudiantes
Jueves 11:00 - 12:00 (Camilo Rocha, Of. 2.02 Facultad de Ingeniería y Ciencias)
Jueves 14:00 - 15:00 (Carlos Ramírez, Of. 2.42 Facultad de Ingeniería y Ciencias)
Viernes 14:00 - 15:00 (Monitor, definido por Discord)
Monitor
Robin Hafid Quintero
Bitácora
Bienvenida (01/24) [grabación]
Introducción
Notación asintótica (01/26) [grabación, apuntes]
Operadores: O, Ω, Θ
Uso de las definiciones para demostrar y refutar pertencia a los cojuntos obtenidos con los operadores
Notación asintótica (01/31) [grabación]
El Teorema Maestro y Dividir-Conquistar-Combinar (02/02) [grabación, apuntes]
Mergesort
Teselación con tridominós
Dividir-Conquistar-Combinar (02/07) [grabación, apuntes]
Teselación con tridominós
Ordenamiento iterativo
Búsqueda binaria (02/09) [grabación, apuntes]
Diseño basado en dividir-conquistar-combinar
Implementaciones recurrente e iterativa [código]
Variantes del problema de búsqueda
Búsqueda binaria (02/14) [grabación, apuntes]
Búsqueda sobre funciones monótonas
Bisección (02/16) [grabación, apuntes]
UVa 907 - Winterim Backpacking Trip [enunciado]
Programación dinámica (02/21) [grabación, apuntes]
Números de Fibonacci
Programación dinámica (02/23) [grabación, apuntes]
SubsetSum [código]
Programación dinámica (02/28) [grabación, apuntes]
Knapsack, i.e., el problema del morral [código]
Programación dinámica (03/07) [grabación, apuntes]
Longest common subsequence (LCS) [código]
Programación dinámica (03/09) [grabación, apuntes]
UVa 12654 - Patches [enunciado]
Parcial 1 (03/14) [enunciado]
Algoritmos voraces (03/21) [grabación, apuntes]
Introducción
Agendamiento de actividades [código]
Algoritmos voraces (03/23) [grabación, apuntes]
Agendamiento de actividades y variantes
Algoritmos voraces (03/28) [grabación, apuntes]
Árboles de cubrimiento mínimo
Algoritmo de Kruskal [código]
Algoritmos voraces (03/30) [grabación, apuntes]
Árboles de cubrimiento mínimo
Algoritmo de Kruskal [código]
Conjuntos disyuntos
Reintento (04/11) [grabación, apuntes]
El problema de las n reinas [código]
Reintento (04/13) [grabación, apuntes]
Segmentación de texto [código]
Reintento (04/20) [grabación]
Repaso e ideas para resolver tarea
Clases de complejidad (04/25)
Parcial 2
Clases de complejidad (04/27) [grabación, apuntes]
Problemas de decisión
Indecidibilidad
Clases de complejidad (05/02) [grabación, apuntes]
La clase P
Reducciones polinomiales
Clases de complejidad (05/04) [grabación, apuntes]
Decisión y aceptación en P
Clases de complejidad (05/09) [grabación, apuntes]
Algoritmos de verificación
La clase NP
Clases de complejidad (05/11) [grabación, apuntes]
La clase NP-hard
La clase NP-complete
Circuit-SAT es NP-complete
Clique es NP-Complete si 3CNF-SAT es NP-complete
Problemas NP-Complete (05/16) [grabación, apuntes]
Clique es NP-Complete si 3CNF-SAT es NP-complete
VertexCover es NP-Complete si Clique es NP-Complete
Problemas NP-Complete (05/18) [grabación, apuntes]
2Partition <=p 3Partition
Solución examenes finales 2022-1 y 2022-2
Enlaces
Notas (actualizado 06/06)
Texto guía
Capítulos 0 a 5 (actualizado 04/15)
Software de apoyo
Arena de programación (DomJudge)
Plataforma de comunicación (Discord)
Otros enlaces
Exámenes
2016-1: parcial 1, parcial 2, examen final
2016-2: parcial 1, parcial 2, examen final
2017-1: parcial 1, parcial 2, examen final
2017-2: parcial 1, parcial 2, examen final
2018-1: parcial 1, parcial 2, examen final
2018-2: parcial 1, parcial 2, examen final
2019-1: parcial 1, parcial 2, examen final
2019-2: parcial 1, parcial 2, examen final
2020-1: parcial 1, parcial 2, examen final
2020-2: parcial 1, parcial 2, examen final
2021-1: parcial 1, parcial 2, examen final
2021-2: parcial 1, parcial 2, examen final
2022-1: parcial 1, parcial 2, examen final
2022-2: parcial 1, parcial 2, examen final
2023-1: parcial 1, parcial 2, examen final
Proyecto
Level Up : enunciado | 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 para el caso de prueba #1: Simple case.
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.
El archivo debe ser enviado, también, por BrightSpace.
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 en 10 categorías. 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 los casos de prueba #1 a #10. 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.
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.
Tareas
Tarea 1: para entregar 02/05
plantillas
Tarea 2: para entregar 02/19
Tarea 3: para entregar 03/12
Tarea 4: para entregar 04/02
Tarea 5: para entregar 04/23