{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CItwGnEDMlCR"
      },
      "source": [
        "#  **Pauta Auxiliar 4: Ecuaciones de Recurrencia y Teorema Maestro**\n",
        "\n",
        "### Profesores: Nelson Baloian, Benjamín Bustos, Sebastian Ferrada, Patricio Poblete\n",
        "### Auxiliares: Sebastián Acuña, Valentina Aravena, Vicente Olivares, Ricardo Valdivia"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B5CogT3yCCg2"
      },
      "source": [
        "## P1. Ecuaciones de Recurrencia"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2HN4N7BFi4Nh"
      },
      "source": [
        "### **Parte a**\n",
        "\n",
        "$$T(n) = 3T(n-1) + 4T(n-2) \\quad \\forall n \\geq 2$$\n",
        "$$T(0) = 1$$\n",
        "$$T(1) = 1$$"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Para resolver esta ecuación asumiremos que la solución es de la forma $T(n) = λ^n$. Entonces la ecuación pasa a ser:\n",
        "\n",
        "$$λ^n = 3λ^{n-1} +\\; 4λ^{n-2}$$\n",
        "$$⇒ λ^n - 3λ^{n-1} -\\; 4λ^{n-2} = 0$$\n",
        "\n",
        "Dividiendo ambos lados por $λ^{n-2}$ llegamos a la siguiente ecuación cuadrática:\n",
        "\n",
        "$$λ^2 - 3λ - 4 = 0$$\n",
        "Factorizando o utilizando la fórmula cuadrática obtenemos que $λ_1=4$ y $λ_2=-1$. Lo que significa que la solución de la ecuación de recurrencia es de la forma:\n",
        "\n",
        "$$T(n) = A \\cdot 4^n + B \\cdot (-1)^n$$\n",
        "Donde $A$ y $B$ son constantes que obtendremos con ayuda de las condiciones iniciales.\n",
        "$$T(0) = A + B = 1 \\quad ⟹ \\quad B = 1 - A$$\n",
        "$$T(1) = 4A + (1-A)(-1) = 1 \\quad ⟹ \\quad A = \\frac{2}{5} \\quad ⟹ \\quad B = \\frac{3}{5}$$\n",
        "$$ ⟹ T(n) = \\frac{2}{5} \\cdot 4^n + \\frac{3}{5} \\cdot (-1)^n$$"
      ],
      "metadata": {
        "id": "Emf9vvYJY3Cz"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### **Parte b**"
      ],
      "metadata": {
        "id": "RsVequCPpLpZ"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "\\begin{align*}\n",
        "X_{n+1}&=\\sqrt{X_n\\cdot X_{n-1}} \\\\\n",
        "X_0&=1 \\\\\n",
        "X_1&=2\n",
        "\\end{align*}\n",
        "Observemos que esta ecuación no es lineal, pero si tomamos logaritmo en ambos lados de la ecuación, ésta se linealiza:\n",
        "$$\\log_{2}(X_{n+1}) = \\frac{1}{2} \\left( \\log_{2}(X_n) + \\log_{2}(X_{n-1}) \\right)$$\n",
        "\n",
        "Ahora, si definimos $Y_n = \\log_{2}(X_n)$, la ecuación queda:\n",
        "$$Y_{n+1}-\\frac{1}{2}Y_n-\\frac{1}{2}Y_{n-1}=0$$\n",
        "\n",
        "\\noindent que es una ecuación lineal homogénea con coeficientes constantes. Obtenemos el polinomio característico\n",
        "$$\\lambda^{n + 1} - \\frac{1}{2}\\lambda^{n} - \\frac{1}{2}\\lambda^{n - 1} = 0$$\n",
        "\n",
        "Descartando la solución trivial ($\\lambda = 0$) y dividiendo ambos lados por $\\lambda^{n-1}$ se obtiene\n",
        "$$\\lambda^2-\\frac{1}{2}\\lambda-\\frac{1}{2}=0$$\n",
        "\n",
        "\\noindent cuyas raíces son $\\lambda_{1} = 1$ y $\\lambda_{2}= -\\frac{1}{2}$, por lo que la solución a la ecuación de recurrencia es de la forma\n",
        "$$Y_{n} = \\alpha \\cdot \\frac{-1}{2}^{n} + \\beta$$\n",
        "\n",
        "Revirtiendo el cambio de variables para calcular las constantes\n",
        "\\begin{align*}\n",
        "Y_0&=\\log_{2}(\\underbrace{X_0}_1)=0 \\\\\n",
        "Y_1&=\\log_{2}(\\underbrace{X_1}_2)=1\n",
        "\\end{align*}\n",
        "\n",
        "Con esto nos queda el sistema\n",
        "\\begin{align*}\n",
        "Y_0&=\\alpha+\\beta=0\\Rightarrow\\beta=-\\alpha \\\\\n",
        "Y_1&=-\\frac{\\alpha}{2}-\\alpha=1\\Rightarrow\\alpha=-\\frac{2}{3}\n",
        "\\end{align*}\n",
        "\n",
        "Así, la solución es\n",
        "$$Y_n=\\frac{2}{3} - \\frac{2}{3} \\left( \\frac{-1}{2} \\right)^n$$\n",
        "\n",
        "y al volver en el cambio de variable obtenemos la solución final a la ecuación de recurrencia original\n",
        "\n",
        "$$X_n = 2^{\\frac{2}{3} \\left( 1 - \\left( \\frac{-1}{2} \\right)^n \\right) }$$"
      ],
      "metadata": {
        "id": "FrQSx-JOpQuh"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d84QBFB2DQTr"
      },
      "source": [
        "## P2. Subarreglo de suma máxima"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### (a) Programe una solución que resuelva el problema, sin importar cuan eficiente es:\n",
        "Para está parte realizaremos un algoritmo utilizando la \"Fuerza bruta\", en este caso sería probando todas las posibles combinaciones."
      ],
      "metadata": {
        "id": "FWBkbGBj1vw7"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def Subarreglo_max_sum_FuerzaBruta(A):\n",
        "  maxSum = A[0]\n",
        "  maxIndex = [0,0]\n",
        "  for i in range(len(A)): # desde i = 0 hasta i = len(A)-1\n",
        "    for j in range(i,len(A)): # desde j = i hasta j = len(A)-1\n",
        "      thisSum = 0\n",
        "      for k in range(i, j+1): # desde k=i hasta k=j\n",
        "        thisSum += A[k]\n",
        "      if thisSum > maxSum:\n",
        "        maxSum = thisSum\n",
        "        maxIndex = [i,j]\n",
        "  return (maxSum, maxIndex)"
      ],
      "metadata": {
        "id": "iaRBXQIA2DZ0"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "A = [-2, -3, 4, -1, -2, 1, 5, -3]\n",
        "maxSum, maxIndex = Subarreglo_max_sum_FuerzaBruta(A)\n",
        "print(\"La suma máxima es\",maxSum)\n",
        "print(\"Los índices son\",maxIndex)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "K2V19uYiiXUZ",
        "outputId": "de4bb024-33ac-4e91-9f85-ed5519256edd"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "La suma máxima es 7\n",
            "Los índices son [2, 6]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Calculo de costo en notación Big-O\n",
        "\n",
        "$$ \\sum^{n-1}_{i=0} \\sum^{n-1}_{j=i} \\sum^j_{k=i} 1 = \\frac{n^3 + 3n^2 + 2n}{6} \\in \\Theta(n^3)$$\n"
      ],
      "metadata": {
        "id": "WhwmNs1O3nqI"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### (b) ¿Puede ser más eficiente la solución? Intente mejorar la solución anterior.\n",
        "Observando la solución anterior podemos notar lo siguiente:\n",
        " $$\\sum^j_{k=i}A_k = A_j + \\sum^{j-1}_{k=i}$$\n",
        "\n",
        "La sumatoria de los valores entre i y j se estaba realizando más veces de las necesarias.\n",
        "Mejorando la solución se tendrá el siguiente código:\n"
      ],
      "metadata": {
        "id": "b9fzNvU53ymV"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def Subarreglo_max_sum_FuerzaBruta_mejora(A):\n",
        "  maxSum = A[0]\n",
        "  maxIndex = [0,0]\n",
        "  for i in range(len(A)): # desde i = 0 hasta i = len(A)-1\n",
        "    thisSum = 0\n",
        "    for j in range(i,len(A)): # desde j = i hasta j = len(A)-1\n",
        "      thisSum += A[j]\n",
        "      if thisSum > maxSum:\n",
        "        maxSum = thisSum\n",
        "        maxIndex = [i,j]\n",
        "  return (maxSum, maxIndex)"
      ],
      "metadata": {
        "id": "TtoCSXfx5b5z"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "A = [-2, -3, 4, -1, -2, 1, 5, -3]\n",
        "maxSum, maxIndex = Subarreglo_max_sum_FuerzaBruta_mejora(A)\n",
        "print(\"La suma máxima es\",maxSum)\n",
        "print(\"Los índices son\",maxIndex)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "V1HLqwBgiv8h",
        "outputId": "3930fc9c-3322-4943-f82a-8068f7c38845"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "La suma máxima es 7\n",
            "Los índices son [2, 6]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Calculo de costo en notación Big-O\n",
        "\n",
        "$$ \\sum^{n-1}_{i=0} \\sum^{n-1}_{j=i}  1 = \\frac{n^2 + n}{2} \\in \\Theta(n^2)$$"
      ],
      "metadata": {
        "id": "rDLV8wnd6uqv"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### (c) Intente mejorar la solución anterior usando una estrategia dividir para reinar.\n"
      ],
      "metadata": {
        "id": "NyaJKhk-649E"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Vamos a dividir las posibles soluciones en 3:\n",
        "\n",
        "\n",
        "1.  La solución se encuentra en la PRIMERA mitad del arreglo.\n",
        "2.  La solución se encuentra en la SEGUNDA mitad del arreglo.\n",
        "3.  La solución se encuentra en medio del arreglo.\n",
        "\n",
        "Con esas posibles soluciones nuestro arreglo consistirá en obtener cada una y comparar cual de las 3 es mayor.\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "OflLLRzMbqjO"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def suma_maxima_dp(arr):\n",
        "  n = len(arr)\n",
        "  if n == 1: # caso base\n",
        "    return arr[0]\n",
        "  else:\n",
        "    # dividimos el arreglo en mitades\n",
        "    primera_mitad = arr[:n//2]\n",
        "    segunda_mitad = arr[n//2:]\n",
        "    MSMI = 0\n",
        "    MSMD = 0\n",
        "    TSMI = 0\n",
        "    TSMD = 0\n",
        "    for i in range(len(primera_mitad)-1,-1,-1):\n",
        "      #calculamos suma máxima de la derecha hacia el centro\n",
        "      TSMI += arr[i]\n",
        "      if TSMI > MSMI:\n",
        "        MSMI = TSMI\n",
        "    for i in range(len(primera_mitad),n):\n",
        "      #calculamos suma máxima de la izquierda hacia el centro\n",
        "      TSMD += arr[i]\n",
        "      if TSMD > MSMD:\n",
        "        MSMD = TSMD\n",
        "    maxSumMedio = MSMI + MSMD #suma máxima que pasa por el medio\n",
        "    return max(suma_maxima_dp(primera_mitad), suma_maxima_dp(segunda_mitad), maxSumMedio) # llamada recursiva"
      ],
      "metadata": {
        "id": "omzJiuoboBp5"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "A = [-2, -3, 4, -1, -2, 1, 5, -3]\n",
        "maxSum = suma_maxima_dp(A)\n",
        "print(\"La suma máxima es\",maxSum)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vSwnqEYui0SX",
        "outputId": "d5452eed-b5ab-43ca-824f-6b8b9b80e04f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "La suma máxima es 7\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Ahora para calcular el tiempo del algoritmo haremos lo siguiente:\n",
        "\n",
        "\n",
        "*   Sea $T(n)$ el tiempo que se demora en encontrar el subarrglo de suma máxima en un arreglo de tamaño n.\n",
        "\n",
        "Tendremos:\n",
        "$$ T(n) = T(\\frac{n}{2})+T(\\frac{n}{2}) + T_{maxSumDelMedio}$$\n",
        "\n",
        "Y el tiempo para encontrar la Suma máxima del medio sería el equivalente al siguiente procedimiento:\n",
        "\n",
        "\n",
        "*   Sumamos todos los valores de la primera mitad de derecha a izquierda, quedandonos con la suma máxima ($\\frac{n}{2}$ operaciones).\n",
        "*   Sumamos todos los valores de la segunda mitad de izquierda a derecha, quedandonos con la suma máxima ($\\frac{n}{2}$ operaciones).\n",
        "*   Juntamos ambos resultados y esa será la suma máxima que pasa por el medio. ($\\Theta(n)$)\n",
        "\n",
        "Finalmente:\n",
        "$$ T(n) = 2\\:T(\\frac{n}{2})+ \\Theta(n)$$\n",
        "Usando el Teorema maestro con ($p=2 \\:;\\: r=1 \\:;\\: q=2$) obtenemos que $T(n)$ es $\\Theta(n\\:log(n))$\n"
      ],
      "metadata": {
        "id": "XaUGYdtudFHF"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### (d) Sea aún más eficiente: Programe una solución que resuelva el problema en tiempo lineal\n",
        "Números negativo: No queremos que nuestra solución tenga números negativos (no queremos que la suma del subarreglo sea negativa).\n",
        "\n",
        "Recorreremos una vez el arreglo (solución lineal $\\Theta(n)$), e iremos sumando los valores en una variable, si es mayor a la suma máxima actual la actualizaremos, si es negativa no nos sirve y tendremos que reiniciar la variable."
      ],
      "metadata": {
        "id": "ewcUoroe691P"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def Subarreglo_Suma_Maxima_Lineal(A):\n",
        "  maxSum = 0\n",
        "  maxIndex = [0,0]\n",
        "  thisSum = 0\n",
        "  thisIndex = [0,0]\n",
        "  for j in range(len(A)):\n",
        "    thisSum += A[j]\n",
        "    if thisSum > maxSum:\n",
        "      maxSum = thisSum\n",
        "      maxIndex = thisIndex.copy()\n",
        "    elif thisSum < 0:\n",
        "      thisSum = 0\n",
        "      thisIndex[0] = thisIndex[1]\n",
        "    thisIndex[1] += 1\n",
        "  return (maxSum, maxIndex)\n"
      ],
      "metadata": {
        "id": "s11OME9q6uU8"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "A = [-2, -3, 4, -1, -2, 1, 5, -3]\n",
        "maxSum, maxIndex = Subarreglo_Suma_Maxima_Lineal(A)\n",
        "print(\"La suma máxima es\",maxSum)\n",
        "print(\"Los índices son\",maxIndex)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-kdLG47ijqEY",
        "outputId": "4bcceb4a-c6fa-468c-d180-a155c4865dc4"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "La suma máxima es 7\n",
            "Los índices son [1, 6]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Calculo de costo en notación Big-O\n",
        "\n",
        "$$ \\sum^{n-1}_{i=0}  1 = n \\in \\Theta(n)$$"
      ],
      "metadata": {
        "id": "O8XXroNe8HP0"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vsYm5N-5Cs5K"
      },
      "source": [
        "## P3. Teorema Maestro"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Recordemos que el **Teorema Maestro** nos dice que la ecuación\n",
        "\n",
        "$$\n",
        "T(n)=pT(\\frac{n}{q})+Cn^r\n",
        "$$\n",
        "\n",
        "tiene solución\n",
        "\n",
        "$$\n",
        "T(n) =\n",
        "\\begin{cases}\n",
        "\\Theta(n^r) & \\text{ si } p<q^r\\\\\n",
        "\\Theta(n^r \\log{n}) & \\text{ si } p=q^r\\\\\n",
        "\\Theta(n^{\\log_q{p}}) & \\text{ si } p>q^r\n",
        "\\end{cases}\n",
        "$$"
      ],
      "metadata": {
        "id": "b-I04dqOvT3P"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Tenemos los siguientes 3 algoritmos y buscamos minimizar el tiempo.\n",
        "\n",
        "* El algoritmo A resuelve el problema de tamaño $n$ dividiéndolo en cinco\n",
        "subproblemas de tamaño $\\frac{n}{2}$, resolviendo recursivamente cada subproblema y luego combinando las soluciones en tiempo lineal.\n",
        "    \n",
        "* El algoritmo B resuelve el problema de tamaño $n$ resolviendo recursivamente dos subproblemas de tamaño $n-1$ y realizando trabajo adicional a tiempo constante.\n",
        "\n",
        "* El algoritmo C resuelve el problema de tamaño $n$ dividiéndolo en nueve subproblemas de tamaño $\\frac{n}{3}$, resolviendo recursivamente cada subproblema y luego combinando las soluciones en tiempo $O(n^2)$."
      ],
      "metadata": {
        "id": "JSbdjNRZp-bi"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Como los tres mencionan recursión, podemos obtener las ecuaciones de recurrencia que siguen los costos de los algoritmos.\n",
        "\n",
        "#### Algoritmo A\n",
        "La descripción menciona que el algoritmo resuelve recursivamente 5 subproblemas de tamaño $\\frac{n}{2}$, por lo que el término $5T_A(\\frac{n}{2})$ estará presente en la ecuación. Además, se menciona que luego combinan las soluciones en tiempo lineal, es decir, en $O(n)$ que equivale a $kn$, siendo k una constante, entonces el término $kn$ también estará en la ecuación. Teniendo encuenta todo lo anterior, llegamos a que la ecuación de recurrencia del costo de este algoritmos es:\n",
        "$$T_A(n) = 5T_A(\\frac{n}{2}) + kn$$\n",
        "Podemos ver que $p=5 > 2^1 = q^r$, por lo que por Teorema Maestro $T_A(n) = Θ(n^{log_2(5)})$."
      ],
      "metadata": {
        "id": "KjmsJ9xMsHFJ"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Algoritmo B\n",
        "\n",
        "La descripción menciona que el algoritmo resuelve recursivamente 2 subproblemas de tamaño $n-1$, por lo que el término $2T_B(n-1)$ estará presente en la ecuación. Además, se menciona que luego combinan las soluciones en tiempo constante, es decir, en $O(1)$ que equivale a $k$, siendo k una constante, entonces el término $k$ también estará en la ecuación. Teniendo encuenta todo lo anterior, llegamos a que la ecuación de recurrencia del costo de este algoritmos es:\n",
        "$$T_B(n) = 2T_B(n-1) + k$$\n",
        "\n",
        "Podemos ver que en este caso no es posible aplicar el teorema maestro, pues no podemos identificar el valor de $q$. Sin embargo, observando el problema que se plantea este es bastante similar al ejemplo del número de movidas en las Torres de Hanoi ($a_n=2a_{n-1}+1$).\n",
        "\n",
        "Resolveremos este caso utilizando la Resolución de Ecuaciones Lineales de Primer Orden.\n",
        "$$ a_n = ba_{n-1}+c_n$$\n",
        "La que nos da cómo resultado:\n",
        "$$ a_n = a_0b^n+\\sum_{1\\leq k\\leq n}c_kb^{n-k}$$\n",
        "En nuestro caso $c_k=constante$, $b=2$, $a_0=constante$, por lo que se tendrá:\n",
        "$$ a_n = a_02^n+\\sum_{1\\leq k\\leq n}c\\:2^{n-k}$$\n",
        "\n",
        "$$ a_n = a_02^n+c\\:\\sum_{1\\leq k\\leq n-1}2^{k}$$\n",
        "\n",
        "$$ a_n = a_02^n+c\\:(2^n-1)$$\n",
        "\n",
        "Finalmente se tendría que el tiempo es: $\\Theta(a_02^n+c\\:(2^n-1))$ como $a_0$ y $c$ son constantes:\n",
        "\n",
        "$$\\Theta(a_02^n+c\\:(2^n-1)) \\in \\Theta(2^n)$$"
      ],
      "metadata": {
        "id": "sFMhsfxhy8fM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Algoritmo C\n",
        "\n",
        "La descripción menciona que el algoritmo resuelve recursivamente 9 subproblemas de tamaño $\\frac{n}{3}$, por lo que el término $9T_C(\\frac{n}{3})$ estará presente en la ecuación. Además, se menciona que luego combinan las soluciones en tiempo cuadrático, es decir, en $O(n^2)$ que equivale a $kn^2$, siendo k una constante, entonces el término $kn^2$ también estará en la ecuación. Teniendo encuenta todo lo anterior, llegamos a que la ecuación de recurrencia del costo de este algoritmos es:\n",
        "$$T_C(n) = 9T_C(\\frac{n}{3}) + kn^2$$\n",
        "Podemos ver que $p=9 = 3^2 = q^r$, por lo que por Teorema Maestro $T_C(n) = Θ(n^2 {log(n)})$."
      ],
      "metadata": {
        "id": "sRM5eREby_Lw"
      }
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}