Descripción del Curso

Justificación

Aunque la capacidad de procesamiento y almacenamiento de los computadores sigue aumentando, también es cierto que los volúmenes de datos y la complejidad de las tareas asignadas a estos es cada vez mayor. Adicionalmente, desde mucho antes de la aparición del computador se han estudiado cientos de problemas de gran aplicación práctica, para los cuales no se conocen procesos algorítmicos eficientes ni se cree que aparezcan en el futuro.

El ingeniero de sistemas debe estar en capacidad de estimar matemáticamente la complejidad computacional de los problemas a los que se enfrenta en su actividad profesional y además, debe ser capaz de proponer, evaluar y elegir acertadamente soluciones para esos de problemas, siendo consciente de antemano, del desempeño que tendrán una vez estén implantadas.


Objetivo

El objetivo del curso es estudiar los principios fundamentales de la solución de problemas a través de algoritmos computacionales. El curso aborda dos aspectos principales: el análisis de algoritmos y el diseño de algoritmos eficientes. El análisis de algoritmos estudia las herramientas matemáticas que permiten caracterizar la eficacia y eficiencia, en términos de tiempo y memoria, de un algoritmo. El diseño de algoritmos estudia diversos tipos de problemas y técnicas para resolverlos de manera eficiente.

Contenido


 Tema          Udacity CS 215  Material y Recursos
1. Introducción
1.1 Nociones básicas (algoritmo, programa, problema, instancia, operación básica)
1.2 Análisis de algoritmos
1.3 Diseño de algoritmos
1.4 Dividir y conquistar
Lesson 1: A Social Network Magic Trick
Becoming familiar with algorithm analysis
[Cormen09] Cap 1, Cap 2
IPython notebook: corrección y análisis de algoritmos 
Datos
2. Análisis de Algoritmos
2.1 Tipos de grafos
2.2 Notación asintótica
2.3 Recurrencias
2.4 Método maestro
Lesson 2: Growth Rates in Social Networks
Using mathematical tools to analyze how things are connected
[Cormen09] Cap 3, Cap 4
IPython notebook: ordenamiento por mezcla
3. Algoritmos Básicos en Grafos
3.1 Búsqueda en profundidad
3.2 Búsqueda en amplitud
3.3 Componentes conexas y conectividad
3.4 Puentes
Lesson 3: Basic Graph Algorithms
Finding the quickest route to Kevin Bacon
[Cormen09] Cap 22
IPython notebook: búsquedas
4. Quicksort, Mediana,, Estadísticas de Orden, Quickselect, M
ontículos y Heapsort

4.1 Media, Mediana y Estadísticas de orden 
4.2 Quicksort
4.3 Quickselect
4.4 Montículos
4.5 Heapsort
Lesson 4: It’s Who You Know
Keeping track of your best friends using heaps
[Cormen09] Cap 9, 6
DISI Quicksort
DISI HeapSort
Lecture 4: Quicksort, Randomized Algorithms MIT Introduction to Algorithms (SMA 5503 ) Fall 2005  
Lecture 6: Order Statistics, Median MIT Introduction to Algorithms (SMA 5503 ) Fall 2005
Median - Wikipedia
Percentile - Wikipedia
Quantile - Wikipedia
Order Statistic -- from Wolfram MathWorld
Computer Generation of Statistical Distributions

Quicksort form interactivepython.org
IPython notebook:quicksort from interactivepython.org
IPython notebook: randomquicksort distr comps(tiempo)

IPython notebook: quicksort two finger comp distrib (tiempo)
IPython notebook: montículos

DISI Applets 
Sorting Comparison Demos

Distributional Convergence for the Number of Symbol Comparisons Used by QuickSort from JA Fill, Johns Hopkings U.
Distributional Convergence for the Number of Symbol Comparisons Used by QuickSelect.from JA Fill, Johns Hopkings U.
5. Programación  Dinámica 
5.1 Funciones con memoria
5.2 Secuencia común más larga
5.3 Numero de formas de dar cambio en monedas
5.4 Corte de la vara
  [Cormen09] Cap 15

IPython notebook: fibonacci
IPython notebook: lcs
IPython notebook: cutrod
IPython notebook: timeitexmaples


Lecture 15: Dynamic Programming, Longest Common Subsequence MIT  Introduction to Algorithms (SMA 5503 ) Fall 2005
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
DISI LCS applet

CS 97SI: Introduction to Programming Contests - Jaehyun Park - Stanford University, 04-dynamic-programming.pdf change-integer partitions

Ch15 Dynamic Programming Rod Cutting  UMass Lowell Computer Science 91.503 Analysis of Algorithms Prof. Giampiero Pecelli 2010

