CC30A Algoritmos y Estructuras de Datos

Sección 01, Semestre Otoño 2005

Objetivos del curso

Estudiar métodos de diseño de algoritmos y de desarrollo de programas. Conocer los principales algoritmos y estructuras de datos, incluyendo el análisis de su desempeño.

Temario

1. Métodos de programación y fundamentos matemáticos: invariantes, diagramas de estado, recursividad, dividir para reinar, nociones de análisis de algoritmos, planteamiento y resolución de ecuaciones de recurrencia, programación dinámica, conceptos de orientación a objetos.
2. Estructuras de datos básicas: arreglos, punteros, listas enlazadas, árboles.
3. Tipos de datos abstractos (TDA): concepto de encapsulamiento, listas, pilas, colas.
4. TDA diccionario: implementaciones simples, árboles de búsqueda binaria, árboles AVL, árboles 2-3, árboles B, árboles digitales, skip lists, hashing.
5. Ordenamiento: cota inferior, quicksort, heapsort, bucketsort, mergesort, ordenamiento externo.
6. Búsqueda en texto: método de fuerza bruta, Knuth-Morris-Pratt, Boyer-Moore.
7. Grafos: representación y recorrido, árbol cobertor mínimo, distancia mínima.
8. Algoritmos probabilísticos.

Evaluaciones

• 2 controles + 1 examen (corresponde a NC):
  • Control 1: viernes 22 de abril.
  • Control 2: viernes 10 de junio.
• 4 tareas + 1 tarea recuperativa (corresponde a NT).
• Para aprobar el curso se deben cumplir las siguientes condiciones: NC ≥ 4.0
  NT ≥ 4.0
  NF = (2/3)*NC + (1/3)*NT

Reglas del juego

• Reglas básicas de convivencia:
  • Apagar los celulares antes de entrar a clases.
  • Si alguien llega atrasado a clases: tratar de entrar sin interrumpir.
• Con respecto a las evaluaciones:
  • No habrá eximición.
  • La nota de examen reemplazará, en caso de ser mejor, a la peor nota de control.
  • Es necesario aprobar controles y tareas por separado.
  • Las tareas son INDIVIDUALES.
  • Cada tarea se compone de un código fuente (en lenguaje Java) y un informe escrito en LaTeX que debe seguir la pauta indicada.
  • Códigos que no compilen, códigos sin informes o informes sin código NO SERAN CORREGIDOS.
  • No se aceptarán tareas atrasadas.
  • Se evaluará principalmente la CORRECTITUD de su tarea, es decir, que haga bien lo que se pide que haga.
  • Debe haber concordancia entre el informe escrito y el código. Si no es posible obtener los resultados descritos en el informe a partir del código entregado, dicha tarea tendrá nota 1.0.
  • Sea cuidadoso en la redacción y ortografía de los informes, ya que también serán evaluados.
  • La tarea recuperativa reemplazará la nota de la peor tarea.
  • No habrá nota I.
  • Los alumnos podrán utilizar durante los controles y el exámen los apuntes del curso impresos y apuntes manuscritos.
• Etica profesional:
  • A todo alumno sorprendido en intento de engaño al cuerpo docente en alguna actividad evaluada, se le aplicará la normativa vigente en la Escuela.
  • Intento de engaño corresponde a: copiar y/o comprar tareas, copiar en las pruebas, utilizar apuntes no autorizados, etc.
  • Cuide sus tareas: no las deje grabadas en computadores compartidos, y proteja la carpeta de su cuenta en donde las almacena.
  • Se permite a los alumnos conversar y discutir libremente sobre las tareas, pero a la hora de sentarse a escribir el código y el informe respectivo deben hacerlo en forma individual.