algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sorting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "lst = [50,30,1,6,40,20,77,100,88,4,16,41]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Selection Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(lst):\n",
    "    if not lst:\n",
    "        return []\n",
    "    for i in range(len(lst) - 1):\n",
    "        smallest = i\n",
    "        for j in range(i, len(lst)):\n",
    "            if lst[j] < lst[smallest]:\n",
    "                smallest = j\n",
    "        lst[i], lst[smallest] = lst[smallest], lst[i]\n",
    "    return lst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 6, 16, 20, 30, 40, 41, 50, 77, 88, 100]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "selection_sort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bubble Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(lst):\n",
    "    if lst == []:\n",
    "        return []\n",
    "    for i in range(len(lst)):\n",
    "        for j in range(1, len(lst) - i):\n",
    "            if lst[j-1] > lst[j]:\n",
    "                lst[j-1], lst[j] = lst[j], lst[j-1]\n",
    "    return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 6, 16, 20, 30, 40, 41, 50, 77, 88, 100]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bubble_sort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Insertion Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(lst):\n",
    "    if not lst:\n",
    "        return []\n",
    "    for i in range(1,len(lst)):\n",
    "        j = i\n",
    "        while j > 0 and lst[j] < lst[j-1]:\n",
    "            lst[j],lst[j-1] = lst[j-1],lst[j]\n",
    "            j -= 1\n",
    "            \n",
    "    return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 6, 16, 20, 30, 40, 41, 50, 77, 88, 100]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insertion_sort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shell Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "def shell_sort(lst):\n",
    "    if not lst:\n",
    "        return []\n",
    "    h = math.ceil(len(lst)/3)\n",
    "    while h >= 1:\n",
    "        for i in range(h, len(lst)):\n",
    "            j = i\n",
    "            while j >= h and lst[j] < lst[j-h]:\n",
    "                lst[j], lst[j-h] = lst[j-h], lst[j]\n",
    "                j -= h\n",
    "        h -= 1\n",
    "    \n",
    "    return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 6, 16, 20, 30, 40, 41, 50, 77, 88, 100]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shell_sort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Merge Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort(lst):\n",
    "    if not lst:\n",
    "        return []\n",
    "    if len(lst) == 1:\n",
    "        return lst\n",
    "    mid = len(lst) // 2\n",
    "    left = merge_sort(lst[:mid])\n",
    "    right = merge_sort(lst[mid:])\n",
    "    return merge(left, right)\n",
    "\n",
    "def merge(left, right):\n",
    "    l, r, res = 0, 0, []\n",
    "    while l < len(left) and r < len(right):\n",
    "        if left[l] < right[r]:\n",
    "            res.append(left[l])\n",
    "            l += 1\n",
    "        else:\n",
    "            res.append(right[r])\n",
    "            r += 1\n",
    "    return res + left[l:] + right[r:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 6, 16, 20, 30, 40, 41, 50, 77, 88, 100]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "merge_sort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quick Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "def quick_sort(lst):\n",
    "    if not lst:\n",
    "        return []\n",
    "    random.shuffle(lst)\n",
    "    pivot = lst[0]\n",
    "    left = quick_sort([x for x in lst[1:] if x <= pivot])\n",
    "    right = quick_sort([x for x in lst[1:] if x > pivot])\n",
    "    return left + [pivot] + right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 6, 16, 20, 30, 40, 41, 50, 77, 88, 100]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quick_sort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Heap Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sift_down(lst,idx,end):\n",
    "    while 2*idx <= end:\n",
    "        child = 2 * idx\n",
    "        if child+1 <= end and lst[child+1] > lst[child]:\n",
    "            child = child + 1\n",
    "        if lst[idx] < lst[child]:\n",
    "            lst[idx], lst[child] = lst[child], lst[idx]\n",
    "            idx = child\n",
    "        else:\n",
    "            break\n",
    "            \n",
    "def heap_sort(lst):\n",
    "    if not lst:\n",
    "        return []\n",
    "    lst = [None] + lst\n",
    "    idx = (len(lst) - 1) // 2\n",
    "    while idx > 0:\n",
    "        sift_down(lst,idx,len(lst)-1)\n",
    "        idx -= 1\n",
    "    end = len(lst) - 1\n",
    "    while end > 1:\n",
    "        lst[1], lst[end] = lst[end], lst[1]\n",
    "        end -= 1\n",
    "        sift_down(lst,1,end)\n",
    "        \n",
    "    return lst[1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 6, 16, 20, 30, 40, 41, 50, 77, 88, 100]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap_sort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Counting Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def counting_sort(lst):\n",
    "    if not lst:\n",
    "        return []\n",
    "    max_lst = max(lst)\n",
    "    min_lst = min(lst)\n",
    "    count_arr_len = max_lst - min_lst + 1\n",
    "    count_arr = [0] * count_arr_len\n",
    "    for i in lst:\n",
    "        count_arr[i-min_lst] += 1\n",
    "    for i in range(1,count_arr_len):\n",
    "        count_arr[i] = count_arr[i] + count_arr[i-1]\n",
    "        \n",
    "    res = [0] * len(lst)\n",
    "    for i in range(len(lst)-1,-1,-1):\n",
    "        res[count_arr[lst[i]-min_lst]-1] = lst[i]\n",
    "        count_arr[lst[i]-min_lst] -= 1\n",
    "        \n",
    "    return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 6, 16, 20, 30, 40, 41, 50, 77, 88, 100]"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counting_sort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bucket Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "def bucket_sort(lst,bucket_size):\n",
    "    if not lst:\n",
    "        return []\n",
    "    \n",
    "    max_lst = max(lst)\n",
    "    min_lst = min(lst)\n",
    "    \n",
    "    bucket_count = math.floor((max_lst-min_lst)/bucket_size)+1\n",
    "    buckets = []\n",
    "    for i in range(bucket_count):\n",
    "        buckets.append([])\n",
    "    \n",
    "    for i in lst:\n",
    "        j = math.floor((i-min_lst)/bucket_size)\n",
    "        buckets[j].append(i)\n",
    "        \n",
    "    res = []\n",
    "    for bucket in buckets:\n",
    "        res_comp = quick_sort(bucket)\n",
    "        res.append(res_comp)\n",
    "    res = [j for i in res for j in i]\n",
    "    \n",
    "        \n",
    "    return res\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 6, 16, 20, 30, 40, 41, 50, 77, 88, 100]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bucket_sort(lst,25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Searching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linear Search "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "def linear_search(lst,elem):\n",
    "    lst_len = len(lst)\n",
    "    for i in range(lst_len):\n",
    "        if lst[i] == elem:\n",
    "            return i\n",
    "        \n",
    "    return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "linear_search(lst,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(lst,elem):\n",
    "    lst_sorted = sorted(lst)\n",
    "    lo = 0\n",
    "    hi = len(lst) - 1\n",
    "    while lo <= hi:\n",
    "        mid = (lo + hi) // 2\n",
    "        if elem == lst[mid]:\n",
    "            return mid\n",
    "        elif elem > mid:\n",
    "            lo = mid + 1\n",
    "        else:\n",
    "            hi = mid - 1\n",
    "    \n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "binary_search(lst,20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## String-Based Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pattern Matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Given a text $txt[0..n-1]$ and a pattern $pat[0..m-1]$, write a function that prints all occurrences of $pat$ in $txt$. \n",
    "\n",
    "You may assume that $n > m$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### BF Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BF(pat,txt):\n",
    "    M = len(pat)\n",
    "    N = len(txt)\n",
    "    idx_l = []\n",
    "    for i in range(N-M+1):\n",
    "        j = 0\n",
    "        while(j < M):\n",
    "            if txt[i+j] != pat[j]:\n",
    "                break\n",
    "            j += 1\n",
    "        if j == M:\n",
    "            idx_l.append(i)\n",
    "    \n",
    "    return idx_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found pattern at index: [10, 15, 22]\n"
     ]
    }
   ],
   "source": [
    "txt = \"ABABDABACDABABCABABCABABABCABAB\"\n",
    "pat = \"ABABCABAB\"\n",
    "print('Found pattern at index:',BF(pat,txt))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Finite-Automata Algorithm "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_next_state(pat, M, state, c): \n",
    "    if state < M and c == ord(pat[state]): \n",
    "        return state+1\n",
    "    i=0\n",
    "    for ns in range(state,0,-1): \n",
    "        if ord(pat[ns-1]) == c: \n",
    "            while(i<ns-1): \n",
    "                if pat[i] != pat[state-ns+1+i]: \n",
    "                    break\n",
    "                i+=1\n",
    "            if i == ns-1: \n",
    "                return ns  \n",
    "    return 0\n",
    "\n",
    "def build_FA(pat, M):   \n",
    "    FA_table = [[0 for i in range(256)] for j in range(M+1)]   # number of characters is 256\n",
    "    for state in range(M+1): \n",
    "        for c in range(256): \n",
    "            ns = get_next_state(pat,M,state,c) \n",
    "            FA_table[state][c] = ns \n",
    "  \n",
    "    return FA_table \n",
    "\n",
    "def FA(pat,txt):\n",
    "    idx_l = []\n",
    "    M = len(pat) \n",
    "    N = len(txt) \n",
    "    FA_table = build_FA(pat, M)     \n",
    "    state=0\n",
    "    for i in range(N): \n",
    "        state = FA_table[state][ord(txt[i])] \n",
    "        if state == M: \n",
    "            idx_l.append(i-M+1)\n",
    "    \n",
    "    return idx_l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found pattern at index: [10, 15, 22]\n"
     ]
    }
   ],
   "source": [
    "txt = \"ABABDABACDABABCABABCABABABCABAB\"\n",
    "pat = \"ABABCABAB\"\n",
    "print('Found pattern at index:',FA(pat,txt))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### KMP Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def KMP(pat,txt):\n",
    "    M = len(pat)\n",
    "    N = len(txt)\n",
    "    j = 0\n",
    "    lps = get_LPS(pat,M)\n",
    "    i = 0\n",
    "    idx_l = []\n",
    "    while i < N:\n",
    "        if pat[j] == txt[i]:\n",
    "            i += 1\n",
    "            j += 1\n",
    "        if j == M:\n",
    "            idx_l.append(i-j)\n",
    "            j = lps[j-1]\n",
    "        elif i < N and pat[j] != txt[i]:\n",
    "            if j != 0:\n",
    "                j = lps[j-1]\n",
    "            else:\n",
    "                i += 1\n",
    "                \n",
    "    return idx_l\n",
    "            \n",
    "def get_LPS(pat,M):\n",
    "    lps = [0] * M\n",
    "    l = 0\n",
    "    i = 1\n",
    "    while i < M:\n",
    "        if pat[i] == pat[l]:\n",
    "            l += 1\n",
    "            lps[i] = l\n",
    "            i += 1\n",
    "        else:\n",
    "            if l != 0:\n",
    "                l = lps[l-1]\n",
    "            else:\n",
    "                lps[i] = 0\n",
    "                i += 1        \n",
    "    return lps\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found pattern at index: [10, 15, 22]\n"
     ]
    }
   ],
   "source": [
    "txt = \"ABABDABACDABABCABABCABABABCABAB\"\n",
    "pat = \"ABABCABAB\"\n",
    "print('Found pattern at index:',KMP(pat,txt))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Wildcard Pattern Matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Given a text and a wildcard pattern, check if the wildcard pattern is matched with text. \n",
    "\n",
    "The wildcard pattern can include the characters $?$ and $*$\n",
    "\n",
    "$?$ – matches with any single character \n",
    "\n",
    "$*$ – matches with any sequence of characters (including the empty sequence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def wildcard_matching(txt,pat):\n",
    "    N = len(txt)\n",
    "    M = len(pat)\n",
    "    \n",
    "    if (M == 0):\n",
    "        return (N == 0)\n",
    " \n",
    "    T = [[False for i in range(M+1)] for j in range(N+1)]\n",
    " \n",
    "    T[0][0] = True\n",
    "    \n",
    "    for j in range(1,M+1):\n",
    "        if pat[j-1] == '*':\n",
    "            T[0][j] = T[0][j-1]\n",
    "            \n",
    "    for i in range(1,N+1):\n",
    "        for j in range(1,M+1):\n",
    "            if (pat[j-1] == '*'):\n",
    "                T[i][j] = T[i][j-1] or T[i-1][j]\n",
    "            elif (pat[j-1] == '?' or txt[i-1] == pat[j-1]):\n",
    "                T[i][j] = T[i-1][j-1]\n",
    "            else:\n",
    "                T[i][j] = False\n",
    " \n",
    "    return T[N][M]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "baaabab matches with b*b : True\n",
      "baaabab matches with *aa* : True\n",
      "baaabab matches with b?b : False\n",
      "baaabab matches with baa?b* : True\n"
     ]
    }
   ],
   "source": [
    "txt = 'baaabab'\n",
    "pat1 = 'b*b'\n",
    "pat2 = '*aa*'\n",
    "pat3 = 'b?b'\n",
    "pat4 = 'baa?b*'\n",
    "print(txt,'matches with',pat1,':',wildcard_matching(txt,pat1))\n",
    "print(txt,'matches with',pat2,':',wildcard_matching(txt,pat2))\n",
    "print(txt,'matches with',pat3,':',wildcard_matching(txt,pat3))\n",
    "print(txt,'matches with',pat4,':',wildcard_matching(txt,pat4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Longest Palindromic Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Given a string, find the longest substring which is palindrome."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Manacher Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Manacher(s):\n",
    "    s_ext = '#' + '#'.join(list(s)) + '#'\n",
    "    s_len = len(s_ext)\n",
    "    lps = [0] * s_len\n",
    "    C = R = 0\n",
    "    for idx in range(1, s_len-1):\n",
    "        i_mirror = 2 * C - idx\n",
    "        if idx >= R:\n",
    "            while (idx+1+lps[idx] < s_len and idx-1-lps[idx] >= 0 and s_ext[idx+1+lps[idx]] == s_ext[idx-1-lps[idx]]):\n",
    "                lps[idx] += 1\n",
    "        else:\n",
    "            if lps[i_mirror] < R - idx:\n",
    "                lps[idx] = lps[i_mirror]\n",
    "            elif lps[i_mirror] == R - idx: \n",
    "                lps[idx] = lps[i_mirror]\n",
    "                while (idx+1+lps[idx] < s_len and idx-1-lps[idx] >= 0 and s_ext[idx+1+lps[idx]] == s_ext[idx-1-lps[idx]]):\n",
    "                    lps[idx] += 1\n",
    "            else:\n",
    "                lps[idx] = R - idx\n",
    "                \n",
    "        if idx + lps[idx] > R:\n",
    "            C = idx\n",
    "            R = idx + lps[idx]\n",
    "\n",
    "    idx = lps.index(max(lps))\n",
    "    start = (idx - lps[idx]) // 2\n",
    "\n",
    "    return s[start: start+lps[idx]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Longest palindromic substring of \"abbabab\": babab\n"
     ]
    }
   ],
   "source": [
    "print('Longest palindromic substring of \"abbabab\":',Manacher('abbabab'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Edit Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two strings $s1$ and $s2$ and below operations that can be performed on $s2$.\n",
    "\n",
    "Find the minimum number of edits (operations) required to convert $s1$ into $s2$.\n",
    "* Insert\n",
    "* Remove\n",
    "* Replace\n",
    "\n",
    "All of the above operations are of equal cost."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def edit_distance(s1,s2):\n",
    "    M = len(s1)\n",
    "    N = len(s2)\n",
    "    T = [[0 for i in range(M+1)] for j in range(N+1)]\n",
    "    for i in range(M+1):\n",
    "        T[0][i] = i\n",
    "    for i in range(N+1):\n",
    "        T[i][0] = i\n",
    "    \n",
    "    for i in range(1,N+1):\n",
    "        for j in range(1,M+1):\n",
    "            if s1[j-1] == s2[i-1]:\n",
    "                T[i][j] = min(T[i][j-1]+1,T[i-1][j]+1,T[i-1][j-1])\n",
    "            else:\n",
    "                T[i][j] = min(T[i][j-1]+1,T[i-1][j]+1,T[i-1][j-1]+1)\n",
    "    \n",
    "    return T[N][M]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Edit distance: 3\n"
     ]
    }
   ],
   "source": [
    "s1 = 'Sunday'\n",
    "s2 = 'Saturday'\n",
    "print('Edit distance:',edit_distance(s1,s2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Greedy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Change-making Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: You have to make a change of an amount using the smallest possible number of coins.\n",
    "\n",
    "Amount: `$` $n$\n",
    "\n",
    "Available coins:\n",
    "* `$` $5$ coin \n",
    "* `$` $2$ coin \n",
    "* `$` $1$ coin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def change_making(amount):\n",
    "    res = []\n",
    "    coins = [5,2,1]\n",
    "    coins.sort(reverse=True)\n",
    "    sum_coins = 0\n",
    "    i = 0\n",
    "    while sum_coins != amount:\n",
    "        if sum_coins + coins[i] <= amount:\n",
    "            sum_coins += coins[i]\n",
    "            res.append(coins[i])\n",
    "        else:\n",
    "            i += 1\n",
    "            \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "solution: [5, 5, 5, 5, 5, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "print('solution:',change_making(28))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fractional Knapsack Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Given weights and values of $n$ items, we need to put these items in a knapsack of capacity $W$ to get the maximum total value in the knapsack.\n",
    "\n",
    "we can break items for maximizing the total value of knapsack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fractional_knapsack(weight,value,capacity):\n",
    "    item_dict = dict()\n",
    "    max_value = 0\n",
    "    for i in range(len(weight)):\n",
    "        fraction = value[i]/weight[i]\n",
    "        item_dict[i] = [fraction,weight[i],value[i]]\n",
    "        \n",
    "    item_dict = {k: v for k, v in sorted(item_dict.items(), key=lambda item: item[1][0], reverse=True)}\n",
    "    for k,v in item_dict.items():\n",
    "        if capacity - v[1] >= 0:\n",
    "            capacity -= v[1]\n",
    "            max_value += v[2]\n",
    "        else:\n",
    "            max_value += v[0]*capacity\n",
    "            capacity = 0\n",
    "            break\n",
    "    \n",
    "    return max_value\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum value to obtain: 240.0\n"
     ]
    }
   ],
   "source": [
    "weight = [10, 40, 20, 30]\n",
    "value = [60, 40, 100, 120]\n",
    "capacity = 50\n",
    "print('Maximum value to obtain:',fractional_knapsack(weight,value,capacity))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Job Sequencing Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline.\n",
    "\n",
    "It is also given that every job takes the single unit of time, so the minimum possible deadline for any job is $1$.\n",
    "\n",
    "How to maximize total profit if only one job can be scheduled at a time?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "def job_sequencing(jobs,deadline):\n",
    "    job_dict = dict()\n",
    "    for i in jobs:\n",
    "        job_dict[i[0]] = [i[1],i[2]] \n",
    "    job_dict = {k: v for k, v in sorted(job_dict.items(), key=lambda item: item[1][1], reverse=True)}\n",
    "    \n",
    "    job_schedule = [None]*deadline\n",
    "    num = 0\n",
    "    for k,v in job_dict.items():\n",
    "        slot = v[0]-1\n",
    "        while slot >= 0:\n",
    "            if job_schedule[slot] is None:\n",
    "                job_schedule[slot] = k\n",
    "                num += 1\n",
    "                break\n",
    "            slot -= 1\n",
    "            \n",
    "        if num == deadline:\n",
    "            break\n",
    "    \n",
    "    return job_schedule\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum profit sequence of jobs: ['c', 'a', 'e']\n"
     ]
    }
   ],
   "source": [
    "jobs = [['a', 2, 100], \n",
    "       ['b', 1, 19],\n",
    "       ['c', 2, 27],\n",
    "       ['d', 1, 25],\n",
    "       ['e', 3, 15]]\n",
    "print('Maximum profit sequence of jobs:',job_sequencing(jobs,3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Divide and Conquer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Closest Pair of Points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: We are given an array of $n$ points in the plane, and the problem is to find out the distance between the closest pair of points in the array. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import copy\n",
    "class Point(): \n",
    "    def __init__(self, x, y): \n",
    "        self.x = x \n",
    "        self.y = y \n",
    "\n",
    "def dist(p1, p2): \n",
    "    res = math.sqrt((p1.x - p2.x)**2 + (p1.y - p2.y)**2)\n",
    "    return res\n",
    "\n",
    "def brute_force(P,n):\n",
    "    min_val = float('inf')\n",
    "    for i in range(n):\n",
    "        for j in range(i+1,n):\n",
    "            if dist(P[i],P[j]) < min_val:\n",
    "                min_val = dist(P[i],P[j])\n",
    "    \n",
    "    return min_val\n",
    "\n",
    "def strip_closest(strip,size,d):\n",
    "    min_val = d\n",
    "    for i in range(size-1):\n",
    "        j = i + 1\n",
    "        while j < size and (strip[j].y - strip[i].y) < min_val:\n",
    "            min_val = min(dist(strip[i], strip[j]),min_val)\n",
    "            j += 1\n",
    "    \n",
    "    return min_val\n",
    "\n",
    "def closestUtil(P, Q, n):\n",
    "    if n <= 3:\n",
    "        return brute_force(P,n)\n",
    "    \n",
    "    mid = n // 2\n",
    "    mid_point = P[mid]\n",
    "    \n",
    "    Ql = copy.deepcopy(P[:mid])\n",
    "    Ql.sort(key = lambda point: point.y)  \n",
    "    Qr = copy.deepcopy(P[mid:])\n",
    "    Qr.sort(key = lambda point: point.y)  \n",
    "    dl = closestUtil(P[:mid],Ql,mid)\n",
    "    dr = closestUtil(P[mid:],Qr,n-mid)\n",
    "    d = min(dl, dr)\n",
    "    \n",
    "    strip = []\n",
    "    for i in range(n):\n",
    "        if abs(Q[i].x - mid_point.x) < d:\n",
    "            strip.append(Q[i])\n",
    "    \n",
    "    return min(d,strip_closest(strip,len(strip),d))\n",
    "            \n",
    "def closest(P): \n",
    "    n = len(P)\n",
    "    P.sort(key = lambda point: point.x) \n",
    "    Q = copy.deepcopy(P) \n",
    "    Q.sort(key = lambda point: point.y)  \n",
    "    \n",
    "    return closestUtil(P, Q, n) \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The distance between the closest pair of points is: 1.4142135623730951\n"
     ]
    }
   ],
   "source": [
    "P = [Point(2, 3), Point(12, 30), \n",
    "     Point(40, 50), Point(5, 1),  \n",
    "     Point(12, 10), Point(3, 4)] \n",
    "print('The distance between the closest pair of points is:',closest(P))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 264,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEKCAYAAAAcgp5RAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAASpElEQVR4nO3dfYxldX3H8fdXFpHdsQFkd0LY1aWFpEFS0Fl5KMQyS1wR6bA1hLixuBrate1us20FRJNGbGqq8QFtSlotKJtGd9j40JlQqZB1LNZWYIdnRAQRXBCZqrvKgAGRb/84Z8N1nMe95869++P9Sm7uPefeub9Pftn97NnfnHtuZCaSpHK9pNsBJEmdZdFLUuEsekkqnEUvSYWz6CWpcEu6HWCqI488MlevXt3tGDN66qmnWLZsWbdjzMh87TFfe8zXnnbyjY+P/zgzl0/7ZGb21G1gYCB72djYWLcjzMp87TFfe8zXnnbyAbtyhl516UaSCmfRS1LhLHpJKpxFL0mFs+glqXCNnl4ZEQ8DTwK/Ap7LzDURcQRwLbAaeBi4IDP3NDmuJGlmnTiiH8zMkzJzTb19GbAzM48DdtbbkqRWo6Owe3d137DFWLo5D9hWP94GrF+EMSXpwDE6Chs2wMREdd9w2Uc2eD36iPg+sAdI4FOZ+emI2JuZh9XPB7Bn33bLz20CNgH09/cPDA8PN5apaZOTk/T19XU7xozM1x7ztcd8+2n3bpiYYHLlSvoefRRWrIBVqxb0FoODg+MtKym/bqZPUu3PDTi6vl8B3Am8Htg75TV7ZnsPPxnbHvO1x3ztMd9+GhnJXLo0xz760cylS6vtBWKxPhmbmY/V9xPAl4GTgSci4iiA+n6iyTEl6YA3NATbt1dH8tu3V9sNaqzoI2JZRLx832NgHXAPMApsrF+2ERhpakxJKsbQULVc03DJQ7OnV/YDX66W4VkCfD4z/zMibgV2RMRFwCPABQ2OKUmaQ2NFn5kPASdOs/8nwFlNjSNJWhg/GStJhbPoJalwFr0kFc6il6TCWfSSVDiLXpIKZ9FLUuEsekkqnEUvSYWz6CWpcBa9JBXOopekwln0klQ4i16SCmfRS1LhLHpJKpxFL0mFs+glqXAWvSQVzqKXpMJZ9JJUOItekgpn0UtS4Sx6SSqcRS9JhbPoJalwFr0kFc6il6TCWfSSVDiLXpIKZ9FLUuEaLfqIOCgibo+I6+rtYyLi5oh4MCKujYiXNjmeJGluTR/RbwXua9n+MHBFZh4L7AEuang8SdIcGiv6iFgJvBm4qt4OYC3whfol24D1TY0nSZqfJo/oPwFcCjxfb78C2JuZz9XbjwJHNzieJGkeIjPbf5OIc4FzMvMvIuJM4GLgHcC36mUbImIVcH1mnjDNz28CNgH09/cPDA8Pt52pUyYnJ+nr6+t2jBmZrz3ma4/52tNOvsHBwfHMXDPtk5nZ9g34B6oj9oeBHwFPA58DfgwsqV9zGvDVud5rYGAge9nY2Fi3I8zKfO0xX3vM15528gG7coZebWTpJjPfm5krM3M18Fbga5n5NmAMOL9+2UZgpInxJEnz1+nz6N8D/E1EPEi1Zn91h8eTJE2xpOk3zMyvA1+vHz8EnNz0GJKk+fOTsZJUOItekgpn0UtS4Sx6SSqcRS9JhbPoJalwFr0kFc6il6TCWfSSVDiLXpIKZ9FLUuEsekkqnEUvSYWz6CWpcBa9JBXOopekwln0klQ4i16SCmfRS1LhLHpJKpxFL0mFs+glqXAWvSQVzqKXpMJZ9JJUOItekgpn0UtS4Sx6SSqcRS9JhbPoJalwFr0kFc6il6TCNVb0EfGyiLglIu6MiHsj4gP1/mMi4uaIeDAiro2IlzY1piRpbk0e0T8DrM3ME4GTgLMj4lTgw8AVmXkssAe4qMEx1aTRUdiypbqXVIzGij4rk/XmwfUtgbXAF+r924D1TY2pBo2OwoYNcOWV1b1lLxUjMrO5N4s4CBgHjgWuBD4CfKs+miciVgHXZ+YJU35uE7AJoL+/f2B4eLixTE2bnJykr6+v2zFmtN/5du+GiYkXtlesgFWrmgtWK3b+Fon52lNyvsHBwfHMXDPtk5nZ+A04DBgDzgAebNm/Crhntp8dGBjIXjY2NtbtCLPa73wjI5lLl2ZCdT8y0miufYqdv0VivvaUnA/YlTP06pL9+qdjDpm5NyLGgNOAwyJiSWY+B6wEHuvEmGrT0BBs3w433ADr1lXbkorQWNFHxHLgl3XJHwq8geoXsWPA+cAwsBEYaWpMNWxoyIKXCtTkEf1RwLZ6nf4lwI7MvC4ivg0MR8TfA7cDVzc4piRpDvMq+og4BHi2Xgdq3bcceKxeIroLeM3Un83Mh4CTG8orSVqgOU+vjIjXUq2rT/0//V8Ct1KdRilJ6lHzOY9+ArgDOGXfjog4HngnsDUzn42I6FA+SVKb5lP0e4D7gNMB6l+0Xgg8mZk7IuIlrUs6kqTeMmfRZ+ZTVL9EfXW969XA24FL6uef71g6SVLb5nvWzc3AQRFxBtWSzW2Z+Y36aN6il6QeNt+i/wlwP/DnVNeu+QPwaF6SDgTzvajZz6jW6TcA12bmd/0FrCQdGOZb9M8A36E6sn8/VFer7FQoSVJz5lv0vwW8BfhYZv6sg3kkSQ2bdY2+Xp55FbAZeHlmfmhRUkmSGjPXEf2bgIeoLjf8ls7HkSQ1bdYj+sz8Cn6BuCQd0CxxSSqcRS9JhbPoJalwFr0kFc6il6TCWfSSVDiLXpIKZ9FLUuEsekkqnEUvSYWz6CWpcBa9JBXOopekwln0klQ4i16SCmfRS1LhLHpJKpxFL0mFs+glqXCNFX1ErIqIsYj4dkTcGxFb6/1HRMSNEfFAfX94U2NKkubW5BH9c8C7M/N44FRgc0QcD1wG7MzM44Cd9bYkaZE0VvSZ+Xhm3lY/fhK4DzgaOA/YVr9sG7C+qTElSXOLzGz+TSNWAzcBJwA/yMzD6v0B7Nm33fL6TcAmgP7+/oHh4eHGMzVlcnKSvr6+bseYkfnaY772mK897eQbHBwcz8w10z6ZmY3egD5gHHhLvb13yvN7Zvv5gYGB7GVjY2PdjjAr87XHfO0xX3vayQfsyhl6tdGzbiLiYOCLwOcy80v17ici4qj6+aOAiSbHlCTNrsmzbgK4GrgvMz/e8tQosLF+vBEYaWpMSdLcljT4XqcDFwJ3R8Qd9b73AR8CdkTERcAjwAUNjilJmkNjRZ+Z/w3EDE+f1dQ4kqSF8ZOxklQ4i16SCmfRS1LhLHpJKpxFL0mFs+glqXAWvSQVzqKXpMJZ9JJUOItekgpn0UtS4Sx6SSqcRS9JhbPoJalwFr0kFc6il6TCWfSSVDiLXpIKZ9FLUuEsekkqnEUvSYWz6CWpcBa9JBXOopekwln0klQ4i16SCmfRS1LhLHpJKpxFL0mFs+glqXAWvSQVrrGij4jPRMRERNzTsu+IiLgxIh6o7w9vajxJ0vw0eUR/DXD2lH2XATsz8zhgZ70tSVpEjRV9Zt4E/HTK7vOAbfXjbcD6psZTB4yOwpYt1b2kYnR6jb4/Mx+vH/8I6O/weNpfo6OwYQNceWV1b9lLxYjMbO7NIlYD12XmCfX23sw8rOX5PZn5G+v0EbEJ2ATQ398/MDw83Fimpk1OTtLX19ftGDPa73y7d8PExAvbK1bAqlXNBasVO3+LxHztKTnf4ODgeGaumfbJzGzsBqwG7mnZvh84qn58FHD/XO8xMDCQvWxsbKzbEWa13/lGRjKXLs2E6n5kpNFc+xQ7f4vEfO0pOR+wK2fo1U4v3YwCG+vHG4GRDo+n/TU0BNu3w+bN1f3QULcTSWrIkqbeKCK2A2cCR0bEo8D7gQ8BOyLiIuAR4IKmxlMHDA1Z8FKBGiv6zNwww1NnNTWGJGnh/GSsJBXOopekwln0klQ4i16SCmfRS1LhLHpJKpxFL0mFs+glqXAWvSQVzqKXpMJZ9JJUOItekgpn0UtS4Sx6SSqcRS9JhbPoJalwFr0kFe5FVfQ3f2Q7d2/YCqOj3Y4iSYvmRVH0t9zyGOesuYJTL/0ulwz/FDZssOwlvWgUXfS7dv2Qc8/9PKecchXXj/+cZTzLa3mcXz39C7jhhm7Hk6RF0diXg/eS8fEfcvnl/8V1130XgGXLDmbLGw/n4uv/liN/8RNYuhTWretySklaHEUV/e2fGObyT97F6MOHALB06cFs3vw6Lrnk91m+fBmMHl0dya9bB0NDXU4rSYujmKK/Zutneec//gA4hEP5JZvXH80ln3o7K1Yse+FFQ0MWvKQXnWKK/pwnb+NIDuXt3MmlfJP+o98BrSUvSS9SxRT9ivVv4AfDF3LoL37uGrwktSim6Bka4tDhf3MNXpKmKKfowTV4SZpG0efRS5IsekkqnkW/EKOjsHu3l0+QdECx6OdrdLS6Rs7EhNfKkXRAsejn64Yb4Omnq8dPP+21ciQdMBal6CPi7Ii4PyIejIjLFmPMxq1bV52fD56nL+mA0vGij4iDgCuBNwHHAxsi4vhOj9u4oSHYvh1WrKjuPY1T0gFiMY7oTwYezMyHMvNZYBg4bxHGbd7QEKxaZclLOqBEZnZ2gIjzgbMz80/q7QuBUzJzS8trNgGbAPr7+weGh4c7mqkdk5OT9PX1dTvGjMzXHvO1x3ztaSff4ODgeGaumfbJzOzoDTgfuKpl+0Lgn2Z6/cDAQPaysbGxbkeYlfnaY772mK897eQDduUMvboYSzePAatatlfW+yRJi2Axiv5W4LiIOCYiXgq8FfAkdElaJB2/qFlmPhcRW4CvAgcBn8nMezs9riSpsihXr8zMrwBfWYyxJEm/ruNn3SxURPwf8Ei3c8ziSODH3Q4xC/O1x3ztMV972sn3qsxcPt0TPVf0vS4iduVMpzD1APO1x3ztMV97OpXPa91IUuEsekkqnEW/cJ/udoA5mK895muP+drTkXyu0UtS4Tyil6TCWfSSVDiLfp4i4uGIuDsi7oiIXd3OAxARn4mIiYi4p2XfERFxY0Q8UN8f3mP5Lo+Ix+p5vCMizulStlURMRYR346IeyNia72/J+Zvlny9Mn8vi4hbIuLOOt8H6v3HRMTN9ZcMXVtf9qSX8l0TEd9vmb+TupGvJedBEXF7RFxXb3dk/iz6hRnMzJN66Dzca4Czp+y7DNiZmccBO+vtbrmG38wHcEU9jyfVn5ruhueAd2fm8cCpwOb6C3F6Zf5myge9MX/PAGsz80TgJODsiDgV+HCd71hgD3BRj+UDuKRl/u7oUr59tgL3tWx3ZP4s+gNYZt4E/HTK7vOAbfXjbcD6RQ3VYoZ8PSEzH8/M2+rHT1L9ZTuaHpm/WfL1hPrKuJP15sH1LYG1wBfq/d2cv5ny9YyIWAm8Gbiq3g46NH8W/fwlcENEjNdflNKr+jPz8frxj4D+boaZwZaIuKte2una0tI+EbEaeA1wMz04f1PyQY/MX73scAcwAdwIfA/Ym5nP1S95lC7+4zQ1X2bum78P1vN3RUQc0q18wCeAS4Hn6+1X0KH5s+jn74zMfC3Vd99ujojXdzvQXOovI+ipoxjgn4Hfofrv9OPAx7oZJiL6gC8Cf5WZP299rhfmb5p8PTN/mfmrzDyJ6jsmTgZ+t1tZpjM1X0ScALyXKufrgCOA93QjW0ScC0xk5vhijGfRz1NmPlbfTwBfpvqD3YueiIijAOr7iS7n+TWZ+UT9F/B54F/p4jxGxMFUJfq5zPxSvbtn5m+6fL00f/tk5l5gDDgNOCwi9l0Vtye+ZKgl39n1klhm5jPAZ+ne/J0ODEXEw1Tfo70W+CQdmj+Lfh4iYllEvHzfY2AdcM/sP9U1o8DG+vFGYKSLWX7DvhKt/RFdmsd6PfRq4L7M/HjLUz0xfzPl66H5Wx4Rh9WPDwXeQPV7hDGqrw+F7s7fdPm+0/KPeFCtf3dl/jLzvZm5MjNXU30Z09cy8210aP78ZOw8RMRvUx3FQ3UN/89n5ge7GAmAiNgOnEl1adMngPcD/w7sAF5JdbnnCzKzK78QnSHfmVTLDgk8DLyrZU18MbOdAXwDuJsX1kjfR7UO3vX5myXfBnpj/n6P6peFB1EdMO7IzL+r/64MUy2L3A78cX303Cv5vgYsBwK4A/izll/adkVEnAlcnJnndmr+LHpJKpxLN5JUOItekgpn0UtS4Sx6SSqcRS9JhbPoJalwFr0kFc6il6TCWfTSLCLi/Ih4JiJe1bLvkxHxvYjo+pUtpfnwk7HSLOprotwK3J6ZfxoRF1NdWvb0zHygu+mk+Vky90ukF6/MzIh4H/AfEfE9quvNnGXJ60DiEb00DxHxP1SXtP3DzLy+23mkhXCNXppDRKwFTqS64uETXY4jLZhH9NIsIuJE4Cbgr6m+37MvM9/Y3VTSwlj00gzqM23+F/iX+lrmJwB3AWsz8+tdDSctgEUvTSMijgC+CdyUme9q2X8t8MrMPK1r4aQFsuglqXD+MlaSCmfRS1LhLHpJKpxFL0mFs+glqXAWvSQVzqKXpMJZ9JJUuP8HqUD+dWcAmMsAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "plt.plot([2,3],[3,4],linewidth = 2,color='navy')\n",
    "plt.scatter(x=[2,12,40,5,12,3],y=[3,30,50,1,10,4],s=10,color='red')\n",
    "plt.xlabel('$x$',fontsize = 14)\n",
    "plt.ylabel('$y$',rotation = True,fontsize = 14)\n",
    "plt.grid()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Longest Common Prefix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Given a set of strings, find the longest common prefix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LCP(lst,low,high):\n",
    "    if low == high:\n",
    "        return lst[low]\n",
    "    \n",
    "    if high > low:\n",
    "        mid = (low + high) // 2\n",
    "        \n",
    "    str1 = LCP(lst, low, mid)  \n",
    "    str2 = LCP(lst, mid + 1, high)  \n",
    "    \n",
    "    return LCP_Util(str1, str2) \n",
    "\n",
    "def LCP_Util(str1,str2):  \n",
    "  \n",
    "    res = \"\"  \n",
    "    n1, n2 = len(str1), len(str2) \n",
    "    i, j = 0, 0\n",
    "  \n",
    "    while i <= n1 - 1 and j <= n2 - 1:  \n",
    "      \n",
    "        if str1[i] != str2[j]:  \n",
    "            break\n",
    "        res += str1[i] \n",
    "        i, j = i + 1, j + 1\n",
    "      \n",
    "    return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Longest common prefix: flo\n"
     ]
    }
   ],
   "source": [
    "lst = [\"flower\", \"flour\",\"flow\", \"floor\"]  \n",
    "n = len(lst) \n",
    "print(\"Longest common prefix:\",LCP(lst,0,n-1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maximum and minimum of an array using minimum number of comparisons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Find the maximum and minimum of an array using minimum number of comparisons."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_max_min(lst,low,high):\n",
    "    if len(lst) == 0:\n",
    "        return None\n",
    "    \n",
    "    if low == high:\n",
    "        lst_max = lst[low]\n",
    "        lst_min = lst[low]\n",
    "        return lst_max,lst_min\n",
    "         \n",
    "    elif high == low + 1:\n",
    "        if lst[low] > lst[high]:\n",
    "            lst_max = lst[low]\n",
    "            lst_min = lst[high]\n",
    "        else:\n",
    "            lst_max = lst[high]\n",
    "            lst_min = lst[low]\n",
    "        return lst_max,lst_min\n",
    "    else:\n",
    "        mid = (low + high) // 2\n",
    "        lst_max1, lst_min1 = get_max_min(lst,low,mid)\n",
    "        lst_max2, lst_min2 = get_max_min(lst,mid+1,high)\n",
    " \n",
    "    return max(lst_max1,lst_max2), min(lst_min1,lst_min2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum: 3124214\n",
      "Minimum: 1\n"
     ]
    }
   ],
   "source": [
    "lst = [1001, 15, 455, 1, 360, 3124214]\n",
    "high = len(lst) - 1\n",
    "low = 0\n",
    "lst_max,lst_min = get_max_min(lst,low,high)\n",
    "print('Maximum:',lst_max)\n",
    "print('Minimum:',lst_min)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Convex-Hull Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: A convex hull is the smallest convex polygon containing all the given points.\n",
    "\n",
    "Input is an array of points specified by their $x$ and $y$ coordinates. The output is the convex hull of this set of points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 251,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Point(): \n",
    "    def __init__(self,x,y): \n",
    "        self.x = x \n",
    "        self.y = y \n",
    "        \n",
    "def line_dist(p_min,p_max,p):\n",
    "    S = abs((p_min.x*p_max.y + p_max.x*p.y + p.x*p_min.y - p_min.x*p.y - p_max.x*p_min.y - p.x*p_max.y) / 2)\n",
    "    dist_max_min = math.sqrt((p_min.x-p_max.x)**2 + (p_min.y-p_max.y)**2)\n",
    "    dist = (S*2)/dist_max_min\n",
    "    return dist\n",
    "\n",
    "def get_side(p_min,p_max,p):        \n",
    "    k = (p_max.y - p_min.y) / (p_max.x - p_min.x)\n",
    "    b = p_max.y - (k * p_max.x)\n",
    "    temp = k * p.x + b \n",
    "    if p.y > temp:\n",
    "        return 1\n",
    "    elif p.y == temp:\n",
    "        return 0\n",
    "    else:\n",
    "        return -1\n",
    "\n",
    "def quick_hull(lst):\n",
    "    n = len(lst)\n",
    "    if n < 3:\n",
    "        print('Convex hull not possible')\n",
    "        return\n",
    "\n",
    "    lst.sort(key = lambda point: point.x)\n",
    "    lst_l = [p for p in lst if get_side(lst[0],lst[-1],p) == 1]\n",
    "    lst_r = [p for p in lst if get_side(lst[0],lst[-1],p) == -1]\n",
    "    \n",
    "    l = _quick_hull(lst_l,lst[0],lst[-1],1)\n",
    "    r = _quick_hull(lst_r,lst[0],lst[-1],-1)\n",
    "    \n",
    "    return [lst[0]]+l+r+[lst[-1]]\n",
    "    \n",
    "def _quick_hull(lst_p,lst_min,lst_max,side):\n",
    "    max_dist = 0\n",
    "    idx = -1\n",
    "    for i in range(len(lst_p)):\n",
    "        l_dist = line_dist(lst_min,lst_max,lst_p[i])\n",
    "        if l_dist > max_dist:\n",
    "            max_dist = l_dist\n",
    "            idx = i\n",
    "    if idx == -1:\n",
    "        return\n",
    "    if side == 1:\n",
    "        lst_l = [p for p in lst_p if get_side(lst_min,lst_p[idx],p) == 1]\n",
    "        lst_r = [p for p in lst_p if get_side(lst_p[idx],lst_max,p) == 1]\n",
    "        p_l = _quick_hull(lst_l,lst_min,lst_p[idx],1)\n",
    "        p_r = _quick_hull(lst_r,lst_p[idx],lst_max,1)\n",
    "        res = []\n",
    "        if p_l is not None:\n",
    "            for i in p_l:\n",
    "                res.append(i)\n",
    "        res.append(lst_p[idx])\n",
    "        if p_r is not None:\n",
    "            for i in p_r:\n",
    "                res.append(i)   \n",
    "        return res\n",
    "    else:\n",
    "        lst_l = [p for p in lst_p if get_side(lst_min,lst_p[idx],p) == -1]\n",
    "        lst_r = [p for p in lst_p if get_side(lst_p[idx],lst_max,p) == -1]\n",
    "        p_l = _quick_hull(lst_l,lst_min,lst_p[idx],-1)\n",
    "        p_r = _quick_hull(lst_r,lst_p[idx],lst_max,-1)\n",
    "        res = []\n",
    "        if p_l is not None:\n",
    "            for i in p_l:\n",
    "                res.append(i)\n",
    "        res.append(lst_p[idx])\n",
    "        if p_r is not None:\n",
    "            for i in p_r:\n",
    "                res.append(i)   \n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 252,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution: ( 0 , 1 ) ( 1 , 3 ) ( 3 , 4 ) ( 1 , 0 ) ( 2 , 0 ) ( 3 , 1 ) ( 4 , 4 ) "
     ]
    }
   ],
   "source": [
    "P = [Point(1,3),Point(2,0),Point(3,4),Point(1,1),Point(2,2),Point(4,4),Point(0,1),Point(1,2),\n",
    "    Point(3,1),Point(3,3),Point(2,1),Point(3,2),Point(1,0)]\n",
    "res = quick_hull(P)\n",
    "print('Solution:',end=' ')\n",
    "for p in res:\n",
    "    print('(',p.x,',',p.y,')',end=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 263,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAEKCAYAAAD+XoUoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3deXgUVdbH8e/NSiBhh4AERBCQVTSIoGwRUEQMAwHEAUcHFFFkRlxwEJDFDV8ZRxy2ERwVHAlLIkQ2ZTDIIiJE2QMKgqyyQwghIUmf949uYwYCBFLp6uV8nqcfursqVT9u0qerq+vea0QEpZRS/iHA7gBKKaXcR4u+Ukr5ES36SinlR7ToK6WUH9Gir5RSfiTI7gBXU7FiRalZs2aRtnHu3DlKlSplTSCLeGIm0FzXwhMzgea6Fp6YCazJlZKSclxEKl2yQEQ8+hYdHS1FlZycXORtWM0TM4lormvhiZlENNe18MRMItbkAjZIATVVT+8opZQf0aKvlFJ+RIu+Ukr5ES36SinlR7ToK6WUH9Gir5RSfkSLvlJK+RHLi74xJtAY84MxZmEBy0KNMbONMbuMMeuMMTWt3r9SSqnLK44j/b8CqZdZ1h84JSI3A/8A3iqG/SulPEhuroNVb37Kr9//DElJdsfxeEnDZ3J2x95iaytLh2EwxkQBDwCvA88VsEpXYLTr/jxgojHGuHqPKaV8RHZ2LitW7CUhIZX5szdx5HQOAA+zH/jB3nCX+NruAAU6HTaEMvEfQ2yspds1VtZbY8w84E0gAnhBRLpctHwr0ElEDrge7wbuFJHjF603ABgAEBkZGR0fH1+kXOnp6YSHhxdpG1bzxEygua6FJ2YC+3JduOBgw4aTrFx5nG++OcHZszluz+BLkseHQ+XKUL36df18TExMiog0u2RBQWMzXM8N6AJMdt1vBywsYJ2tQFS+x7uBilfaro69416aq/A8MZOIe3OdPZslc+Zsld6950l4+BsCo/Nut9wyUYYPXy4p78wSR1hJSR4/XqRkSZEFC9yW72o86Xe4Y8cxCQgYLUGMlE/+9n9FbisuM/aOlad37gZijTGdgRJAaWPMJyLSN986B4HqwAFjTBBQBjhhYQalVDE7fTqTzz/fSWLiDpYu3UVm5u9H9E2bViEurj5xcfWpXz/fAI+1S8KZMzBrluWnK3zF6NFf43DA4/dVplqDMsXWVpYVfREZBgwDMMa0w3l6p+9FqyUBjwJrgR7AV653JKWUBzt27Bzz5+8gMXEHy5f/THa2I29ZixZRxMXVp3v3+tSqVa7gDcTGwooV0K6dW/J6m82bjxAfv5WQkEBGTHuE3bt/KLa2Kvbx9I0xY3F+zEgCPgBmGmN2ASeB3sW9f6XU9Tl4MI3ExFQSE3ewcuUvOBzO47OAAEO7djWJi6vPH/5wC1FRpW1O6v1GjVoBwMCB0VSvXobdu4tvX8VS9EVkBbDCdf+VfM9nAj2LY59KqaL7+edTJCRsJzFxB99+eyDv+eDgAO69tzZxcfWJja1H5cqeN/GIt1q//iDz5+8gLCyIYcNaF/v+PH7mLKVU8dq+/Vheod+48de850uUCKJTp5uJi6tPly51KVu2hI0pfdfIkckADB7cnCpViv+qKy36SvkZEeGHH37NK/Q7dvx+xXR4eAhdutQlLq4+999/M6VKhdiY1PetWvULX3yxm4iIEIYOvdst+9Sir5QfcDiEb789kFfo9+49nbesXLkSdO16C3Fx9enQoRYlSmhZcAcRYcQI51H+c8+1pEKFkm7Zr/52lfJROTkOVq78hYSE7Xz22Q4OH07PWxYZWYpu3W4hLq4BbdveSHBwoI1J/dPy5XtYufIXypUrwZAhLdy2Xy36SvmQrKwcvv32BJ98ksSCBTs5fjwjb1mNGmXo3t1Z6Fu2jCIwUAfZtYvzKP8rAIYOvZsyZdz3fYkWfaW8XEZGNkuX7iIxMZXPP/+RtLSsvGV16pR3dZZqQHR0VYwxNiZVv1m06CfWrTtI5cqlGDy4uVv3rUVfKS+UlpbFwoU/kpCQypIlP3H+/O+9YmvVKsWf/tSMuLgGNGxYSQu9h3E4JO+KnWHDWrn9y3It+kp5iRMnMliwYCeJiaksW/YzFy7k5i27444b8nrFHjy4hXba89VjJSRsZ+PGX6lWLYKBAy8dD624adFXyoMdPnyWzz7bQWJiKitW7CU319kr1hho3boGcXH16datPjVqlMn7mYMH7UqrriY318Err6wAYMSINrZcKaVFXykPs3fvadfwB6l8881+fhudKigogI4db8ob/iAy0vOGdVZX9umnW9ix4zg1a5alX7/bbMmgRV8pD7Bz53ESEpyFPiXlcN7zoaGBecMfPPhgPcqXD7MxpSqK7OxcRo92TtgyenRbQkLsuUxWi75SNhARNm8+klfot207lresVKlgOneuQ1xcfTp3rkNERKiNSZVVPvpoIz//fIp69SrQp08T23Jo0VfKTUSE7747mFfod+8+lbesTJlQYmPrERdXn3vvrU1YWLCNSZXVMjNzGDt2JQBjxrQjKMi+PhJa9JUqRrm5Dlav3pc3RPGBA2l5yypVKskf/uAc/iAm5ibbPu6r4jdtWgoHDqTRuHFlevZsaGsWLfpKWezChVySk/c4JwWfv4Njx37vFVutWgTduztnlmrVqob2ivUDGRnZvP76KgBefTWGgAB7+01YVvSNMSWAlUCoa7vzRGTURes8BryNc9pEgIkiMt2qDErZ5fz5bL78cjcJCc5esadPZ+Ytq1WrXN4UgnfcUc32F71yr4kTv+PIkXM0a3YDsbH17I5j6ZF+FnCPiKQbY4KB1caYJSLy7UXrzRaRZyzcr1K2yMjIYfbsrSQm7mDRoh85dy47b1nDhpXyjuibNInUXrF+Ki0ti7feWgPAa6/FeMTfgZVz5Arw2zB+wa6bzn+rfMqpU+dJSnJOCr5kyY9kZ//+Jx4dXTWv0NerV9HGlMpTvPvut5w8eZ5WrWpw77217Y4DgLFyXnJjTCCQAtwMTBKRly5a/hjwJnAM+BEYIiL7C9jOAGAAQGRkZHR8fHyRcqWnpxMe7lkdWTwxE2iugpw8eYHVq4+zatVxfvjh9P/0im3YsDStW1ekTZtKVKniGTNL6e+w8IozU1paNn/84zrOncvl3Xdv5dZby7o1V0xMTIqIXDrOg4hYfgPKAslAo4uerwCEuu4/CXx1tW1FR0dLUSUnJxd5G1bzxEwimus3+/adlnffXStt2nwoxowWcN4CA8dI+/Yfy6RJ38m8eUvdmqmw9HdYeMWZadiw/wqMlo4dZ1zzz1qRC9ggBdTU4poY/bQxJhnoBGzN9/yJfKtNB/6vOPav1PXYtetk3sxS3333+wA2ISGBdOxYi+7dnZOCV6zonOFoxYoVNiVVnu7o0XNMmLAOcF6x40msvHqnEpDtKvhhQEfgrYvWqSoiv/UxjwVSrdq/UtdKRNi27fdJwTdvPpK3LCwsiM6d69C9e30eeKCOWye5UN5v3LjVZGRk8+CDdbnzzii74/wPK4/0qwIfu87rBwBzRGShMWYszo8ZScBfjDGxQA5wEnjMwv0rdVUiQkrKYRITU0lISOXHH3//8Fm6dCgPPliX7t3r06nTzZQsqb1i1bU7eDCNyZPXAzB2rGcd5YO1V+9sBi4ZNk5EXsl3fxgwzKp9KlUYDofwzTf7847o9+07k7esQoUw/vCHW+jevT7t299EaKj2V1RF89prK8nKyqVnzwY0bVrF7jiX0L9w5ZOys3P5+mvnpODz5+/k119/nxS8atVwund3TjjSps2Nto6DonzLnj2nmD79BwICDGPGtLM7ToG06CufkZWVw7JlP5OYmMqCBTs5efJ83rKaNcvmzSzVokWU9opVxWLs2JXk5Dh45JEm1K9fye44BdKir7zauXMXWLLEOSn4woU/cvbshbxl9epVyJsU/LbbqnhEb0jlu3buPM6MGZsICgpg1Ki2dse5LC36yuucOZPJ55//SGJiKkuX7vqfScGbNq2Sd0TfoIFnHmkp3zR69Nc4HMLjj99G7drl7Y5zWVr0lVc4ffoC06d/T2JiKv/9789kZzvylrVoEeWaK/YWj36xKd+1efMR4uO3EhISyIgRbeyOc0Va9JXHOngwLW9S8K+/3ovDVecDAgzt2tXMmys2Kqq0vUGV3xs1agUAAwdGU716mSuvbDMt+sqj7NlzKm9mqbVrD+Q9HxRkuPfe2nTvfgtdu95C5cqlbEyp1O82bDjE/Pk7CAsLYtiw1nbHuSot+sp2qanH8jpL/fDDr3nPlygRRKdONxMXV5+yZY/SpUsHG1MqVbARI74CYPDg5lSp4lkDyhVEi75yOxFh48Zf847oU1OP5y0LDw+hS5e6xMU5e8WGh4cAOs6N8kyrVv3CF1/sJiIihKFD77Y7TqFo0Vdu4XAI69YdyCv0e/aczltWrlwJunZ1zhXboUMtSpTQP0vl+USEESOSARgypAUVKpS0OVHh6KtLFZucHAerVv1CYmIqn322g4MHz+Yti4wsRbduzuEP2rWrSXCwTgquvMvy5XtYufIXypUrwXPPtbQ7TqFp0VeWunAhl+XLnb1i58/fyfHjv08KXqNGGbp3dxb6u+6qrpOCK6/lPMp3nssfOvRurxqFVYu+KrKMjGy++GIXiYk7+PzznZw5k5W3rE6d8nm9YqOjq2qvWOUTFi36iXXrDlK5cikGD25ud5xrokVfXZe0tCwWLfqRxMQdLF78ExkZv08K3rhx5bxC37BhJS30yqc4HMLIkc5z+cOGtaJUqRCbE10bLfqq0E6cyMibFPzLL3dz4UJu3rI77rghb/iDOnUq2JhSqeKVmJjKxo2/Uq1aBAMHXjoFraezcuasEsBKINS13XkiMuqidUKBGUA0cAJ4SET2WpVBWe/XX9P57LNUEhN3kJy8538mBW/duoZr+IP61Kjh2b0QlbJCbq6DV15xHuWPGNHGK680szJxFnCPiKQbY4KB1caYJSLybb51+gOnRORmY0xvnNMpPmRhBlUUSUlw5gy/TJ9H4tlqJCbuYM2afTjnsYegoAA6drwpb/iDyEjP74iiPITrb4ukJIiNtTvNdfv00y2kph6nZs2y9Ot3yZxRXsHKmbME+G2mimDXTS5arSsw2nV/HjDRGGNcP6tsdPyTRGIfXcLPZapz5JQA2wAIDQ3k3ntrExdXnwcfrEf58mH2BlXeJykJHn4Yxo6FgQNh1iyvLPzZ2bmMHv01AKNGtSUkxDsvMzZW1lvX/LgpwM3AJBF56aLlW4FOInLA9Xg3cKeIHL9ovQHAAIDIyMjo+Pj4IuVKT08nPNyzjko9LdPcaVuY/OlJAEKDocVtpWhzXw1atChPyZL2f4T1tPYCz8wEHphr/344epT0qCjCDxyAypWhenW7UwHX1lYLFx7m73//kerVw/jwwzsIDCy+CxSs+B3GxMSkiMilXzqIiOU3oCyQDDS66PmtQFS+x7uBilfaVnR0tBRVcnJykbdhNU/KtHHjYSkRMkZgtPzhrtckI6y0yIIFdsf6H57UXr/xxEwiHphrwQKRkiUlefx4kZIlPepvq7Btdf58tkRFvSMwWuLjtxRvKLHmdwhskAJqarEcwonIaWNMMtDJVeh/cxCoDhwwxgQBZXB+oatscvp0JnFxc8i8IPTrUJ5H/lSWsDIzvfLjt/JQsbHOUzpnznjtqZ1p01I4cCCNxo0r07NnQ7vjFIllXSKNMZWMMWVd98OAjsCOi1ZLAh513e8BfOV6R1I2cDiERx+dz+7dp2jatAoTkwY6P3Z74YtSebjYWK/928rIyOb111cB8OqrMV4/v7KVR/pVgY9d5/UDgDkistAYMxbnx4wk4ANgpjFmF3AS6G3h/tU1+r//W0NS0k7Kli1BQkIvwsKC7Y6klMeZNOk7jhw5R7NmNxAbW8/uOEVm5dU7m4FLrmESkVfy3c8Eelq1T3X9vvpqD8OHO8cOmTmzG7VqlbM5kVKeJy0ti3Hj1gDw2msxPtG7XEe88kMHD6bRu/c8HA5h+PDWdOlS1+5ISnmkd9/9lpMnz9OqVQ3uvbe23XEsoUXfz1y4kEvPnnM5diyD9u1vYsyYdnZHUsojnTx5nr//fS3gO0f5oEXf7wwduoy1aw8QFVWaWbPidHhjpS5j/PhvSEvLomPHWrRtW9PuOJbRV7wfiY/fyoQJ6wgODmDu3J5UqqSTiytVkKNHzzFhwjrAecWOL9Gi7ye2bz/G448nAfCPf9xHixZRNidSynONG7eajIxsHnywLnfe6VuvFS36fuDs2Szi4uZw7lw2f/xjY55++g67IynlsQ4eTGPy5PUAjB3rW0f5oEXf54kIjz/+OTt2HKdhw0q8/34Xn/lCSqni8Prrq8jKyqVnzwY0bVrF7jiW06Lv4957bx1z5mwjPDyEhIReXjfLj1LutGfPKaZN+56AAOOzV7Zp0fdha9bs44UXlgHw4YddqVevos2JlPJsY8euJCfHQZ8+jalfv5LdcYqFFn0fdeRIOr16zSMnx8Fzz7WgR48GdkdSyqPt3HmcGTM2ERhoGDWqrd1xio0WfR+Uk+Ogd+8EDh06S+vWNRg3roPdkZTyeKNHf43DIfTrdxu1a5e3O06x0aLvg0aM+IoVK/YSGVmK2bN7EBzsnTP8KOUumzcfIT5+KyEhgYwc2cbuOMVKi76PmT9/B2+9tYbAQMOcOT2pWjXC7khKebxRo1YAMHBgNNWrl7E3TDHTou9Ddu06yaOPzgdg3LgOtGlzo82JlPJ8GzYcYv78HYSFBTFsWGu74xQ7Lfo+IiMjm7i4OaSlZdG9e32ef76l3ZGU8gojRyYDMHhwc6pU8aC5hYuJFn0fICIMHLiQzZuPUKdOeT78sKt2wFKqELZsOcPSpbuIiAhh6NC77Y7jFlZOl1jdGJNsjNlujNlmjPlrAeu0M8acMcZsdN1eKWhb6tq8/34KM2dupmTJYBITH6J06VC7Iynl8USE6dP3ADBkSAsqVChpcyL3sHK6xBzgeRH53hgTAaQYY5aJyPaL1lslIl0s3K9fW7/+IH/5y1IA3n+/C40aVbY5kVLeYfnyPWzefIZy5UowZIj/nA617EhfRA6LyPeu+2eBVKCaVdtXlzpxIoMePeZy4UIuTz/djD59mtgdSSmvICKMGOGcLvTFF++ibNkSNidyHyMi1m/UmJrASqCRiKTle74dkAAcAA4BL4jItgJ+fgAwACAyMjI6Pj6+SHnS09MJD/esL2iKmik3Vxg2bAvr15/illsimDChKSEhRX8P98S2As/M5YmZQHMVxtq1J3j55a2ULRvEp5+2ICzMs/qyWNFWMTExKSLS7JIFImLpDQgHUoDuBSwrDYS77ncGfrra9qKjo6WokpOTi7wNqxU106hRyQKjpUKFt2TfvtPWhBLPbCsRz8zliZlENNfV5OY6pGnTqQKjZdCgmXbHKZAVbQVskAJqqqVX7xhjgnEeyf9HRBILeINJE5F01/3FQLAxRkcBu0ZLlvzE2LFfYwzMmhXn851JlLJSYmIqGzf+SrVqEcTG3mB3HLez8uodA3wApIrIO5dZp4prPYwxzV37P2FVBn+wd+9p+vb9DBHnBA8dO9a2O5JSXiM318Errzivyx8xoo0lp0S9jZVX79wNPAJsMcZsdD33MlADQESmAj2Ap4wxOcB5oLfrY4gqhMzMHHr0mMPJk+fp3LkOL7/s+70HlbLSrFlbSU09Ts2aZenX7za++WaV3ZHczrKiLyKrgSv2CBKRicBEq/bpb559dikpKYepWbMsM2d2IyBAO2ApVVjZ2bl5Y+yMGtWWkBDP+vLWXfzvs42X+vjjjfzrXymEhgaSkNCL8uXD7I6klFf56KON/PzzKerWrUDfvv57ebMWfS+wadOvDBy4CIBJkzpz++1VbU6klHfJzMxh7NiVAIwZ046gIP8tff77P/cSp09nEhc3h8zMHPr1a0r//rfbHUkprzNtWgoHDqTRuHFlevVqaHccW2nR92AOh/Doo/PZvfsUTZtWYeLEznZHUsrrZGRk8/rrzi9sX301xu+/C9Oi78HefnsNSUk7KVu2BAkJvQgLC7Y7klJeZ9Kk7zhy5BzNmt1AbGw9u+PYrlBF3xgTai4aq9f1XNTFzytrJCfv4eWXnWODzJzZjVq1ytmcSCnvk5aWxVtvrQHgtddidMhxClH0jTG3AweB2IsWDQbWA3r4abGDB9Po3TsBh0MYPrw1XbrUtTuSUl5pwoRvOXHiPK1a1eDee7UjIxTuSP8osBG487cnjDENgD8DfxWRC3q0b50LF3Lp2XMuR4+eo337mxgzpp3dkZTySidPnmf8+LWAHuXnV5iifwrnMMl3AxhjwnD2vD0rInOMMQHaq9Y6Q4cuY+3aA0RFlWbWrDgCA/VrF6Wux/jx35CWlkWHDrVo27am3XE8xlUrioicA34AfrvOqSHwJ+BF13JHsaXzM7Nnb2XChHUEBwcwd25PKlUqZXckpbzS0aPnmDBhHeA8yle/K+wwDOuAQGNMK5yndb4XkVWuo3wt+hZITT1G//5JALzzzn20aBFlcyKlvNe4cavJyMjmwQfrcued+lrKr7BF/wSwE3gKuAdoC3qUb5WzZ7Po3n0O585l88c/NmbQoDvsjqSU1zp4MI3Jk9cDzpFo1f8q7AnjMzjP6z8MzBaRH/XLW2uICI8//jk7dhynYcNKvP9+F/3CSakieP31VWRl5dKzZwOaNq1idxyPU9iinwXswHnEPwpAv7y1xnvvrWPOnG2Eh4eQkNCLUqVC7I6klNfas+cU06d/T0CA0SvfLqOwRb800B34u4icKcY8fmXNmn288MIyAD78sCv16ukkYkoVxauvriQ720GfPo2pX7+S3XE80hWLvnGqCQwHIkRk3BXWrW6MSTbGbDfGbDPG/PUy23vPGLPLGLPZ1fHLL508eYFeveaRk+Pgueda0KNHA7sjKeXVdu48zscfbyIw0DBqVFu743isqx3p3w/8DLTCeaR/JTnA8yLSAGgBDHJ14rp4e3VctwHAlGtO7ANychy89loqhw6dpXXrGowb18HuSE5JSbB/v/NfdWXaVtfGDe01evTXOBxCv363Ubt2+WLbj7e7YtEXkcUiEiAiLUVkx1XWPSwi37vun8X5xW+1i1brCsxwTdb+LVDWGON3g8OPGPEVP/xwmsjIUsye3YPgYA+YwScpCR5+GI4edf6rxezytK2ujRvaa/PmI8THbyUkJJARI9pYvn1fYorj+1jXKaGVQCMRScv3/EJgnGtqRYwxy4GXRGTDRT8/AOcnASIjI6Pj4+OLlCc9PZ3w8PAibcMqq1cfZ+TIbQQEwDvv3Mqtt5a1O5LT/v1w9CjpUVGEHzgAlStD9ep2p8rjSb9Dbatr5Ib2GjlyK6tXn6B792oMHnxzoX/O49rKxYpcMTExKSLS7JIFImLpDQgHUoDuBSxbCLTK93g50OxK24uOjpaiSk5OLvI2rPDTTyekdOk3BUbLwIEzrv4D7rRggUjJkpI8frxIyZLOxx7EU36HIqJtda2Kub3Wrz8oMFrCwl6Tw4fPXtPPelxbuViRC9ggBdRUyyZGBzDGBAMJwH9EJLGAVQ4C+d/io1zP+byMjGzi4uaQlpZF9+716dXLw64siI2FWbPgzBnnv7EXD6qq8mhbXZtibq+RI5MBGDy4OVWqeN5Ru6exbDQvV2etD4BUEXnnMqslAX9yXcXTAjgjIoetyuCpRISnnlrE5s1HqFOnPB9+2NUzO2DFxjo/dmsRuzptq2tTTO21evU+li7dRURECEOH3m3ptn2VlUf6d+McfXOLMWaj67mXgRoAIjIVWAx0BnYBGTjH8fF577+fwowZmyhZMpjExIcoXTrU7khKeT0RYcQI50RDQ4a0oEKFkjYn8g6WFX1xfjl7xcNX13mmQVbt0xusX3+Qv/xlKQDvv9+FRo0q25xIKd+wfPkevv76F8qVK8GQIS3tjuM1dLD2YnTiRAY9eszlwoVcnn66GX36NLE7klI+If9R/osv3kXZsiVsTuQ9tOgXk9xcB336JLJv3xmaN6/GO+/cZ3ckpXzGokU/sW7dQSpXLsXgwXde/QdUHi36xeS111byxRe7qVAhjLlzexIaaumFUkr5LYdD8q7YGTasFeHhOkjhtdCiXwyWLt3FmDFfYwzMmhVHjRpl7I6klM9ITExl48ZfqVYtgoEDL+17pK5MDz8ttnfvafr0SUQEXn01ho4da9sdSSmfkZvr4JVXnEf5I0a0oUQJLWHXSo/0LZSZmUOPHnM4efI8nTvX4eWXW9sdSSmfMmvWVlJTj1OzZln69bvN7jheSYu+hZ59dikpKYepWbMsM2d2IyDAAztgKeWlsrNzGT16BQCjRrUlJMQDBir0Qlr0LfLxxxv5179SCA0NJCGhF+XLh9kdSSmf8tFHG9m9+xR161agb1+9/Pl6adG3wKZNvzJw4CIAJk3qzO23+91o0UoVq8zMHMaOXQnAmDHtCArS0nW9tOWK6PTpTOLi5pCZmUO/fk3p399vJwNTqthMm5bCgQNpNG5cmV69Gtodx6tp0S8Ch0N49NH57N59iqZNqzBxYme7IynlczIysnn99VWA84o4/a6saLToF8Hbb68hKWknZcuWICGhF2FhwXZHUsrnTJr0HUeOnKNZsxuIja1ndxyvp0X/OiUn7+Hll51jf8yc2Y1atcrZnEgp35OWlsVbb60B4LXXYjxzSHIvo0X/Ohw8mEbv3gk4HMLw4a3p0qWu3ZGU8kkTJnzLiRPnadWqBvfeqx0draBF/xpduJBLr17zOHr0HO3b38SYMe3sjqSUTzp58jzjx68F9CjfSlbOnPVvY8xRY8zWyyxvZ4w5Y4zZ6Lq9YtW+3Wno0GV8881+oqJKM2tWHIGB+r6pVHEYP/4b0tKy6NChFm3b1rQ7js+wcuCKj4CJwIwrrLNKRLpYuE+3mj17KxMmrCM4OIC5c3tSqVIpuyMp5ZOOHj3HhAnrAOcVO8o6lh2mishK4KRV2/M0qanH6N8/CYB33rmPFi2ibE6klO8aN241GRnZdOlSV19rFjPOGQwt2pgxNYGFIjEPu8oAABtoSURBVNKogGXtgATgAHAIeEFEtl1mOwOAAQCRkZHR8fHxRcqVnp5OeHj4df98RkYOTz31A/v2ZdC+fWWGD7+lyOcXi5qpuGiuwvPETOD9uY4dy6JPn3VkZwvTpkVz883F93/x9ra6kpiYmBQRuXTsaRGx7AbUBLZeZllpINx1vzPwU2G2GR0dLUWVnJx83T/rcDjkoYfmCoyWhg0nSXp6VpHzFDVTcdJcheeJmUS8P9dTTy0UGC09e84p3kDi/W11JcAGKaCmuu1bSBFJE5F01/3FQLAxpqK79n+93ntvHbNnbyM8PISEhF6UKqWz9ChVXPbsOcX06d8TEGD0yrhi4raib4ypYlznRIwxzV37PuGu/V+PNWv28cILywD48MOu1Kvn8e9RSnm1V19dSXa2gz59GlO/fiW74/gky67eMcbMAtoBFY0xB4BRQDCAiEwFegBPGWNygPNAb9dHEI905Eg6vXrNIyfHwXPPtaBHjwZ2R1LKp/344wk+/ngTgYGGUaPa2h3HZ1lW9EXk4assn4jzkk6Pl5Pj4OGHEzh06CytWtVg3LgOdkdSyueNGrUCh0N44onbqV27vN1xfJb2LCrAyJFfkZy8l8jIUsyZ04PgYJ2hR6nitHnzEeLjtxISEsiIEW3sjuPTtOhfZMGCHYwbt4bAQMOcOT2pWjXC7khK+bxRo1YA8OST0dSoUcbeMD5Oi34+u3ad5E9/mg/AuHEdaNPmRpsTKeX7Nmw4xPz5OwgLC+Lll1vbHcfnadF3ycjIJi5uDmlpWXTvXp/nn29pdySl/MLIkckADB7cnCpVPK+jlK/Roo+zg9pTTy1i8+Yj1KlTnn//O1ZH9FPKDVav3sfSpbuIiAhh6NC77Y7jF7ToA9Omfc+MGZsoWTKYxMSHKFOmhN2RlPJ5IsKIEc6JiIYMaUGFCiVtTuQf/L7ob9hwiMGDlwDw/vtdaNSoss2JlPIPX321h6+//oVy5UowZIieTnUXvy76J05k0KPHHC5cyOXpp5vRp08TuyMp5RdEhOHDnUf5L754F2XL6qdrd/Hbop+b66BPn0R++eUMzZtX45137rM7klJ+Y9Gin1i37iCVKpVk8OA77Y7jV/y26L/22kq++GI3FSqEMXduT0JDrZxPRil1OQ6H5F2xM2xYK8LDdRBDd/LLor906S7GjPkaY2DWrDjtDKKUGyUmprJx46/ccEMEAwdeOty7Kl5+d3j7yy+n6dMnERHnNGwdO9a2O5JSfiM318ErrziP8keObENYWLDNifyPXx3pZ2bm0KPHXE6ePE/nznW0959SbjZr1lZSU49Ts2ZZ+vW7ze44fsmviv6zzy5lw4ZD1KxZlpkzuxEQoB2wlHKXnBwHo0evAGDUqLaEhOhAhnbwm6L/8ccb+de/UggNDSQhoRfly4fZHUkpv/LFF0fYvfsUdetWoG9fvTzaLn5xTn/XrnQGD14DwKRJnbn99qo2J1LKv2Rl5TBjxi8AjBnTjqAgvzne9DiWtbwx5t/GmKPGmK2XWW6MMe8ZY3YZYzYbY263at9Xcvp0JqNGbSMzM4d+/ZrSv79bdquUyuf991M4ejSLRo0q06tXQ7vj+DUr324/AjpdYfn9QB3XbQAwxcJ9Fyg310HrWydw6FAmTW8KY+LEzsW9S++WlAT79zv/VVembVVoZ89mMfylLwF49cFS+l2azSwr+iKyEjh5hVW6AjPE6VugrDGmWM+z9Lj7Pbbuy8QYGHJwLmHLlhTn7rxbUhI8/DAcPer8V4vZ5WlbFdq2bUdpWOvvnD3voEwp6PruU9peNjNWzk1ujKkJLBSRRgUsWwiME5HVrsfLgZdEZEMB6w7A+WmAyMjI6Pj4+OvKszIxldenHOVCjvNxp9bhPPVCE0qXtv/a4PT0dMLDPWjs8P374ehR0qOiCD9wACpXhurV7U6Vx6PaS9vqqrKzHXz66T4++WQfOTlCYAA81L0CT7TI8qj28oS2KogVuWJiYlJE5NLebyJi2Q2oCWy9zLKFQKt8j5cDza62zejoaLluCxZIRokIGdD5DQllhMBoiYx8W+bM2SoOh+P6t2uB5ORkW/d/iQULREqWlOTx40VKlnQ+9iAe1V7aVle0du1+adhwksBogdEysNNEOVmirHz19tse1152t9XlWJEL2CAF1FR3foV+EMj/9h7leq74xMYSNvsTHu4dxebJjWnT5kaOHDlHr17z6N59DocOnS3W3XuV2FiYNct5FDZrlvOxKpi2VYHS0y/w7LNLueuuD9i27Rh16pRnxYpHmbJkEOVmf4yJjNT28gDuLPpJwJ9cV/G0AM6IyOFi32tsLFSvTt2nepGc/ChTpjxAREQI8+fvoEGDSUyf/v1vnzyUq630RVkI2lb/48svd9O48RQmTFhHQIDhb3+7m02bBtK2bU3nCtpeHsPKSzZnAWuBesaYA8aY/saYgcaYga5VFgM/A7uAacDTVu27sAICDAMHNmP79kF06VKXM2eyeOKJz2nffga7dl3pO2ilVEFOnjzPY4/N5777PmHv3tPcdlsV1q9/gjff7KDj6ngoyzpnicjDV1kuwCCr9lcUUVGlSUrqzezZ2/jLX5aQnLyXxo2n8OqrMTz7bAvtOKLUVYgI8+Zt55lnlnD06DlCQwMZM6Ydzz3XkuBgHV7Bk/ltdTPG0Lt3I7ZvH8QjjzQhMzOHF19cRosW09m06Ve74ynlsQ4dOku3brPp1WseR4+eo02bG9m8+SleeqmVFnwv4LdF/zcVK5ZkxoxuLFnShxo1ypCScphmzaYxfPhyMjNz7I6nlMcQEaZNS6FBg0ksWLCTiIgQpk59gOTkR6lbt4Ld8VQh+X3R/02nTjezdetTPPPMHeTmOnjjjdU0bTqV1av32R1NKdvt2nWS9u1nMGDAQs6cyaJLl7ps3z6IJ59spj1svYwW/XwiIkL55z87s3p1P265pSI7d56gdesPGTRoEWlpWXbHU8rtcnIcvP32Gho3nkJy8l4qVSrJrFlxJCX1JiqqtN3x1HXQol+Au+6qzsaNTzJyZBuCggKYPHkDjRpNZvHin+yOppTbbNr0Ky1aTGfo0P+SmZnDI480ITV1EL17N8IYPbr3Vlr0LyM0NIixY2NISRlAs2Y3sH9/Gg888Cl9+yZy/HiG3fGUKjaZmTkMH76cZs2mkZJymBo1yrBkSR9mzOhGhQol7Y6nikiL/lU0aRLJ2rX9GT++I2FhQfznP1uoX38Sn366RTt1KZ+zevU+mjadyhtvrCY318Hgwc3ZuvUpOnW62e5oyiJa9AshKCiA55+/iy1bnuKee27i+PEM+vRJ5MEHZ7F//xm74ylVZGlpWQwatIjWrT9k584T3HJLRVav7sd7791PRESo3fGUhbToX4Patcvz3/8+wvTpD1KmTCiLFv1Ew4aTmTJlPQ6HHvUr77Ro0Y80bDiZyZM3EBQUwMiRbdi48UnuusszRsJU1tKif42MMfTvfzupqYPo3r0+Z89e4OmnF9Ou3Ufs3Hnc7nhKFdqxY+fo0yeRLl1mceBAGnfccQMpKQMYOzaG0FC/mEnVL2nRv05Vq0aQkNCLefN6EhlZilWr9nHrrVN5441VZGfn2h1PqcsSET79dAsNGkzm00+3EBYWxN//fi9r1/anSZNIu+OpYqZFv4ji4hqQmjqIfv2akpWVy/DhX3HHHdNISTlkdzSlLrF//xm6dJlFnz7Oq9Duuecmtmx5iueea0lgoJYDf6C/ZQuUKxfGBx90ZdmyR7jpprJs2nSEO++cztChy8jIyLY7nlI4HMLkyetp0MDZ36RMmVA++CCW//73EWrXLm93POVGWvQt1KFDLddRUwtE4O23v+HWW6eyYsVeu6MpP7Zz53Hatv2IQYMWk55+ge7d67s+nd6mnaz8kBZ9i5UqFcLf/34fa9f2p1GjyuzadZKYmI958snPOXMm0+54yo9kZ+fyxhuruPVW5xhSVaqEM29eTxISelG1aoTd8ZRNLC36xphOxpidxphdxpi/FbD8MWPMMWPMRtftcSv370maN6/muhKiHcHBAbz//vc0aDCZBQt22B1N+YGUlEPcccc0hg//iqysXPr1a8r27U8TF9fA7mjKZlbOnBUITALuBxoADxtjCvoLmy0iTV236Vbt3xOFhAQycmRbNm4cSMuWURw6dJY//GE2Dz00j5MnL9gdT/mgjIxspk7dTfPm09m06Qg33VSWZcse4YMPulKuXJjd8ZQHsPJIvzmwS0R+FpELQDzQ1cLte60GDSqxatWfmTChE6VKBTNnzjYee2w9M2Zs0qEclGWSk/fQpMkUZs8+AMBzz7Vgy5an6NChls3JlCcxVhUdY0wPoJOIPO56/Ahwp4g8k2+dx4A3gWPAj8AQEdlfwLYGAAMAIiMjo+Pj44uULT09nfDw8CJtwyq//prJO+/8yPr1pwBo1qwczz9flypVSticzMmT2io/T8zlKZnS03OYOvVnFi06DMCNN5bgpZfqU7++Zw197CntlZ8nZgJrcsXExKSISLNLFoiIJTegBzA93+NHgIkXrVMBCHXdfxL46mrbjY6OlqJKTk4u8jas5HA4ZNiweClf/i2B0VKq1Ovy7rtrJScn1+5oHtdWv/HEXJ6Q6bPPUqVq1fECoyU4eKyMHbtCvvxyud2xCuQJ7XUxT8wkYk0uYIMUUFOtPL1zEMg/WEeU67n8bzAnROS32UimA9EW7t9rGGO4995Itm9/moceasi5c9k8++wXtGr1Idu3H7M7nvICR46k06vXXLp1m83hw+m0bBnFxo0DGTmyLcHBelGeujwr/zrWA3WMMTcZY0KA3kBS/hWMMVXzPYwFUi3cv9eJjAwnPr4HCxb05oYbIvj22wM0bTqVMWNWcOGCDuWgLiUifPzxRurXn8TcudspVSqY997rxKpVf6ZBg0p2x1NewLKiLyI5wDPAFziL+RwR2WaMGWuMiXWt9hdjzDZjzCbgL8BjVu3fm8XG1mP79qd58slosrMdjB79NdHR77Nu3QG7oykPsnfvaTp1+g+PPbaAU6cyue++2mzb9jSDB9+pQyioQrP0L0VEFotIXRGpLSKvu557RUSSXPeHiUhDEblVRGJERC9adylTpgRTp3ZhxYpHufnm8mzdepSWLT/guee+4Nw5vbzTn+XmOpgw4VsaNpzMl1/upnz5MGbM+ANLlvThxhvL2h1PeRk9PPAwbdvWZPPmgbz00t0EBBj+8Y9vadx4Cv/97892R1M22LbtKHff/W+effYLMjKyeeihhqSmDuKRR27VIRTUddGi74HCwoIZN64D3333BE2bVmHPntN07DiTfv0WcOrUebvjKTe4cCGXMWNWcNtt/2LduoPccEMECxb0Jj6+B5Url7I7nvJiWvQ92O23V+W77x7njTfuITQ0kA8/dH6BN2/edu3U5cPWrTvA7bf/i9GjvyY728GTT0azffvTxMbWszua8gFa9D1ccHAgw4a1ZtOmgbRuXYMjR87Rs+dcunefw6FDZ+2Opyx07twFhgxZSsuWH7Bt2zFuvrk8K1Y8ytSpXShTxjM67ynvp0XfS9SrV5EVKx5jypQHiIgIYf78HTRoMInp07/Xo34fsGzZbho1msK7764jIMDw0kt3s3nzQNq2rWl3NOVjtOh7kYAAw8CBzdi27Wm6dKnLmTNZPPHE57RvP4Ndu07aHU9dh5Mnz/PnPy/g3ns/Ye/e0zRtWoXvvnuCceM6EBYWbHc85YO06Huh6tXLkJTUm1mz4qhYsSTJyXtp0mQK48d/Q06Ow+54qhBEhLlzt9GgwSQ++mgjoaGBvPlme7777nFuv73q1Teg1HXSou+ljDH07t2I1NRB9O3bhPPnc3jxxWW0bPkBmzcfsTueuoJDh87SvfscevWax5Ej52jdugabNg3kb39rRXBwoN3xlI/Tou/lKlYsycyZ3Vi8+I9Ur16aDRsOER39PiNGfEVmZo7d8VQ+IsL06d/ToMEk5s/fQURECFOmPMCKFY9Rr15Fu+MpP6FF30fcf38dtm17mmeeuYPcXAevv76K2277F2vW7LM7mgJ27TpJ+/YzeOKJzzlzJosuXeqyffsgBg5sRkCAdrJS7qNF34dERITyz392ZtWqP3PLLRXZseM4rVt/yODBizl7NuvqG1CWy8lxMH78NzRuPIXk5L1UqlSSWbPiSErqTVSUZ413r/yDFn0fdPfdNfjhhycZMaI1gYEBTJy4noYNJ7NkyU92R/Mrmzb9SosW03nxxWVkZubQt28Ttm8fRO/ejXQIBWUbLfo+qkSJIF599R5SUgbQrNkN7N+fRufOn9K3byLHj2fYHc+nZWbmMHz4cpo1m0ZKymGqVy/N4sV/ZObMblSsWNLueMrPadH3cU2aRLJ2bX/Gj+9IWFgQ//nPFurXn8SsWVu0U1cxWL16H02bTuWNN1aTm+vgmWfuYNu2p7n//jp2R1MK0KLvF4KCAnj++bvYsuUpYmJqcvx4Bn/8YyKxsfHs33/G7ng+IS0ti0GDFtG69Yfs3HmCW26pyOrV/fjnPzsTERFqdzyl8lha9I0xnYwxO40xu4wxfytgeagxZrZr+TpjTE0r96+urHbt8ixf/iemT3+QMmVCWbjwRxo2nMyUKetxOPSo/3otXvwTjRpNZvLkDQQFBTBiRGt++OFJ7rqr+tV/WCk3s6zoG2MCgUnA/UAD4GFjTIOLVusPnBKRm4F/AG9ZtX9VOMYY+ve/ne3bB9Gt2y2cPXuBp59eTLt2H/HjlDmwfz8kJV19Q/4uKYkz2/fSt917PPDAp+zfn0azZjeQkjKAV1+9hxIlguxOqFSBrPzLbA7sEpGfAYwx8UBXYHu+dboCo1335wETjTFG9OSy291wQwSJiQ+RkLCdQYMWs2rVPuqtyr/GD3ZFu4Kv7Q5QoLAQw6tvdOCvf21BUJCeMVWezVhVb40xPYBOIvK46/EjwJ0i8ky+dba61jngerzbtc7xi7Y1ABgAEBkZGR0fH1+kbOnp6YSHhxdpG1bzpExpadlMGb+ZpavS7Y7idW6rHcjzA2+gWrNadkfJ40l/W/l5Yi5PzATW5IqJiUkRkWaXLBARS25AD2B6vsePABMvWmcrEJXv8W6g4pW2Gx0dLUWVnJxc5G1YzeMyLVggX4bWl5F93xQpWVJkwQK7E/0Pj2qvBQvk29Da8kLPN8URpm1VWJ6YyxMziViTC9ggBdRUK0/vHATyf3MV5XquoHUOGGOCgDLACQszqOsVG0vHORB85gz0nAWxsXYn8lyxsdw5B86fOYPpq22lvIuVJyDXA3WMMTcZY0KA3sDF3wgmAY+67vcAvnK9IylPEBsL1atrESsMbSvlpSw70heRHGPMM8AXQCDwbxHZZowZi/NjRhLwATDTGLMLOInzjUEppZSbWHpdmYgsBhZf9Nwr+e5nAj2t3KdSSqnC0+vLlFLKj2jRV0opP6JFXyml/IgWfaWU8iNa9JVSyo9o0VdKKT9i2dg7xcUYcwz4pYibqQgcv+pa7uWJmUBzXQtPzASa61p4YiawJteNIlLp4ic9vuhbwRizQQoaeMhGnpgJNNe18MRMoLmuhSdmguLNpad3lFLKj2jRV0opP+IvRf99uwMUwBMzgea6Fp6YCTTXtfDETFCMufzinL5SSiknfznSV0ophRZ9pZTyKz5T9I0xnYwxO40xu4wxfytgeagxZrZr+TpjTE0PyfWYMeaYMWaj6/a4GzL92xhz1DVncUHLjTHmPVfmzcaY24s7UyFztTPGnMnXVq8UtJ7FmaobY5KNMduNMduMMX8tYB23t1chc7m1vYwxJYwx3xljNrkyjSlgHbe/DguZy+2vQ9d+A40xPxhjFhawrHjaqqA5FL3thnPSlt1ALSAE2AQ0uGidp4Gprvu9gdkekusxLppL2A252gC3A1svs7wzsAQwQAtgnYfkagcsdHNbVQVud92PAH4s4Hfo9vYqZC63tpfr/x/uuh8MrANaXLSOHa/DwuRy++vQtd/ngE8L+j0VV1v5ypF+c2CXiPwsIheAeKDrRet0BT523Z8HtDfGGA/I5XYishLnzGWX0xWYIU7fAmWNMVU9IJfbichhEfnedf8skApUu2g1t7dXIXO5lev/n+56GOy6XXyliNtfh4XM5XbGmCjgAWD6ZVYplrbylaJfDdif7/EBLn0B5K0jIjnAGaCCB+QCiHOdFphnjKlewHJ3K2xuO7R0fUxfYoxp6M4duz5e34bzSDE/W9vrCrnAze3lOl2xETgKLBORy7aVG1+HhckF7n8dvgsMBRyXWV4sbeUrRd+bfQ7UFJEmwDJ+f2dXl/oe53gitwL/BOa7a8fGmHAgAXhWRNLctd+ruUout7eXiOSKSFMgCmhujGlU3PssjELkcuvr0BjTBTgqIinFuZ+C+ErRPwjkf2eOcj1X4DrGmCCgDHDC7lwickJEslwPpwPRxZypMArTnm4nImm/fUwX53zMwcaYisW9X2NMMM7C+h8RSSxgFVva62q57Gov1/5OA8lAp4sW2fE6vGouG16HdwOxxpi9OE/73mOM+eSidYqlrXyl6K8H6hhjbjLGhOD80iPponWSgEdd93sAX4nrGxI7c1107jcW57lZuyUBf3JdldICOCMih+0OZYyp8ts5TWNMc5x/v8VaMFz7+wBIFZF3LrOa29urMLnc3V7GmErGmLKu+2FAR2DHRau5/XVYmFzufh2KyDARiRKRmjjrwlci0vei1YqlrYKKugFPICI5xphngC9wXjHzbxHZZowZC2wQkSScL5CZxphdOL8s7O0huf5ijIkFcly5HivuXMaYWTiv7KhojDkAjML55RYiMhVYjPOKlF1ABvDn4s5UyFw9gKeMMTnAeaC3G9647wYeAba4zgkDvAzUyJfLjvYqTC53t1dV4GNjTCDON5g5IrLQ7tdhIXO5/XVYEHe0lQ7DoJRSfsRXTu8opZQqBC36SinlR7ToK6WUH9Gir5RSfkSLvlJK+REt+kop5Ue06CullB/Roq+UUn5Ei75S18AY08MYk2WMuTHfcxOMMbuNMZF2ZlOqMLRHrlLXwDWWzXrgBxF5whjzAs7hce8WkZ/sTafU1fnE2DtKuYuIiDHmZWCRMWY3zvFu2mvBV95Cj/SVug7GmG9wzoz2oIgssTuPUoWl5/SVukbGmHuAW3HOvXrE5jhKXRM90lfqGhhjbgVWAkNwzm8aLiL32ZtKqcLToq9UIbmu2FkLTBWRsa4p9zYD94jIClvDKVVIWvSVKgRjTHlgDbBSRJ7M9/xsoIaItLQtnFLXQIu+Ukr5Ef0iVyml/IgWfaWU8iNa9JVSyo9o0VdKKT+iRV8ppfyIFn2llPIjWvSVUsqPaNFXSik/8v82IwqZeyG0JAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "plt.plot([0,1],[1,0],linewidth = 2,color='navy')\n",
    "plt.plot([0,1],[1,3],linewidth = 2,color='navy')\n",
    "plt.plot([1,3],[3,4],linewidth = 2,color='navy')\n",
    "plt.plot([1,2],[0,0],linewidth = 2,color='navy')\n",
    "plt.plot([2,3],[0,1],linewidth = 2,color='navy')\n",
    "plt.plot([3,4],[4,4],linewidth = 2,color='navy')\n",
    "plt.plot([3,4],[1,4],linewidth = 2,color='navy')\n",
    "plt.scatter(x=[1,2,3,1,2,4,0,1,3,3,2,3,1],y=[3,0,4,1,2,4,1,2,1,3,1,2,0],s=10,color='red')\n",
    "plt.xlabel('$x$',fontsize = 14)\n",
    "plt.ylabel('$y$',rotation = True,fontsize = 14)\n",
    "plt.grid()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dynamic Programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0-1 Knapsack Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Given weights and values of $n$ items, put these items in a knapsack of capacity $W$ to get the maximum total value in the knapsack.\n",
    "\n",
    "You cannot break an item, either pick the complete item or don’t pick it (0-1 property)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def knapsack_0_1(capacity, wt, val):\n",
    "    n = len(val)\n",
    "    K = [[0 for x in range(capacity + 1)] for x in range(n + 1)] \n",
    "  \n",
    "    for i in range(n + 1): \n",
    "        for w in range(capacity + 1): \n",
    "            if i == 0 or w == 0: \n",
    "                K[i][w] = 0\n",
    "            elif wt[i-1] <= w: \n",
    "                K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]],K[i-1][w]) \n",
    "            else: \n",
    "                K[i][w] = K[i-1][w] \n",
    "  \n",
    "    return K[n][capacity] \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum value to obtain: 220\n"
     ]
    }
   ],
   "source": [
    "value = [60, 100, 120] \n",
    "weight = [10, 20, 30] \n",
    "capacity = 50\n",
    "print('Maximum value to obtain:',knapsack_0_1(capacity, weight, value))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Longest Common Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**:  Given two sequences, find the length of longest substring (consecutive) present in both of them. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LCS(S1, S2):\n",
    "    n = len(S1)\n",
    "    m = len(S2)\n",
    "    K = [[0 for x in range(m + 1)] for x in range(n + 1)] \n",
    "    \n",
    "    res = 0\n",
    "    for i in range(n+1):\n",
    "        for j in range(m+1):\n",
    "            if i == 0 or j == 0:\n",
    "                K[i][j] = 0\n",
    "            elif S1[i-1] == S2[j-1]:\n",
    "                K[i][j] = K[i-1][j-1] + 1\n",
    "            \n",
    "            if res < K[i][j]:\n",
    "                res = K[i][j]\n",
    "                \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of longest common substring: 3\n"
     ]
    }
   ],
   "source": [
    "S1 = \"AGGTAB\"\n",
    "S2 = \"BGGTCACAB\"\n",
    "print(\"Length of longest common substring:\",LCS(S1, S2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Longest Common Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**:  Given two sequences, find the length of longest subsequence present in both of them. \n",
    "\n",
    "A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. \n",
    "\n",
    "For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LCS(S1, S2):\n",
    "    n = len(S1)\n",
    "    m = len(S2)\n",
    "    K = [[0 for x in range(m + 1)] for x in range(n + 1)] \n",
    "    \n",
    "    for i in range(n+1):\n",
    "        for j in range(m+1):\n",
    "            if i == 0 or j == 0:\n",
    "                K[i][j] = 0\n",
    "            elif S1[i-1] == S2[j-1]:\n",
    "                K[i][j] = K[i-1][j-1] + 1\n",
    "            else:\n",
    "                K[i][j] = max(K[i][j-1],K[i-1][j])\n",
    "    \n",
    "    return K[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of longest common subsequence: 4\n"
     ]
    }
   ],
   "source": [
    "S1 = \"AGGTAB\"\n",
    "S2 = \"GXTXAYB\"\n",
    "print(\"Length of longest common subsequence:\",LCS(S1, S2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Coin-Row Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: There is a row of $n$ coins whose values are some positive integers $c1$, $c2$, ..., $cn$, not necessarily distinct. \n",
    "\n",
    "The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cow_row(coins):\n",
    "    N = len(coins)\n",
    "    res = [0] * (N + 1)\n",
    "    res[1]  =coins[0]\n",
    "    \n",
    "    for i in range(2,len(res)):\n",
    "        res[i] = max(res[i-2]+coins[i-1],res[i-1])\n",
    "    \n",
    "    return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum amount of money: 17\n"
     ]
    }
   ],
   "source": [
    "coins = [5,1,2,10,6,2]\n",
    "print('Maximum amount of money:',cow_row(coins))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Coin-Collecting Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Several coins are placed in cells of an $N × M$ board, no more than one coin per cell. \n",
    "\n",
    "A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. \n",
    "\n",
    "On each step, the robot can move either one cell to the right or one cell down from its current location. When the robot visits a cell with a coin, it always picks up that coin. \n",
    "\n",
    "Find the maximum number of coins the robot can collect."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def robot_coin_collecting(B):\n",
    "    N  = len(B)\n",
    "    M = len(B[0])\n",
    "    T = [[0 for j in range(M)] for i in range(N)]\n",
    "    if B[0][0] == 1:\n",
    "        T[0][0] = 1\n",
    "    for i in range(1,M):\n",
    "        T[0][i] = T[0][i-1] + B[0][i]  \n",
    "    for i in range(1,N):\n",
    "        T[i][0] = T[i-1][0] + B[i][0]\n",
    "        \n",
    "    for i in range(1,N):\n",
    "        for j in range(1,M):\n",
    "            T[i][j] = max(T[i-1][j]+B[i][j],T[i][j-1]+B[i][j])\n",
    "    \n",
    "    return T[N-1][M-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum number of coins to collect: 5\n"
     ]
    }
   ],
   "source": [
    "board = [[0,0,0,0,1,0],\n",
    "         [0,1,0,1,0,0],\n",
    "         [0,0,0,1,0,1],\n",
    "         [0,0,1,0,0,1],\n",
    "         [1,0,0,0,1,0]]\n",
    "print('Maximum number of coins to collect:',robot_coin_collecting(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rat in a Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: A Maze is given as $N×N$ binary matrix of blocks where source block is the upper left most block, $maze[0][0]$, and destination block is lower rightmost block, $maze[N-1][N-1]$. \n",
    "\n",
    "A rat starts from source and has to reach the destination. \n",
    "\n",
    "The rat can move only in two directions: $forward$ and $down$.\n",
    "\n",
    "In the maze matrix, $0$ means the block is a dead end and $1$ means the block can be used in the path from source to destination. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_maze(maze): \n",
    "    N = len(maze)\n",
    "    res = [[0 for j in range(N)] for i in range(N)] \n",
    "      \n",
    "    if solve_maze_util(maze,0,0,res) == False: \n",
    "        print(\"Solution doesn't exist\")\n",
    "        return False\n",
    "      \n",
    "    print_res(res) \n",
    "    return True\n",
    "\n",
    "def solve_maze_util(maze,x,y,res): \n",
    "    N = len(maze)\n",
    "    if x == N-1 and y == N-1 and maze[x][y]== 1: \n",
    "        res[x][y] = 1\n",
    "        return True\n",
    "          \n",
    "    if is_safe(maze,x,y) == True: \n",
    "        res[x][y] = 1\n",
    "        \n",
    "        if solve_maze_util(maze,x+1,y,res) == True: \n",
    "            return True\n",
    "        \n",
    "        if solve_maze_util(maze,x,y+1,res) == True: \n",
    "            return True\n",
    "\n",
    "        res[x][y] = 0\n",
    "        return False\n",
    "    \n",
    "    return False\n",
    "  \n",
    "def is_safe(maze,x,y):\n",
    "    N = len(maze)\n",
    "    if x >= 0 and x < N and y >= 0 and y < N and maze[x][y] == 1:\n",
    "        return True\n",
    "      \n",
    "    return False\n",
    "\n",
    "def print_res(res):\n",
    "    for i in res: \n",
    "        for j in i:\n",
    "            print(str(j)+\" \", end =\"\") \n",
    "        print(\"\") \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution:\n",
      "1 0 0 0 \n",
      "1 1 0 0 \n",
      "0 1 0 0 \n",
      "0 1 1 1 \n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maze = [[1, 0, 0, 0],\n",
    "        [1, 1, 0, 1], \n",
    "        [0, 1, 0, 0], \n",
    "        [1, 1, 1, 1]] \n",
    "print('Solution:')\n",
    "solve_maze(maze)               "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Knight’s Tour Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Given a $N×N$ board with the Knight placed on the first block of an empty board. \n",
    "\n",
    "Moving according to the rules of chess Knight must visit each square exactly once. \n",
    "\n",
    "Print the order of each the cell in which they are visited."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_KT(N):\n",
    "    board = [[-1 for j in range(N)] for i in range(N)]\n",
    " \n",
    "    move_x = [2, 1, -1, -2, -2, -1, 1, 2]\n",
    "    move_y = [1, 2, 2, 1, -1, -2, -2, -1]\n",
    "    board[0][0] = 0\n",
    "    pos = 1\n",
    "    if(not solve_KT_util(N,board,0,0,move_x,move_y,pos)):\n",
    "        print(\"Solution doesn't exist\")\n",
    "    else:\n",
    "        print_solution(N,board)\n",
    "\n",
    "def solve_KT_util(N,board,cur_x,cur_y,move_x,move_y,pos):\n",
    "    if(pos == N**2):\n",
    "        return True\n",
    "    num_moves = len(move_x)\n",
    "    for i in range(num_moves):\n",
    "        new_x = cur_x + move_x[i]\n",
    "        new_y = cur_y + move_y[i]\n",
    "        if(is_safe(N,new_x,new_y,board)):\n",
    "            board[new_x][new_y] = pos\n",
    "            if(solve_KT_util(N,board,new_x,new_y,move_x,move_y,pos+1)):\n",
    "                return True\n",
    "            \n",
    "            board[new_x][new_y] = -1\n",
    "    return False\n",
    "\n",
    "def is_safe(N,x,y,board):\n",
    "    if(x >= 0 and y >= 0 and x < N and y < N and board[x][y] == -1):\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "def print_solution(N,board):\n",
    "    for i in range(N):\n",
    "        for j in range(N):\n",
    "            print(board[i][j], end=' ')\n",
    "        print('')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution:\n",
      "0 59 38 33 30 17 8 63 \n",
      "37 34 31 60 9 62 29 16 \n",
      "58 1 36 39 32 27 18 7 \n",
      "35 48 41 26 61 10 15 28 \n",
      "42 57 2 49 40 23 6 19 \n",
      "47 50 45 54 25 20 11 14 \n",
      "56 43 52 3 22 13 24 5 \n",
      "51 46 55 44 53 4 21 12 \n"
     ]
    }
   ],
   "source": [
    "print('Solution:')\n",
    "solve_KT(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Subset-Sum Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.\n",
    "\n",
    "It is assumed that the input set is unique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "def subset_sum(lst,target):\n",
    "    N = len(lst)\n",
    "    res = [False] * N\n",
    "    s = 0\n",
    "    sol = []\n",
    "    if s == target or len(lst) == 0:\n",
    "        print(\"Solution doesn't exist\")\n",
    "        return\n",
    "    subset_sum_util(lst,target,s,res,0,sol)\n",
    "    if len(sol) != 0:\n",
    "        print(sol)\n",
    "    else:\n",
    "        print(\"Solution doesn't exist\")\n",
    "\n",
    "def subset_sum_util(lst,target,s,res,i,sol):\n",
    "    for i in range(i,len(lst)):\n",
    "        if res[i] != True:\n",
    "            if s + lst[i] == target:\n",
    "                s += lst[i]\n",
    "                res[i] = True\n",
    "                temp = get_solution(lst,res)\n",
    "                sol.append(temp)\n",
    "                s -= lst[i]\n",
    "                res[i] = False\n",
    "            elif s + lst[i] < target:\n",
    "                    s += lst[i]\n",
    "                    res[i] = True\n",
    "                    if subset_sum_util(lst,target,s,res,i,sol) == False:\n",
    "                        s -= lst[i]\n",
    "                        res[i] = False\n",
    "                        \n",
    "    return False\n",
    "                \n",
    "def get_solution(lst,res):\n",
    "    temp = []\n",
    "    for i in range(len(lst)):\n",
    "        if res[i] == True:\n",
    "            temp.append(lst[i])\n",
    "    return temp\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution:\n",
      "[[1, 2, 3, 9], [1, 5, 9], [2, 5, 8], [15]]\n"
     ]
    }
   ],
   "source": [
    "lst = [1,2,3,5,8,9,15]\n",
    "print('Solution:')\n",
    "subset_sum(lst,15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hamiltonian-Circuit Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once. \n",
    "\n",
    "A Hamiltonian Circuit is a Hamiltonian Path such that there is an edge from the last vertex to the first vertex of the Hamiltonian Path. \n",
    "\n",
    "Determine whether a given graph contains Hamiltonian Circuit or not. \n",
    "\n",
    "If it contains, then print the path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph():  \n",
    "    def __init__(self,vertices):  \n",
    "        self.graph = [[0 for column in range(vertices)] for row in range(vertices)]  \n",
    "        self.V = vertices  \n",
    "\n",
    "def hamiltonian_circuit(G):\n",
    "    path = [-1] * G.V\n",
    "    path[0] = 0\n",
    "    \n",
    "    if hamiltonian_circuit_util(G,path,1) == False:\n",
    "        print(\"Solution does not exist\")\n",
    "    else:\n",
    "        path.append(0)\n",
    "        print(path)  \n",
    "    \n",
    "\n",
    "def hamiltonian_circuit_util(G,path,pos):\n",
    "    if pos == G.V:\n",
    "        if G.graph[path[pos-1]][path[0]] == 1:\n",
    "            return True\n",
    "        else:  \n",
    "            return False\n",
    "        \n",
    "    for v in range(1,G.V):\n",
    "        if is_safe(G,v,pos,path) == True:  \n",
    "            path[pos] = v\n",
    "            if hamiltonian_circuit_util(G,path,pos+1) == True:\n",
    "                return True\n",
    "\n",
    "            path[pos] = -1\n",
    "  \n",
    "    return False\n",
    "  \n",
    "def is_safe(G,v,pos,path):\n",
    "    if G.graph[path[pos-1]][v] == 0:\n",
    "        return False\n",
    "    for vertex in path:  \n",
    "        if vertex == v:  \n",
    "            return False\n",
    "    return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution:\n",
      "[0, 1, 2, 4, 3, 0]\n"
     ]
    }
   ],
   "source": [
    "G = Graph(5)  \n",
    "G.graph = [[0,1,0,1,0],\n",
    "           [1,0,1,1,1],  \n",
    "           [0,1,0,0,1],\n",
    "           [1,1,0,0,1],  \n",
    "           [0,1,1,1,0]]  \n",
    "\n",
    "print('Solution:')  \n",
    "hamiltonian_circuit(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### N-Queens Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: place $N$ chess Queens on an $N×N$ chessboard so that no two Queens attack each other."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_NQ(N):\n",
    "    board = [[0 for j in range(N)] for i in range(N)]\n",
    "    if solve_NQ_util(board,0,N) == False:\n",
    "        print(\"Solution doesn't exist\")\n",
    "        return False\n",
    "    else:\n",
    "        print_solution(board,N)\n",
    "        return True\n",
    "\n",
    "def solve_NQ_util(board,col,N):\n",
    "    if col >= N:\n",
    "        return True\n",
    "    \n",
    "    for i in range(N):\n",
    "        if is_safe(board,i,col,N):\n",
    "            board[i][col] = 1\n",
    "            if solve_NQ_util(board,col+1,N) == True:\n",
    "                return True\n",
    "            \n",
    "            board[i][col] = 0\n",
    "    \n",
    "    return False\n",
    "\n",
    "def is_safe(board,row,col,N):\n",
    "    for i in range(col):\n",
    "        if board[row][i] == 1:\n",
    "            return False\n",
    "    \n",
    "    for i,j in zip(range(row,-1,-1),range(col,-1,-1)):\n",
    "        if board[i][j] == 1:\n",
    "            return False\n",
    "    \n",
    "    for i,j in zip(range(row,N,1),range(col,-1,-1)):\n",
    "        if board[i][j] == 1:\n",
    "            return False\n",
    "    \n",
    "    return True\n",
    "\n",
    "def print_solution(board,N):\n",
    "    for i in range(N):\n",
    "        for j in range(N):\n",
    "            print(board[i][j],end=' ')\n",
    "        print('')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 1 0 \n",
      "1 0 0 0 \n",
      "0 0 0 1 \n",
      "0 1 0 0 \n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve_NQ(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Travelling Salesman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem**: Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns back to the starting point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_travelling_salesman(G):\n",
    "    N = len(G)\n",
    "    v = [False for i in range(N)]\n",
    "    v[0] = True\n",
    "    res = []\n",
    "    solve_travelling_salesman_util(G,v,0,N,1,0,res)\n",
    "    \n",
    "    return min(res)\n",
    "\n",
    "def solve_travelling_salesman_util(G,v,cur_pos,N,count,cost,res):\n",
    "    if count == N and G[cur_pos][0] != 0:\n",
    "        res.append(cost+G[cur_pos][0])\n",
    "        return\n",
    "    \n",
    "    for i in range(N):\n",
    "        if v[i] == False and G[cur_pos][i] != 0:\n",
    "            v[i] = True\n",
    "            solve_travelling_salesman_util(G,v,i,N,count+1,cost+G[cur_pos][i],res)\n",
    "            \n",
    "            v[i] = False\n",
    "    return\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cost for shortest possible route: 80\n"
     ]
    }
   ],
   "source": [
    "G = [[0,10,15,20], \n",
    "     [10,0,35,25], \n",
    "     [15,35,0,30], \n",
    "     [20,25,30,0]]\n",
    "\n",
    "print(\"Cost for shortest possible route:\",solve_travelling_salesman(G))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}