CS3233 Competitive Programming  - old teaching materials - Steven Halim - NUS, week04_dp_1.pdfweek04_dp_2.pdf
6. Camino más Corto
6.1 Camino más corto desde una fuente
6.2 Camino más corto entre todas las parejas
Lesson 5: Strong and Weak Bonds
Working with social networks with edge weights.
[Cormen09] Cap 24, 25

IPython notebook: Dijksitra
IPython notebook: Djkstra_eppstein
IPython notebook: BellmanFord
IPython notebook: FloydWarshall
  

DISI decompositions_of_graphs.rar
DISI ch04-paths-in-graphs.ppt

Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search 
Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints and 
Lecture 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson MIT  Introduction to Algorithms (SMA 5503 ) Fall 2005
 
CS3233 Competitive Programming  - old teaching materials - Steven Halim, NUS, week05_graph_1.pdf
Udacity CS 215 Lesson 5: Strong and Weak Bonds Working with social networks with edge weights.
7. Complejidad Computacional
7.1 Clases de complejidad
7.2 Problemas NP-completos

Lesson 6: Hardness of Network Problems
Exploring what it means for a social network problem to be harder than other.
Lesson 7: Conclusion
Using your knowledge
[Cormen09] Cap 34
Complejidad computacional
DISI calculabilidad.zip
DISI complejidad.zip 
Udacity CS 215 Lesson 6: Hardness of Network Problems Exploring what it means for a social network problem to be harder than other.
Udacity CS 215 Lesson 7: Conclusion Using your knowledge.

Extracredito 5%
Udacity CS 313 Intro to Theoretical Computer Science 
Problem Set 4  - 
Reduced Satisfaction SAT 


Programa 


Semana
Tema
Entregas
1 de Agosto (1.1) Presentación general del curso y nociones básicas
Introducción a python

8 de Agosto (1.2) Análisis de Algoritmos
(1.3) Diseño de Algoritmos.
 
15 de Agosto Udacity Lesson 1
22 de Agosto (1.4) Dividir y conquistar Práctica de Python
29 de Agosto (2.1) Tipos de grafos
(2.2) Notación asintótica

5 de Septiembre (2.3) Recurrencias
(2.4) Método maestro
Udacity Lesson 2
12 de Septiembre (3.1) Búsqueda en profundidad
(3.2) Búsqueda en amplitud
 
19 de Septiembre (3.3) Componentes conexas y conectividad
(3.4) Puentes
Udacity Lesson 3
26 de Septiembre(4.1) Quicksort
Taller 1
3 de Octubre (4.2) Quickselect
(4.3) Media, Mediana y Estadísticas de orden
Examen 1 (7 de Octubre)
10 de Octubre (4.4) Montículos
(4.5) Heapsort
Udacity Lesson 4
24 de Octubre (5.1) Funciones con memoria 
(5.2) Secuencia común más larga
(5.3) Número de formas de dar cambio en monedas
(5.4) Corte de la vara
 
31 de Octubre (6.1) Camino más corto desde una fuente  
7-14 de Noviembre (6.2) Camino más corto entre todas las parejas Udacity Lesson 5
21 de Noviembre (7.1) Clases de complejidad
(7.2) Problemas NP-completos
Udacity Lesson 6
28 de Noviembre Examen Final Taller 2
Taller: caminos más cortos desde una fuente
Taller: Grafos, Complejidad Computacional, Programación Dinámica

Evaluación


La calificación final se obtiene según la siguiente distribución de porcentajes:
  • Examen parcial: 20% 
  • Examen final:    20%
  • Laboratorio y Udacity:   30%
  • Talleres, tareas, quices: 15% 
  • Proyecto - desarrollar una estrategia de  algorítmica de trading en Quantopian: 15% 

Bibliografía

  • [Cormen09] Cormen, T. H., Stein, C., Rivest, R. L., and Leiserson, C. E. 2009 Introduction to Algorithms. 3rd. McGraw-Hill Higher Education
  • [Dasgupta07] Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, "Algorithms" , McGraw Hill, 2007. Book Website
  • [Skiena03] Skiena, S. S. and Revilla, M. A. 2003. Programming challenges: the programming contest training manual. Springer-Verlag.
  • [Harel04] Harel D, Feldman Y. Algorithmics: The Spirit of Computing (3rd Edition). Addison Wesley; 2004.
  • [Goodrich02] MT Goodrich, R Tamassia. 2002. Algorithm design: foundations, analysis, and Internet examples. Wiley. 
  • [Bentley00] Bentley, J. 2000 Programming Pearls (2nd Ed.). ACM Press/Addison-Wesley Publishing Co.

Otros Recursos

Cursos en línea sobre algoritmos:
Visualizing data structures and algorithms through animation
Pancake sorting problem
C. Leiserson and E. Demaine, Introduction to Algorithms Course, MIT OpenCourseware, 2005
http://disi.unal.edu.co/~algoritmos
CMU Great Theoretical Ideas In Computer Science http://www.cs.cmu.edu/~15251/
Python: