{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Datastructure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"pic/datas.png\" width=\"70%\" height = \"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"pic/fig1.jpg\" width=\"50%\" height = \"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"pic/lin.jpg\" width=\"40%\" height = \"40%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"pic/array.png\" width=\"50%\" height = \"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Complexity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://miro.medium.com/max/1898/1*r3ud6C_p9hNAwjHF9guILA.png\" width=\"150%\" height = \"150%\">\n",
    "\n",
    "[image source](https://becominghuman.ai/cheat-sheets-for-ai-neural-networks-machine-learning-deep-learning-big-data-science-pdf-f22dc900d2d7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Iteration, Recurrsion & Dynamic Coding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.1 Factorial (Iteration)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time as time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial_iteration(n):\n",
    "    product = 1\n",
    "    for i in range(1,n+1):\n",
    "        product = product*i\n",
    "    return product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- step 1: 1x1\n",
    "- step 2: 1x2\n",
    "- step 3: 1x2x3\n",
    "- .\n",
    "- .\n",
    "- step 10: 1x2x3x4x5x6x7x8x9x10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "265252859812191058636308480000000 5.2928924560546875e-05\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "p = factorial_iteration(30)\n",
    "t2 = time.time()\n",
    "print(p, t2-t1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.2 Factorial (Recursion)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial_recursion(n):\n",
    "    if n==1 or n==0:\n",
    "        return 1\n",
    "    else:\n",
    "        return n*factorial_recursion(n-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- step 1: 10x(9!)\n",
    "- step 2: 10x9x(8!)\n",
    "- step 3: 10x9x8x(7!) \n",
    "\n",
    "- .  \n",
    "- . \n",
    "\n",
    "- step 10: 10x9x8x7x6x5x4x3x2x(1!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "265252859812191058636308480000000 7.796287536621094e-05\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "p = factorial_recursion(30)\n",
    "t2 = time.time()\n",
    "print(p, t2-t1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.3 Factorial (Dynamic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial_dynamic(n):\n",
    "    fct = [1 for i in range(n+1)]\n",
    "    fct[0] =1\n",
    "    fct[1] =1\n",
    "    for k in range(2,n+1):\n",
    "        fct[k] = k*fct[k-1]\n",
    "    return fct[n]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- F[0] =1\n",
    "- F[1] =1\n",
    "- F[2] = 2\n",
    "- F[3] = 6\n",
    "- .\n",
    "- .\n",
    "- .\n",
    "- F[10] = 10!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "265252859812191058636308480000000 6.413459777832031e-05\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "p = factorial_dynamic(30)\n",
    "t2 = time.time()\n",
    "print(p, t2-t1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.4 Fibonacy No"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..\n",
    "    \n",
    "$F_n = F_{n-1} + F_{n-2}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![img](https://www.w3resource.com/w3r_images/python-conditional-image-exercise-9.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci_recursive(n): \n",
    "    if n<0: \n",
    "        print(\"Incorrect input\") \n",
    "    # First Fibonacci number is 0 \n",
    "    elif n==1: \n",
    "        return 0\n",
    "    # Second Fibonacci number is 1 \n",
    "    elif n==2: \n",
    "        return 1\n",
    "    else: \n",
    "        return fibonacci_recursive(n-1)+fibonacci_recursive(n-2) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"http://www.introprogramming.info/wp-content/uploads/2013/07/clip_image00525.png\" width=\"40%\" height = \"40%\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "63245986 36.67340326309204\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "F = fibonacci_recursive(40)\n",
    "t2 = time.time()\n",
    "print(F, t2-t1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "FibArray = [0,1] \n",
    "  \n",
    "def fibonacci_dynamic(n): \n",
    "    if n<0: \n",
    "        print(\"Incorrect input\") \n",
    "    elif n<=len(FibArray): \n",
    "        return FibArray[n-1] \n",
    "    else: \n",
    "        temp_fib = fibonacci_dynamic(n-1)+fibonacci_dynamic(n-2) \n",
    "        FibArray.append(temp_fib) \n",
    "        return temp_fib "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://camo.githubusercontent.com/31777b548b585d1f0dbef600352ed5867dbaef66/687474703a2f2f692e696d6775722e636f6d2f626771743265722e706e67\" width=\"60%\" height = \"60%\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "63245986 9.298324584960938e-05\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "F = fibonacci_dynamic(40)\n",
    "t2 = time.time()\n",
    "print(F, t2-t1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Greedy and Divide & Conqure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.1 Greedy algorithm: Find minimum number of currency notes and values that sum to given amount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countCurrency(amount): \n",
    "    \n",
    "    notes = [1000, 500, 200, 100, 50, 20, 10, 5, 1] \n",
    "    noteCounter = [0, 0, 0, 0, 0, 0, 0, 0, 0] \n",
    "    \n",
    "    for note, j in zip(notes, noteCounter): \n",
    "        if amount >= note: \n",
    "            j = amount // note \n",
    "            amount = amount - (j * note)\n",
    "            print (note ,\" : \", j) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "500  :  1\n",
      "200  :  1\n",
      "100  :  1\n",
      "50  :  1\n",
      "10  :  1\n",
      "5  :  1\n",
      "1  :  3\n"
     ]
    }
   ],
   "source": [
    "amount = 868\n",
    "countCurrency(amount) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.2. Divide & Conqure: Merge Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://www.geeksforgeeks.org/wp-content/uploads/Merge-Sort-Tutorial.png\" width=\"40%\" height = \"40%\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeSort(arr): \n",
    "    if len(arr) >1: \n",
    "        \n",
    "        mid = len(arr)//2 #Finding the mid of the array \n",
    "        L = arr[:mid] # Dividing the array elements \n",
    "        R = arr[mid:] # into 2 halves \n",
    "\n",
    "        mergeSort(L) # Sorting the first half \n",
    "        mergeSort(R) # Sorting the second half \n",
    "\n",
    "        i = j = k = 0\n",
    "        \n",
    "        # Copy data to temp arrays L[] and R[] \n",
    "        while i < len(L) and j < len(R): \n",
    "            if L[i] < R[j]: \n",
    "                arr[k] = L[i] \n",
    "                i+=1\n",
    "            else: \n",
    "                arr[k] = R[j] \n",
    "                j+=1\n",
    "            k+=1\n",
    "\n",
    "        # Checking if any element was left \n",
    "        while i < len(L): \n",
    "            arr[k] = L[i] \n",
    "            i+=1\n",
    "            k+=1\n",
    "\n",
    "        while j < len(R): \n",
    "            arr[k] = R[j] \n",
    "            j+=1\n",
    "            k+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Given array is\n",
      "[12, 11, 13, 5, 6, 7]\n",
      "Sorted array is: \n",
      "[5, 6, 7, 11, 12, 13]\n"
     ]
    }
   ],
   "source": [
    "arr = [12, 11, 13, 5, 6, 7] \n",
    "print (\"Given array is\", end=\"\\n\") \n",
    "print(arr) \n",
    "mergeSort(arr) \n",
    "print(\"Sorted array is: \", end=\"\\n\") \n",
    "print(arr) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}