=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
2024/2025
Ejercicio 14 del Tema 5.3 (opciona)
Borrador
=================================================================


(a) Algoritmo recursivo eficiente empleando Programacion Dinamica
=================================================================

En este pseudocodigo suponemos que los argumentos de tipo secuencia y
matriz se pasan por referencia y se indexan desde 0. Si x es de tipo
secuencia su longitud es x.longitud() y sus elementos van desde x[0]
hasta x[x.longitud() - 1].

________________________________________________________________________________________________________________
entero sequenceAlignment(secuencia X, secuencia Y) :

   Crear una matriz resultado de dimensiones (X.longitud() + 1) x (Y.longitud() + 1)
   Inicializar resultado con -1 en todas sus celdas
   devolver sequenceAlignment(X, Y, 0, 0, resultado)

________________________________________________________________________________________________________________
entero sequenceAlignment(secuencia X, secuencia Y, entero posicionX, entero posicionY, matriz resultado) :

   si resultado[posicionX][posicionY] == -1 :

      si posicionX == X.longitud() y posicionY == Y.longitud() :
         resultado[posicionX][posicionY] = 0

      sino si posicionX == X.longitud() :
         resultado[posicionX][posicionY] = 2 + sequenceAlignment(X, Y, posicionX, posicionY + 1, resultado)

      sino si posicionY == Y.longitud() :
         resultado[posicionX][posicionY] = 2 + sequenceAlignment(X, Y, posicionX + 1, posicionY, resultado)

      sino :
         si X[posicionX] == Y[posicionY] :
            p = 0
         sino :
            p = 1
         resultado[posicionX][posicionY] = min(2 + sequenceAlignment(X, Y, posicionX, posicionY + 1, resultado),
                                               2 + sequenceAlignment(X, Y, posicionX + 1, posicionY, resultado),
                                               p + sequenceAlignment(X, Y, posicionX + 1, posicionY + 1, resultado))

   devolver resultado[posicionX][posicionY]
________________________________________________________________________________________________________________


(b) Algoritmo no recursivo eficiente empleando Programacion Dinamica
====================================================================
__________________________________________________________________________________________
entero sequenceAlignment(secuencia X, secuencia Y) :

   Crear una matriz resultado de dimensiones (X.longitud() + 1) x (Y.longitud() + 1)

   para posicionX decreciendo desde X.longitud() hasta 0:

      para posicionY decreciendo desde Y.longitud() hasta 0 :

         si posicionX == X.longitud() y posicionY == Y.longitud() :
            resultado[posicionX][posicionY] = 0

         sino si posicionX == X.longitud() :
            resultado[posicionX][posicionY] = 2 + resultado[posicionX][posicionY + 1]

         sino si posicionY == Y.longitud() :
            resultado[posicionX][posicionY] = 2 + resultado[posicionX + 1][posicionY]

         sino :
            si X[posicionX] == Y[posicionY] :
               p = 0
            sino :
               p = 1
            resultado[posicionX][posicionY] = min(2 + resultado[posicionX][posicionY + 1],
                                                  2 + resultado[posicionX + 1][posicionY],
                                                  p + resultado[posicionX + 1][posicionY + 1])

   devolver resultado[0][0]
__________________________________________________________________________________________


(c) Coste temporal y espacial de ambos algoritmos
=================================================

O(n m) siendo n y m las longitudes de las dos secuencias dadas.