🇪🇸 Español | 🇬🇧 English

---

Algorítmica

Curso 2019-2020, Grado en Ingeniería Informática, ETSIIT UGR.

Introducción

El apartado práctico de la asignatura se repartió en 5 entregas, cada una de ellas exceptuando la primera se centró en la resolución de uno o varios problemas haciendo uso de un método de diseño de algoritmos diferente. Las prácticas fueron realizadas en equipo junto a José María Gómez García, Fernando Lojano Mayaguari y Carlos Mulero Haro.

Compilación

Los programas fueron realizados y probados tanto en Ubuntu 18+ como en Windows 10 con Cygwin.

Para compilar un programa se debe hacer uso del makefile incluído en la carpeta.

Contenido

Práctica 1: Análisis de Eficiencia de los Algoritmos

• Análisis Teórico, Empírico e Híbrido de la Eficiencia de
  • Bubblesort
  • Insertion Sort
  • Selection Sort
  • Mergesort
  • Quicksort
  • Heapsort
  • Algoritmo de Floyd
  • Algoritmo de las Torres de Hanoi

Práctica 2: Divide y Vencerás

• Problema general: Matriz Traspuesta
• Problema asignado: Eliminar elementos repetidos de un vector

Práctica 3: Greedy

• Problema general: El Problema del Viajante de Comercio
  • Basado en Cercanía
  • Basado en Insersión
  • Basado en Aristas
• Problema asignado: Asignación de tareas

Práctica 4: Programación Dinámica

• Problema general: El Problema del Viajante de Comercio

Práctica 5: Backtracking y Branch And Bound

• Problema general: El Problema del Viajante de Comercio
  • Basado en Backtracking
  • Basado en Branch and Bound
• Problema asignado: Estación de ITV

---

Algorithmics

2019-2020 Course, Computer Science Engineering Degree, ETSIIT UGR.

Introduction

The practical side of this course was divided in 5 practical sessions, each one of them except the first one was centered on the resolution of one or many problems making use of a different algorithm design paradigm. These sessions where made in a team with José María Gómez García, Fernando Lojano Mayaguari and Carlos Mulero Haro.

Compilation

The programs where made and tested in Ubuntu 18+ and Windows 10 with Cygwin.

The programs can be easily compiled with the makefile included in the folder.

Contents

Practical Session 1: Algorithm Efficiency Analysis

• Theoretical, Empirical and Hybrid Efficiency of
  • Bubblesort
  • Insertion Sort
  • Selection Sort
  • Mergesort
  • Quicksort
  • Heapsort
  • Floyd's Algorithm
  • Tower of Hanoi Algorithm

Practical Session 2: Divide and Conquer

• General problem: Matrix transpose
• Assigned problem: Delete repeated elements in a vector

Practical Session 3: Greedy

• General problem: Travelling Salesman Problem
  • Based on Nearest Neighbour
  • Based on Insertion
  • Based on Edges
• Assigned problem: Task assignment

Practical Session 4: Dynamic Programming

• General problem: Travelling Salesman Problem

Practical Session 5: Backtracking and Branch And Bound

• General problem: Travelling Salesman Problem
  • Based on Backtracking
  • Based on Branch and Bound
• Assigned problem: Vehicle Inspection Station