Advanced_Algos.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Advanced_Algos.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# **Maximum Subarray Problem**"
      ],
      "metadata": {
        "id": "YugE0phoIxUb"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import math\n",
        "import timeit\n",
        "import numpy as np\n",
        "\n",
        "#arr = [int(item) for item in input(\"Enter the list items : \").split()]\n",
        "arr = [-2,-5,6,-2,-3,1,5,-6]"
      ],
      "metadata": {
        "id": "gwwm01aLjunA"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Brute Force**"
      ],
      "metadata": {
        "id": "EtrRENs18150"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def maxSubArraySum(nums):\n",
        "    def solve(i, must_pick):\n",
        "        if i >= len(nums):\n",
        "           return 0 if must_pick else -2147483648\n",
        "        return max(nums[i] + solve(i+1, True), 0 if must_pick else solve(i+1, False))\n",
        "    return solve(0, False)\n",
        "\n",
        "st= timeit.timeit()\n",
        "print(\"Maximum contiguous sum is:\",maxSubArraySum(arr))\n",
        "end= timeit.timeit()\n",
        "print (\"The Execution Time:\",np.abs((end-st)*1000),str(\"milliseconds\"))\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-HXj95VC81gL",
        "outputId": "e1f96b67-adb5-49e6-cd79-a9028fd8d055"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Maximum contiguous sum is: 7\n",
            "The Execution Time: 4.548508999960177 milliseconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Kadane's Algorithm**"
      ],
      "metadata": {
        "id": "TReRmeR37pJy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "max_so_far = arr[0]\n",
        "curr_max = arr[0]\n",
        "\n",
        "def maxSubArraySum(arr,i,n,max_so_far,curr_max):\n",
        "    if i >= n:\n",
        "        print(\"Maximum contiguous sum is:\",max_so_far)\n",
        "        return   \n",
        "    curr_max = max(arr[i], curr_max + arr[i])\n",
        "    max_so_far = max(max_so_far,curr_max)\n",
        "    maxSubArraySum(arr,i+1,n,max_so_far,curr_max)\n",
        "\n",
        "st= timeit.timeit()\n",
        "maxSubArraySum(arr,1,len(arr),max_so_far,curr_max)\n",
        "end= timeit.timeit()\n",
        "print (\"The Execution Time:\",np.abs((end-st)*1000),str(\"milliseconds\"))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Y9QspE0sqNQD",
        "outputId": "8067c859-f23b-4f4b-8f39-8b27c2108ccc"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Maximum contiguous sum is: 7\n",
            "The Execution Time: 2.63337399996999 milliseconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Dynamic Programming - Tabulation**"
      ],
      "metadata": {
        "id": "HurkTXJ-JEqR"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def maxSubArray(nums):\n",
        "        dp = [[0]*len(nums) for i in range(2)]\n",
        "        dp[0][0], dp[1][0] = nums[0], nums[0]\n",
        "        for i in range(1, len(nums)):\n",
        "            dp[1][i] = max(nums[i], nums[i] + dp[1][i-1])\n",
        "            dp[0][i] = max(dp[0][i-1], dp[1][i])\n",
        "        return dp[0][-1]\n",
        "\n",
        "st= timeit.timeit()\n",
        "print(\"Maximum contiguous sum is:\",maxSubArray(arr))\n",
        "end= timeit.timeit()\n",
        "print (\"The Execution Time:\",np.abs((end-st)*1000),str(\"milliseconds\"))\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "S04qyqu5HHQ6",
        "outputId": "8834bd00-26bf-4de7-be6d-103228e2a749"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Maximum contiguous sum is: 7\n",
            "The Execution Time: 2.8778549999515235 milliseconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Divide and Conquer Algorithm**"
      ],
      "metadata": {
        "id": "tIG83S2aiQHB"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def maximumsumsub(a,l=None,r=None ):\n",
        "    \n",
        "    if(l==None and r== None):\n",
        "        l=0\n",
        "        r=len(a)-1   \n",
        "    if(r==l):  \n",
        "        return a[l] \n",
        "    m=math.floor((l+r)/2)\n",
        "    lmax=-99999\n",
        "    suum=0\n",
        "    for i in range(m,l,-1):\n",
        "        suum+=a[i]\n",
        "        if(suum>lmax):\n",
        "            lmax=suum\n",
        "    rmax=-99999\n",
        "    suum=0\n",
        "    for i in range(m+1,r+1):\n",
        "        suum+= a[i]\n",
        "        if(suum>rmax):\n",
        "            rmax=suum    \n",
        "    maxlr=max(maximumsumsub(a,l,m),maximumsumsub(a,m+1,r))\n",
        "    return max(lmax+rmax,maxlr)\n",
        "\n",
        "st= timeit.timeit()\n",
        "print(\"Maximum contiguous sum is:\",maximumsumsub(arr))\n",
        "end= timeit.timeit()\n",
        "print (\"The Execution Time:\",np.abs((end-st)*1000),str(\"milliseconds\"))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kMT9J6MMiNzD",
        "outputId": "f3f2d149-60b0-47f0-fc89-de844c85f75f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Maximum contiguous sum is: 7\n",
            "The Execution Time: 1.2580850000176724 milliseconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# **knapsack problem**"
      ],
      "metadata": {
        "id": "TuRknWaoO39G"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Brute-Force Algorithm**"
      ],
      "metadata": {
        "id": "x0x5EjvcQ3ah"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def knapSack(W, wt, val, n):\n",
        "\n",
        "    # Base Case\n",
        "    if n == 0 or W == 0:\n",
        "        return 0\n",
        "    if (wt[n-1] > W):\n",
        "        return knapSack(W, wt, val, n-1)\n",
        "    else:\n",
        "        return max(\n",
        "            val[n-1] + knapSack(\n",
        "                W-wt[n-1], wt, val, n-1),\n",
        "            knapSack(W, wt, val, n-1))\n",
        "        \n",
        "Gifts = [60, 100, 120]\n",
        "Weights = [10, 20, 30]\n",
        "Req_W = 50\n",
        "n = len(Gifts)\n",
        "st= timeit.timeit()\n",
        "print (knapSack(Req_W, Weights, Gifts, n))\n",
        "end= timeit.timeit()\n",
        "print (\"The Execution Time:\",np.abs((end-st)*1000),str(\"milliseconds\"))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "AAb64zShQr7F",
        "outputId": "cb16a2eb-bd17-4fbd-dce2-90be0e300085"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "220\n",
            "The Execution Time: 4.963520999808679 milliseconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Dynamic Programming**"
      ],
      "metadata": {
        "id": "Ib_N4LV7Rhws"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def knapSack(W, wt, val, n):\n",
        "    A = [[0 for x in range(W + 1)] for x in range(n + 1)]\n",
        "\n",
        "    # Build table K[][] in bottom up manner\n",
        "    for i in range(n + 1):\n",
        "        for w in range(W + 1):\n",
        "            if i == 0 or w == 0:\n",
        "                A[i][w] = 0\n",
        "            elif wt[i-1] <= w:\n",
        "                A[i][w] = max(val[i-1]\n",
        "                          + A[i-1][w-wt[i-1]],  \n",
        "                              A[i-1][w])\n",
        "            else:\n",
        "                A[i][w] = A[i-1][w]\n",
        "\n",
        "    return A[n][W]\n",
        "\n",
        "Gifts = [60, 100, 120]\n",
        "Weights = [10, 20, 30]\n",
        "Req_W = 50\n",
        "n = len(Gifts)\n",
        "st= timeit.timeit()\n",
        "print(knapSack(Req_W, Weights, Gifts, n))\n",
        "end= timeit.timeit()\n",
        "print (\"The Execution Time:\",np.abs((end-st)*1000),str(\"milliseconds\"))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4PG__DFTRmEK",
        "outputId": "244be972-8edb-49a9-9d03-6a127d05278a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "220\n",
            "The Execution Time: 0.22539899964613141 milliseconds\n"
          ]
        }
      ]
    }
  ]
}