Algoritmos y estructura de datos - catedra Buchwald - 2c 2021

• Durante toda la cursada se utilizo Linux, ya que era requisito de la materia, y por ello algunos programas tal vez no funcionen en Windows.
• En la materia se utilizo lenguaje C, excepto por el ultimo trabjo práctico que se realizo en Python.

Tipos de Datos Abstractos

• Todos realizados durante la cursada, algunos a partir solo de la definición de las primitivas.
• En algunos también se debian entregar con las correspondientes pruebas que muestren su correcto funcionamiento.
• TDA's realizados:
  • Vector dinámico
  • Pila dinámica
  • Cola enlazada
  • Lista enlazada
  • Hash
  • ABB
  • Heap

Trabajos Prácticos

• TP0: Repaso general de lenguaje C realizando el algoritmo de selección.
• TP1-Fixcol: El objetivo era manejar archivos y crear un programa que se le pasen parametros por consola. El programa consiste en dividir un texto en reglones según una cantidad máxima de caracteres pasadas por parametro.
• TP2-AlgoGram: El objetivo era crear una especie de red social simil Twitter utilizando las estructuras aprendidas y optimizando tiempos de complejidad.
• TP3-NetStats: El objetivo principal era la utilización de distintos tipos de grafos para la implementación de diferentes algoritmos como BFS, Page Rank, Label Propagation, Backtracking, etc. para la resolucion del TP.

Contenido Mínimo de la Asignatura

Complejidad computacional: cálculo de complejidad computacional para algoritmos iterativos y recursivos simples. División y Conquista, Teorema Maestro. Algoritmos de ordenamiento no comparativos. Abstracción en el diseño de estructuras de datos y tipos abstractos de datos. Análisis de implementaciones sobre estructuras en arreglo y estructuras enlazadas. Criterios de redimensión en estructuras en arreglo y análisis de complejidad amortizado. Estructuras de datos básicas: Vector, Pila, Cola, Listas enlazadas, diccionarios, tablas de Hashing y resolución de colisiones en tablas de hashing, árboles, árboles binarios de búsqueda, árboles autobalanceados, colas de prioridad. Grafos. Características y representaciones de grafos. Implementaciones eficientes de grafos. Recorridos BFS y DFS de grafos. Ordenamiento topológico. Algoritmos de cálculo de caminos mínimos en grafos. Algoritmos de cálculo de árboles de tendido mínimo.