$[/\]$

Universidad de Costa Rica Escuela de Ciencias de la Computación e Informática

$[\/]$

CI-1303 Estructuras de Datos y Análisis de Algoritmos

II Semestre 1999

Profesor Adolfo Di Mare

REQUISITOS

CI-1201 Programación II	Horas:	4
CI-1104 Matemáticas Discretas I	Créditos:	4

OBJETIVO

El estudiante será capaz de seleccionar el objeto o modelo matemático más adecuado para la especificación formal y la posterior resolución de un problema. Además, podrá identificar las operaciones elementales y no elementales que se deberán aplicar al modelo escogido con el fin de resolver el problema. El estudiante será capaz de implementar el modelo mediante la escogencia de la estructura de datos apropiada, así como de implementar las operaciones mediante algoritmos específicos. Ambas implementaciones deberán hacerse tomando en cuenta, principalmente, criterios de eficiencia, tanto de espacio como de tiempo, para lo cual el estudiante deberá saber calcular el tiempo y orden de duración de un algoritmo, así como estimar la cantidad de espacio que utiliza.

OBJETIVOS ESPECIFICOS

Estudiar los modelos matemáticos básicos, sus diversas representaciones, sus operaciones básicas y sus algoritmos.
Estudiar las principales estructuras de datos para la organización eficiente de información.
Estudiar los principales algoritmos para ordenamiento, búsqueda, manejo de grafos, etc.
Estudiar las técnicas fundamentales para la resolución de problemas.
Estudiar un modelo para medir la complejidad espacio-tiempo de un algoritmo.

CONTENIDOS

Relaciones de recurrencia Solución Aplicaciones Complejidad computacional	Parametrización de contenedores Biblioteca STL de C++ Iteradores Memoria dinámica
Listas Listas de punteros Listas de cursores Multilistas Pila Cola	Grafos Grafos dirigidos Algoritmos para grafos Expresiones regulares Autómatas finitos
Arreglos Matrices Matriz de adyacencia Lista de adyacencia	Métodos de búsqueda `LinearSearch()` `BinarySearch()` `KMPsearch()` `BMearch()`
Arbol Representación Arboles de búsqueda Arboles balanceados *Montículo (Heap)* Colas de prioridad	Métodos de ordenamiento `BubbleSort()` `SelectionSort()` `InsertionSort()` `MergeSort()` `HeapSort()` `BinSort()` `ShellSort()` `RadixSort()` `QuickSort()`

Periódicamente los estudiantes, en grupos de dos personas, deben entregar una tarea programada corta, que consiste en implementar dos algoritmos. El pseudo-código de la implementación estará disponible en Internet, o en alguno de los dos libros de texto del curso.

Exámenes
P#1 - Final

Tareas programadas cortas
#1 - #2 - #3

Tareas programadas
#1 - #2

Proyectos
#1

Otros

EVALUACION

El peso de la evaluación estará en los exámenes, aunque es indispensable que todos los estudiantes realicen los proyectos.

Examen Parcial #1 [29-set-1999] 25%      Proyecto #1 10%

Examen Final [3-dic-1999] 30%      Proyecto #2 10%

Tareas programadas 20%      Otros: 5%

Durante el curso es posible que se haga algún examen de práctica, para que los estudiantes tengan la oportunidad de afinar sus habilidades para tomar exámenes.

BIBLIOGRAFIA

Aho, Alfred V.; Hopcroft, John E.; Ullman, Jefrrey D.: "Data Structures and Algorithms"; Addisson Wesley Publishing Co.; 1984.
Aho, Alfred V.; Hopcroft, John E.; Ullman, Jefrrey D.: "The Design and Analysis of Computer Algorithms"; Addisson Wesley Publishing Co.; pp [329335]; 1974.
Baase Sara: "Computer Algorithms".
Hopcroft, J.; Ullman, J.: "Introduction to Automata Theory, Languages, and Computation". Addison-Wesley Publishing Co.; pp [1619]; 1979.
Horowitz, E.; Sahni, S.: "Fundamentals of Data Structures"; Computer Science Press; 1982.
Knuth, Donald: "The Art of Computer Programming, Vol. 1 Fundamental Algorithms"; Addison-Wesley; 1968.
Knuth, Donald: "The Art of Computer Programming, Vol. 3 Sorting and Searching"; Adisson-Wesley; 1971.
Kronsjo, Lydia: "Algorithms: Their complexity and efficiency".
Sedgewick, Robert: "Algorithms". Addison-Wesley, 1995
Wirth, Niklaus: "Algoritmos y Estructura de Datos"; Prentice Hall Hispanoamericana; México 1982.

$[/\]$

Examen Parcial #1 [29-set-1999]	25%	Proyecto #1	10%
Examen Final [3-dic-1999]	30%	Proyecto #2	10%
Tareas programadas	20%	Otros:	5%