Jul 13.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Computing:\n",
    "\n",
    "0. Number System\n",
    "1. Basic constructs\n",
    "2. Recursion\n",
    "3. Big O - complexity\n",
    "4. Sorting\n",
    "5. Dictionary\n",
    "6. Binary Search\n",
    "7. Classes\n",
    "8. Basics of Linear Regression\n",
    "9. Basics of Linux\n",
    "10. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Q: Data Structures."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Trees - Binary Trees, Max Heap, breath first search and depth first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2*3 + 4\n",
    "class Node():\n",
    "    def __init__(self, typ=0, val=None, left=None, right=None):\n",
    "        #type 0 - operator otherwise it is a value\n",
    "        self.typ = typ\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "    def __repr__(self, indent=''):\n",
    "        leftstr, rightstr = '', ''\n",
    "        if self.left:\n",
    "            leftstr = self.left.__repr__(indent + '\\t')\n",
    "        if self.right:\n",
    "            rightstr = self.right.__repr__(indent + '\\t')\n",
    "        return \"%s%s:%s  -> \\n %s \\n %s\" % (indent,self.val,self.typ, leftstr, rightstr)\n",
    "    def eval(self):\n",
    "        typ = self.typ\n",
    "        val = self.val\n",
    "        if typ == 1:\n",
    "            return val\n",
    "        else:\n",
    "            l, r = None, None\n",
    "            if self.left:\n",
    "                l = self.left.eval()\n",
    "            if self.right:\n",
    "                r = self.right.eval()\n",
    "            if val == '*':\n",
    "                return l * r\n",
    "            elif val == '+':\n",
    "                return l + r\n",
    "            elif val == '-':\n",
    "                return l - r\n",
    "            elif val == '/':\n",
    "                return l /r \n",
    "            elif val == '^':\n",
    "                return l ** r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "_2 = Node(typ=1, val = 2)\n",
    "_3 = Node(typ=1, val = 3)\n",
    "_mul = Node(typ=0, val = '*', left=_2, right=_3)\n",
    "_4 = Node(typ=1, val = 4)\n",
    "tree = Node(typ=0, val = '+', left=_mul, right = _4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+:0  -> \n",
      " \t*:0  -> \n",
      " \t\t2:1  -> \n",
      "  \n",
      "  \n",
      " \t\t3:1  -> \n",
      "  \n",
      "  \n",
      " \t4:1  -> \n",
      "  \n",
      " \n"
     ]
    }
   ],
   "source": [
    "print(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.eval()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [],
   "source": [
    "# def toTree(exp):\n",
    "#     return Node...\n",
    "# return ... toTree('2+3*6^2')\n",
    "# https://github.com/girisandeep/calcuchat/blob/master/lib/calc.dart"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Parsing and expression string into a tree (token tree/parse tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [],
   "source": [
    "# SQL -> parse it -> TREE\n",
    "# C++ -> parse it -> TREE -> execute it\n",
    "# Compiler Compiler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [],
   "source": [
    "# yacc -> C++, C, Java\n",
    "# javacc\n",
    "# antlr - python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [],
   "source": [
    "# https://www.antlr.org/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Problem:\n",
    "     We have lot of additions, deletions and find operation on our continously.\n",
    "     We need a good mechanism\n",
    "\n",
    " Suggestion: Why not list?\n",
    "  - insert: O(1)\n",
    "  - Delete: find - O(n), moving O(n)\n",
    "  - find: O(n)\n",
    "\n",
    "Why not maintain a sorted the list\n",
    " - insert - n log n\n",
    " - find - log n\n",
    " - delete - o (n)\n",
    " \n",
    " Why not do in a dictionary:\n",
    " - insert - Order(1)\n",
    " - delete - O(1)\n",
    " - find - O(1)\n",
    " - TOO MUCH MEMORY"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Binary Search Tree\n",
    "\n",
    "class Node():\n",
    "    def __init__(self, val=None, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "    def __repr__(self, indent=''):\n",
    "        leftstr, rightstr = '', ''\n",
    "        if self.left:\n",
    "            leftstr = self.left.__repr__(indent + '\\t')\n",
    "        if self.right:\n",
    "            rightstr = self.right.__repr__(indent + '\\t')\n",
    "        return f\"{self.val} -> \\n {indent} + {leftstr} \\n {indent} * {rightstr}\"\n",
    "    \n",
    "    def insert(self, node):\n",
    "        if node.val < self.val:\n",
    "            if self.left == None:\n",
    "                self.left = node\n",
    "            else:\n",
    "                self.left.insert(node)\n",
    "        else:\n",
    "            if self.right == None:\n",
    "                self.right = node\n",
    "            else:\n",
    "                self.right.insert(node)\n",
    "    def find(self, v):\n",
    "        if self.val == v:\n",
    "            return self\n",
    "        elif v < self.val:\n",
    "            if self.left == None:\n",
    "                return None\n",
    "            else:\n",
    "                return self.left.find(v)\n",
    "        else:\n",
    "            if self.right == None:\n",
    "                return None\n",
    "            else:\n",
    "                return self.right.find(v)\n",
    "\n",
    "class BST():\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "    def __repr__(self, indent=''):\n",
    "        if self.root:\n",
    "            return self.root.__repr__()\n",
    "    def insert(self, val):\n",
    "        n = Node(val)\n",
    "        if self.root == None:\n",
    "            self.root = n\n",
    "        else:\n",
    "            self.root.insert(n)\n",
    "    def find(self, v):\n",
    "        if self.root == None:\n",
    "            return None\n",
    "        else:\n",
    "            return self.root.find(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {},
   "outputs": [],
   "source": [
    "bst = BST()\n",
    "bst.insert(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10 -> \n",
       "  +  \n",
       "  * "
      ]
     },
     "execution_count": 182,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bst.root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {},
   "outputs": [],
   "source": [
    "bst.insert(12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10 -> \n",
       "  +  \n",
       "  * 12 -> \n",
       " \t +  \n",
       " \t * "
      ]
     },
     "execution_count": 184,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bst.root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "metadata": {},
   "outputs": [],
   "source": [
    "bst.insert(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10 -> \n",
       "  + 1 -> \n",
       " \t +  \n",
       " \t *  \n",
       "  * 12 -> \n",
       " \t +  \n",
       " \t * "
      ]
     },
     "execution_count": 186,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10 -> \n",
       "  + 1 -> \n",
       " \t +  \n",
       " \t *  \n",
       "  * 12 -> \n",
       " \t + 11 -> \n",
       " \t\t +  \n",
       " \t\t *  \n",
       " \t * "
      ]
     },
     "execution_count": 187,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bst.insert(11)\n",
    "bst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10 -> \n",
       "  + 1 -> \n",
       " \t +  \n",
       " \t *  \n",
       "  * 12 -> \n",
       " \t + 11 -> \n",
       " \t\t +  \n",
       " \t\t *  \n",
       " \t * 13 -> \n",
       " \t\t +  \n",
       " \t\t * "
      ]
     },
     "execution_count": 188,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bst.insert(13)\n",
    "bst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10 -> \n",
       "  + 1 -> \n",
       " \t +  \n",
       " \t * 3 -> \n",
       " \t\t +  \n",
       " \t\t *  \n",
       "  * 12 -> \n",
       " \t + 11 -> \n",
       " \t\t +  \n",
       " \t\t *  \n",
       " \t * 13 -> \n",
       " \t\t +  \n",
       " \t\t * "
      ]
     },
     "execution_count": 189,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bst.insert(3)\n",
    "bst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = bst.find(13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13 -> \n",
       "  +  \n",
       "  * "
      ]
     },
     "execution_count": 193,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n"
   ]
  },
  {
   "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.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}