dynamic programming-Fibonacci numbers-for-github.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Computer Science: Dynamic programming: Fibonacci numbers\n",
    "###### by Hamed Shah-Hosseini\n",
    "**Reminder:** Fibonacci numbers $F_n$ are defined by:\n",
    "- $F_0=0, F_1=1;\\:  F_n=F_{n-1}+F_{n-2},\\: n>1$\n",
    "\n",
    "<br>Explanation in English: https://www.pinterest.com/HamedShahHosseini/\n",
    "<br>Explanation in Persian: https://www.instagram.com/words.persian\n",
    "<br> Python code at: https://github.com/ostad-ai/Computer-Science"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# simple recursive implementation\n",
    "def fib(n):\n",
    "    if n<=1: \n",
    "        return n    \n",
    "    else:\n",
    "        return fib(n-1)+fib(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Simple recursive:\n",
      "Time of fib(32)=2178309 is: 1.32601 secs.\n"
     ]
    }
   ],
   "source": [
    "#experiment with simple recursive\n",
    "n=32\n",
    "start=time.time()\n",
    "fb=fib(n)\n",
    "end=time.time()\n",
    "print('Simple recursive:')\n",
    "print(f'Time of fib({n})={fb} is: {end-start:.5f} secs.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#top-down Dynamic Programming\n",
    "def fib_td(n,memo={0:0,1:1}):\n",
    "    if n not in memo.keys():\n",
    "        memo[n]=fib_td(n-1)+fib_td(n-2)\n",
    "    return memo[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Top-down Dynamic Programming:\n",
      "Time of fib(32)=2178309 is: 0.00000 secs.\n"
     ]
    }
   ],
   "source": [
    "#experiment with top-down DP\n",
    "n=32 \n",
    "start=time.time()\n",
    "fb=fib_td(n)\n",
    "end=time.time()\n",
    "print('Top-down Dynamic Programming:')\n",
    "print(f'Time of fib({n})={fb} is: {end-start:.5f} secs.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#bottom-up Dynamic Programming\n",
    "def fib_bu(n):\n",
    "    memo=[0]*(n+1)\n",
    "    memo[1]=1\n",
    "    for i in range(2,n+1):\n",
    "        memo[i]=memo[i-1]+memo[i-2]\n",
    "    return memo[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bottom-up Dynamic Programming:\n",
      "Time of fib(32)=2178309 is: 0.00000 secs.\n"
     ]
    }
   ],
   "source": [
    "#experiment with bottom-up DP\n",
    "n=32\n",
    "start=time.time()\n",
    "fb=fib_bu(n)\n",
    "end=time.time()\n",
    "print('Bottom-up Dynamic Programming:')\n",
    "print(f'Time of fib({n})={fb} is: {end-start:.5f} secs.')"
   ]
  },
  {
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}