script.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  `Data structures and Algorithms Notebook `\n",
    "* The algorithm to use primarily depends on the type of data structure you use."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `1. Data Structures`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Arrays\n",
    "* A one-dimensional array is composed of multiple sequential <b>homogeneous</b> elements stored in <b>contiguous</b> bytes of memory and allows for random access to the individual elements.\n",
    "* A list in python is a collection of items which can contain elements of varying data types.\n",
    "* Once an array is created it's size is fixed so if you want to add an element after array is full then we have to create a new array with +1 size and copy the old array then add new element.\n",
    "* (Python)List can grow and shrink during execution as elements are added or removed.\n",
    "* Python doesn't have an array implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ctypes\n",
    "\n",
    "class Array:\n",
    "    def __init__(self, size):\n",
    "        assert size > 0, \"Array size should be greater than 0\"\n",
    "        self.size = size\n",
    "        PyArrayObject = ctypes.py_object * size\n",
    "        self.array = PyArrayObject()\n",
    "        self.clear(None)\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def __getitem__(self, index):\n",
    "        return self.array[index]\n",
    "\n",
    "    def __setitem__(self, index, value):\n",
    "        assert index >= 0 and index < len(self), \"Array subs out of range\"\n",
    "        self.array[index] = value\n",
    "\n",
    "    def clear(self, value):\n",
    "        for i in range(len(self)):\n",
    "            self.array[i] = value\n",
    "\n",
    "    def iter(self):\n",
    "        return _Arrayiterator(self.array)\n",
    "\n",
    "\n",
    "class _Arrayiterator:\n",
    "    def __init__(self, array):\n",
    "        self.narray = array\n",
    "        self.curindex = 0\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        if self.curindex < len(self.narray):\n",
    "            entry = self.narray[self.curindex]\n",
    "            self.curindex += 1\n",
    "            return entry\n",
    "        else:\n",
    "            raise StopIteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Array contains: \n",
      "21\n",
      "319\n",
      "485\n"
     ]
    }
   ],
   "source": [
    "arr = Array(3)\n",
    "arr[0] = 21\n",
    "arr[1] = 319\n",
    "arr[2] = 485\n",
    "\n",
    "print(\"Array contains: \")\n",
    "for i in arr:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linked List\n",
    "* Like Arrays and list Linked Lists can also be used for storing collection of nodes, which store data.\n",
    "* Stores a collection in a linear order.\n",
    "* Requires smaler memory allocations.\n",
    "* Requires no element shifts for insertions and deletions\n",
    "* Does not require contiguous block of memory\n",
    "* Disadvantage - Requires more time to access an element\n",
    "\n",
    "There are three main types:\n",
    "* Singly Linked List\n",
    "* Doubly Linked List\n",
    "* Circular Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Singly Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SLLNode:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class SinglyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.size = 0\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def __contains__(self, data):\n",
    "        curNode = self.head\n",
    "        while curNode is not None and curNode.data != data:\n",
    "            curNode = curNode.next\n",
    "            \n",
    "        return curNode is not None\n",
    "    \n",
    "    def reverse(self):\n",
    "        prev = None\n",
    "        current = self.head\n",
    "        while(current is not None):\n",
    "            next = current.next\n",
    "            current.next = prev\n",
    "            prev = current\n",
    "            current = next\n",
    "        self.head = prev\n",
    "\n",
    "    def addAtBegin(self, data):\n",
    "        newNode = SLLNode(data)\n",
    "        newNode.next = self.head\n",
    "        self.head = newNode\n",
    "        self.size += 1\n",
    "\n",
    "    def addAtEnd(self, data):\n",
    "        curNode = self.head\n",
    "        newNode = ListNode(data)\n",
    "        while curNode.next is not None:\n",
    "            curNode = curNode.next\n",
    "        curNode.next = newNode\n",
    "        self.size += 1\n",
    "\n",
    "    def addAtIndex(self, index, data):\n",
    "        if index > len(self) or index < 0:\n",
    "            return\n",
    "        else:\n",
    "            if index == 0:\n",
    "                self.addAtBegin(data)\n",
    "            else:\n",
    "                if index == len(self) - 1:\n",
    "                    self.addAtEnd(data)\n",
    "                else:\n",
    "                    curNode = self.head \n",
    "                    newNode = ListNode(data)\n",
    "                    count = 1 \n",
    "                    \n",
    "                    while count < index - 1:\n",
    "                        count += 1\n",
    "                        curNode = curNode.next\n",
    "                        \n",
    "                    newNode = curNode.next\n",
    "                    curNode.next = newNode\n",
    "                    self.size += 1\n",
    "\n",
    "    def deleteElement(self, data):\n",
    "        predNode = None\n",
    "        curNode = self.head\n",
    "        \n",
    "        while curNode != None and curNode.data != data:\n",
    "            predNode = curNode\n",
    "            curNode = curNode.next\n",
    "            \n",
    "        assert curNode is not None, \"The element does not exist in the linked list\"\n",
    "        \n",
    "        if (curNode == self.head):\n",
    "            self.head = curNode.next\n",
    "        else:\n",
    "            predNode.next = curNode.next\n",
    "        self.size -= 1\n",
    "        \n",
    "        return curNode.data\n",
    "\n",
    "    def deleteFirst(self):\n",
    "        assert self.size == 0, \"Cannot remove from an empty List\"\n",
    "        self.head = self.head.next\n",
    "        self.size -= 1\n",
    "\n",
    "    def deleteLast(self):\n",
    "        if self.size == 1:\n",
    "            pass\n",
    "        else:\n",
    "            curNode = self.head\n",
    "            prevNode = self.head\n",
    "            while curNode.next is not None:\n",
    "                curNode = curNode.next\n",
    "                prevNode = curNode\n",
    "            prevNode.next = None\n",
    "            self.size -= 1\n",
    "\n",
    "    def deleteAtIndex(self, index):\n",
    "        if index == 0:\n",
    "            self.deleteFirst()\n",
    "        else:\n",
    "            if index == len(self) - 1:\n",
    "                self.deleteLast()\n",
    "            else:\n",
    "                prevNode = self.head\n",
    "                curNode = self.head\n",
    "                count = 1\n",
    "                while count < index - 1:\n",
    "                    prevNode = curNode\n",
    "                    curNode = curNode.next\n",
    "                prevNode.next = curNode.next\n",
    "                self.size -= 1\n",
    "\n",
    "    def clear(self):\n",
    "        self.head = None\n",
    "\n",
    "    def __iter__(self):\n",
    "        return _LLIterator(self.head)\n",
    "\n",
    "\n",
    "class _LLIterator:\n",
    "    def __init__(self, head):\n",
    "        self.curNode = head\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        if self.curNode is None:\n",
    "            raise StopIteration\n",
    "        else:\n",
    "            item = self.curNode.data\n",
    "            self.curNode = self.curNode.next\n",
    "            return item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Singly Linked List contains: \n",
      "32\n",
      "12\n",
      "43\n",
      "56\n",
      "47\n",
      "\n",
      "Is 3 present in SLL: False\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "ll1 = SinglyLinkedList()\n",
    "ll1.addAtIndex(0, 12)\n",
    "ll1.addAtBegin(32)\n",
    "ll1.addAtEnd(43)\n",
    "ll1.addAtEnd(56)\n",
    "ll1.addAtEnd(47)\n",
    "ll1.addAtIndex(3, 112)\n",
    "\n",
    "print(\"Singly Linked List contains: \")\n",
    "for i in ll1:\n",
    "    print(i)\n",
    "    \n",
    "print()\n",
    "print(\"Is 3 present in SLL:\", 3 in ll1)  # invoking contains\n",
    "print(len(ll1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Doubly Linked List\n",
    "* Contains link to the next node, data component like SLL and also a link to preceding node.\n",
    "* A <b>head</b> refrence is used to refer to first  node. A <b>tail</b> refrence is optional."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DLLNode:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.prev = None\n",
    "        self.next = None\n",
    "\n",
    "        \n",
    "class DoublyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.size = 0\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def insertAtStart(self, data):\n",
    "        newNode = DLLNode(data)\n",
    "        \n",
    "        if (self.head == None):\n",
    "            self.head = newNode\n",
    "        else:\n",
    "            newNode.prev = None\n",
    "            newNode.next = self.head\n",
    "            self.head.prev = newNode\n",
    "            self.head = newNode\n",
    "\n",
    "    def insertAtEnd(self, data):\n",
    "        newNode = DLLNode(data)\n",
    "        if (self.head == None):\n",
    "            self.head = newNode\n",
    "        else:\n",
    "            curNode = self.head\n",
    "            \n",
    "            while curNode.next != None:\n",
    "                curNode = curNode.next\n",
    "                \n",
    "            curNode.next = newNode\n",
    "            newNode.prev = curNode\n",
    "\n",
    "            # newNode.next is already None so no need to change\n",
    "\n",
    "    def insertAtIndex(self, index, data):\n",
    "        assert index >= 0 or len(self), \"array index out of range\"\n",
    "        \n",
    "        if index == 0:\n",
    "            self.insertAtStart(data)\n",
    "        else:\n",
    "            if index == len(self) - 1:\n",
    "                self.insertAtEnd(data)\n",
    "            else:\n",
    "                count = 0\n",
    "                curNode = self.head\n",
    "                newNode = DLLNode(data)\n",
    "                \n",
    "                while count != index - 1:\n",
    "                    curNode = curNode.next\n",
    "                    count += 1\n",
    "                    \n",
    "                tempNode = curNode.next\n",
    "                curNode.next = newNode\n",
    "                newNode.next = tempNode\n",
    "\n",
    "    def deleteAtStart(self):\n",
    "        assert len(self) == 0, \"Cannot remove from an empty array\"\n",
    "        \n",
    "        item = self.head.data\n",
    "        self.head.next.prev = None\n",
    "        self.head = self.head.next\n",
    "        self.size -= 1\n",
    "        \n",
    "        return item\n",
    "\n",
    "    def deleteAtEnd(self):\n",
    "        pass  # use self.tail later\n",
    "\n",
    "    def deleteAtIndex(self, index):\n",
    "        assert index >= 0 or index < len(self), \"Index out of range\"\n",
    "        \n",
    "        if index == 0:\n",
    "            self.deleteAtStart()\n",
    "        else:\n",
    "            count = 0\n",
    "            curNode = self.head\n",
    "            \n",
    "            while count != index - 1:\n",
    "                curNode = curNode.next\n",
    "                count += 1\n",
    "                \n",
    "            item = curNode.next.data\n",
    "            curNode.next = curNode.next.next\n",
    "        self.size -= 1\n",
    "        \n",
    "        return item\n",
    "\n",
    "    def __iter__(self):\n",
    "        return _LLIterator(self.head)\n",
    "\n",
    "\n",
    "class _LLIterator:\n",
    "    def __init__(self, head):\n",
    "        self.curNode = head\n",
    "        self.curNode.prev = None\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        if self.curNode is None:\n",
    "            raise StopIteration\n",
    "        else:\n",
    "            item = self.curNode.data\n",
    "            self.curNode.prev = self.curNode\n",
    "            self.curNode = self.curNode.next\n",
    "            \n",
    "            return item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Doubly Linked List contains: \n",
      "101\n",
      "16\n",
      "15\n",
      "14\n",
      "13\n",
      "12\n",
      "18\n",
      "\n",
      "\n",
      "After inserting 41 at index 2 and deleting 101: \n",
      "16\n",
      "41\n",
      "15\n",
      "14\n",
      "13\n",
      "12\n",
      "18\n",
      "\n",
      "Some more deletions at index 2 and 1: \n",
      "15\n",
      "41\n",
      "\n",
      "Final DLL: \n",
      "16\n",
      "14\n",
      "13\n",
      "12\n",
      "18\n"
     ]
    }
   ],
   "source": [
    "# TESTING\n",
    "ddl = DoublyLinkedList()\n",
    "ddl.insertAtStart(12)\n",
    "ddl.insertAtStart(13)\n",
    "ddl.insertAtStart(14)\n",
    "ddl.insertAtStart(15)\n",
    "ddl.insertAtStart(16)\n",
    "ddl.insertAtEnd(18)\n",
    "ddl.insertAtIndex(0, 101)\n",
    "\n",
    "print(\"Doubly Linked List contains: \")\n",
    "for i in ddl:\n",
    "    print(i)\n",
    "    \n",
    "print()\n",
    "ddl.insertAtIndex(2, 41)\n",
    "ddl.deleteAtStart()\n",
    "\n",
    "print(\"\\nAfter inserting 41 at index 2 and deleting 101: \")\n",
    "for i in ddl:\n",
    "    print(i)\n",
    "\n",
    "print(\"\\nSome more deletions at index 2 and 1: \")\n",
    "print(ddl.deleteAtIndex(2))\n",
    "print(ddl.deleteAtIndex(1))\n",
    "\n",
    "print(\"\\nFinal DLL: \")\n",
    "for i in ddl:\n",
    "    print(i)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Circular Linked List\n",
    "* the nodes form a continuous circle.\n",
    "* The circular linked list allows for a complete traversal of the nodes starting with any node in the list.\n",
    "* It is also commonly used for applications in which data is processed in a round-robin fashion. For example, when scheduling the use of a CPU, the operating system must cycle through all of the processes running on a computer, allowing each an opportunity to use the processor for a short period of time\n",
    "* A single external reference variable is used to point to a node within the list. Technically, this could be any node in the list, but for convenience, the external reference is commonly set to the last node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CLLNode:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "class CLL:\n",
    "    def __init__(self):\n",
    "        self.headRef = None\n",
    "        \n",
    "    def insert(self, data):\n",
    "        node = CLLNode(data)\n",
    "\n",
    "        if self.headRef == None:\n",
    "            self.headRef = node\n",
    "            node.next = node\n",
    "        elif self.headRef.next == self.headRef:\n",
    "            self.headRef.next = node\n",
    "            node.next = self.headRef\n",
    "        else:\n",
    "            predNode = None\n",
    "            curNode = self.headRef.next\n",
    "\n",
    "            while curNode != self.headRef:\n",
    "                predNode = curNode\n",
    "                curNode = curNode.next\n",
    "\n",
    "            node.next = curNode\n",
    "            predNode.next = node\n",
    "\n",
    "    def printCLL(self):\n",
    "        curNode = self.headRef.next\n",
    "        print('head ->',self.headRef.data, end=' ')\n",
    "\n",
    "        while curNode != self.headRef:\n",
    "            print(curNode.data, end=' ')\n",
    "            curNode = curNode.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "head -> 1 2 3 4 5 "
     ]
    }
   ],
   "source": [
    "cl1 = CLL()\n",
    "cl1.insert(1)\n",
    "cl1.insert(2)\n",
    "cl1.insert(3)\n",
    "cl1.insert(4)\n",
    "cl1.insert(5)\n",
    "\n",
    "cl1.printCLL()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Stack(list)\n",
    "* Last In First Out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = list()\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return len(self) == 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "    def peek(self):\n",
    "        assert not self.isEmpty(), 'Cannot peek in an empty stack'\n",
    "        return self.items[-1]\n",
    "    \n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "        \n",
    "    def pop(self):\n",
    "        assert not self.isEmpty(), 'Cannot pop, empty stack'\n",
    "        return self.items.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Top of the stack:  13\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s1 = Stack()\n",
    "s1.push(12)\n",
    "s1.push(10)\n",
    "s1.push(13)\n",
    "print(\"Top of the stack: \", s1.peek())\n",
    "s1.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stack(linked list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "class StackNode:\n",
    "    def __init__(self, item, link):\n",
    "        self.item = item\n",
    "        self.next = link\n",
    "        \n",
    "class StackLL:\n",
    "    def __init__(self):\n",
    "        self.top = None\n",
    "        self.size = 0\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        return self.top == None\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "    \n",
    "    def peek(self):\n",
    "        return self.top.item\n",
    "    \n",
    "    def push(self, item):\n",
    "        newNode = StackNode(item, self.top)\n",
    "        if self.top == None:\n",
    "            self.top = newNode\n",
    "        else:\n",
    "            self.top.next = newNode\n",
    "        self.size += 1\n",
    "        \n",
    "    def pop(self):\n",
    "        assert len(self) != 0, 'Cannot remove from an empty stack'\n",
    "        x = self.top\n",
    "        self.top = self.top.next\n",
    "        self.size -= 1\n",
    "        return x.item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Top of the stack:  12\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s2 = StackLL()\n",
    "s2.push(12)\n",
    "s2.push(10)\n",
    "s2.push(13)\n",
    "print(\"Top of the stack: \", s2.peek())\n",
    "s2.pop()\n",
    "s2.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Queue(list)\n",
    "* First In First Out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items = list()\n",
    "        \n",
    "    def __len__(self):\n",
    "        return len(self.items)\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return len(self) == 0\n",
    "    \n",
    "    def enqueue(self, item):\n",
    "        self.items.append(item)\n",
    "        \n",
    "    def dequeue(self):\n",
    "        assert not self.isEmpty(), 'Cannot dequeue from an empty queue'\n",
    "        return self.items.pop(0)\n",
    "    \n",
    "    def watch(self):\n",
    "        assert not self.isEmpty(), 'Cannot watch an empty queue'\n",
    "        return self.items[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Top of the queue:  11\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q1 = Queue()\n",
    "q1.enqueue(11)\n",
    "q1.enqueue(12)\n",
    "q1.enqueue(13)\n",
    "print(\"Top of the queue: \",q1.watch())\n",
    "q1.dequeue()\n",
    "q1.dequeue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Queue(linked list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class QueueNode:\n",
    "    def __init__(self, item):\n",
    "        self.item = item\n",
    "        self.next = None\n",
    "        \n",
    "class QueueLL:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.size = 0\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.head == None\n",
    "    \n",
    "    def enqueue(self, item):\n",
    "        node = QueueNode(item)\n",
    "        if self.head == None:\n",
    "            self.head = node\n",
    "        else:\n",
    "            self.tail.next = node\n",
    "        self.tail = node\n",
    "        self.size += 1\n",
    "        \n",
    "    def dequeue(self):\n",
    "        assert not self.isEmpty(), 'Cannot dequeue from an empty queue'\n",
    "        x = self.head.item\n",
    "        self.head = self.head.next\n",
    "        if self.isEmpty():  # if the head is the only element in queue\n",
    "            self.tail = None\n",
    "        self.size -= 1\n",
    "        return x\n",
    "    \n",
    "    def watch(self):\n",
    "        return self.head.item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Top of the queue:  12\n",
      "12\n",
      "Top of the queue:  10\n"
     ]
    }
   ],
   "source": [
    "q2 = QueueLL()\n",
    "q2.enqueue(12)\n",
    "q2.enqueue(10)\n",
    "q2.enqueue(13)\n",
    "print(\"Top of the queue: \",q2.watch())\n",
    "print(q2.dequeue())\n",
    "print(\"Top of the queue: \",q2.watch())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hash Map\n",
    "* Dictionaries in python\n",
    "* Dicts in python implement hash tables\n",
    "* Hasp Map has $O(1)$ for search, insertion and deletion operation.\n",
    "* It takes in a key and generates a hash using a hash function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HashMap:\n",
    "    def __init__(self, size):\n",
    "        self.Max = size\n",
    "        self.arr = [None for i in range(self.Max)]\n",
    "        \n",
    "    def getHash(self, key):\n",
    "        # hashing with ascii\n",
    "        h = 0\n",
    "        for char in key:\n",
    "            h+=ord(char)\n",
    "        return h % self.Max\n",
    "    \n",
    "    def __setitem__(self, key, value):\n",
    "        h = self.getHash(key)\n",
    "        print(h)\n",
    "        self.arr[h] = value\n",
    "        \n",
    "    def __getitem__(self, key):\n",
    "        h = self.getHash(key)\n",
    "        return self.arr[h]\n",
    "    \n",
    "    def __delitem(self, key):\n",
    "        h = self.getHash(key)\n",
    "        self.arr[h] = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "0\n",
      "1\n",
      "2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "67.8"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hmap = HashMap(3)\n",
    "hmap['march 10'] = 32.1\n",
    "hmap['march 11'] = 73.18\n",
    "hmap['march 12'] = 113.08\n",
    "hmap['march 13'] = 67.8 # march 10 value is overwritten but march 10 hash is still in memory pointing to new value\n",
    "hmap['march 14'] = 222.8 # march 11 value is --||--\n",
    "\n",
    "hmap['march 10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[113.08, 67.8, 222.8]"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hmap.arr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Set\n",
    "* The values in set are unique"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Set:\n",
    "    def __init__(self):\n",
    "        self.elements = list()\n",
    "        \n",
    "    def __len__(self):\n",
    "        return len(self.elements)\n",
    "    \n",
    "    def __contains__(self, ele):\n",
    "        return ele in self.elements\n",
    "    \n",
    "    def add(self, ele):\n",
    "        if ele not in self.elements:\n",
    "            self.elements.append(ele)\n",
    "    \n",
    "    def remove(self):\n",
    "        assert ele in self.elements, 'Element not present in Set'\n",
    "        self.elements.remove(ele)\n",
    "    \n",
    "    def isSubsetOf(self, B):\n",
    "        for element in self.elements:\n",
    "            if element not in B:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def union(self, B):\n",
    "        newSet = Set()\n",
    "        newSet.elements.extend(self.elements)\n",
    "        for ele in B:\n",
    "            newSet.add(ele)\n",
    "        return newSet\n",
    "    \n",
    "    def intersection(self, B):\n",
    "        newSet = Set()\n",
    "        for ele in self.elements:\n",
    "            if ele in B:\n",
    "                newSet.elements.append(ele)\n",
    "        return newSet\n",
    "    \n",
    "    def __eq__(self, B):\n",
    "        assert len(B) == len(self.elements), 'The sets are not equal'\n",
    "        self.elements.isSubsetOf(B)\n",
    "    \n",
    "    def difference(self, B):\n",
    "        newSet = Set()\n",
    "        for ele in self.elements:\n",
    "            if ele not in B:\n",
    "                newSet.elements.append(ele)\n",
    "        return newSet\n",
    "        \n",
    "    \n",
    "    def __iter__(self):\n",
    "        return SetIterator(self.elements)\n",
    "    \n",
    "class SetIterator:\n",
    "    def __init__(self, A):\n",
    "        self.curIndex = 0\n",
    "        self.elementSet = A\n",
    "    \n",
    "    def __iter__(self):\n",
    "        return self\n",
    "    \n",
    "    def __next__(self):\n",
    "        if self.curIndex < len(self.elementSet):\n",
    "            curElement = self.elementSet[self.curIndex]\n",
    "            self.curIndex += 1\n",
    "            return curElement\n",
    "        else:\n",
    "            raise StopIteration\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------------ Set 1 -------------\n",
      "12\n",
      "13\n",
      "14\n",
      "15\n",
      "------------ Set 2 -------------\n",
      "22\n",
      "13\n",
      "34\n",
      "15\n",
      "-------------- Union -------------\n",
      "12\n",
      "13\n",
      "14\n",
      "15\n",
      "22\n",
      "34\n",
      "-------------- Intersection -------------\n",
      "13\n",
      "15\n",
      "-------------- Difference -------------\n",
      "12\n",
      "14\n"
     ]
    }
   ],
   "source": [
    "s1 = Set()\n",
    "s1.add(12)\n",
    "s1.add(13)\n",
    "s1.add(14)\n",
    "s1.add(15)\n",
    "s1.add(12)\n",
    "\n",
    "s2 = Set()\n",
    "s2.add(22)\n",
    "s2.add(13)\n",
    "s2.add(34)\n",
    "s2.add(15)\n",
    "s2.add(22)\n",
    "su = s1.union(s2)\n",
    "si = s1.intersection(s2)\n",
    "sd = s1.difference(s2)\n",
    "\n",
    "print(\"------------ Set 1 -------------\")\n",
    "for i in s1:\n",
    "    print(i)\n",
    "\n",
    "print(\"------------ Set 2 -------------\")\n",
    "for i in s2:\n",
    "    print(i)\n",
    "\n",
    "print(\"-------------- Union -------------\")\n",
    "for i in su:\n",
    "    print(i)\n",
    "\n",
    "print(\"-------------- Intersection -------------\")\n",
    "for i in si:\n",
    "    print(i)\n",
    "\n",
    "print(\"-------------- Difference -------------\")\n",
    "for i in sd:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Priority Queue\n",
    "* Items with higher priority are dequeued first. However the items with same priority follow FIFO.\n",
    "* Two types:\n",
    "\n",
    "### Unbounded Priority Queue\n",
    "* No range on integer values that can used as priorities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UPQNode:\n",
    "    def __init__(self, item, priority):\n",
    "        self.item = item\n",
    "        self.priority = priority\n",
    "\n",
    "class UPQueue:\n",
    "    def __init__(self):\n",
    "        self.qlist = list()\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self.qlist)\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return len(self.qlist) == 0\n",
    "\n",
    "    def enqueue(self, item, priority):\n",
    "        node = UPQNode(item, priority)\n",
    "        self.qlist.append(node)\n",
    "\n",
    "    def dequeue(self):\n",
    "        assert not self.isEmpty(), \"Cannot dequeue from an empty priority queue\"\n",
    "\n",
    "        highest = 0\n",
    "        for i in range(len(self)):\n",
    "            if self.qlist[i].priority > self.qlist[highest].priority:\n",
    "                highest = i\n",
    "        x = self.qlist.pop(highest)\n",
    "        print(x.item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[<__main__.UPQNode object at 0x7f110ef117c0>, <__main__.UPQNode object at 0x7f110e79b9d0>, <__main__.UPQNode object at 0x7f110ef11c40>, <__main__.UPQNode object at 0x7f110ef11910>, <__main__.UPQNode object at 0x7f110ef11a00>, <__main__.UPQNode object at 0x7f110f0721c0>]\n",
      "6\n",
      "Purple\n",
      "Yellow\n",
      "Orange\n",
      "Black\n",
      "Green\n",
      "White\n"
     ]
    }
   ],
   "source": [
    "pq = UPQueue()\n",
    "pq.enqueue(\"Purple\",5)\n",
    "pq.enqueue(\"Black\",1)\n",
    "pq.enqueue(\"Orange\",3)\n",
    "pq.enqueue(\"White\",0)\n",
    "pq.enqueue(\"Green\",1)\n",
    "pq.enqueue(\"Yellow\",5)\n",
    "print(pq.qlist)\n",
    "print(len(pq))\n",
    "pq.dequeue()\n",
    "pq.dequeue()\n",
    "pq.dequeue()\n",
    "pq.dequeue()\n",
    "pq.dequeue()\n",
    "pq.dequeue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bounded Priority Queue\n",
    "* Priorities of bounded queue are restricted\n",
    "* Contains an array whose indices are priorities and elements are Queues that store values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BPQueue:\n",
    "    def __init__(self, p):\n",
    "        self.size = 0\n",
    "        self.bpqlist = Array(p)\n",
    "        \n",
    "        for i in range(p):\n",
    "            self.bpqlist[i] = Queue()\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.size == 0\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self) == 0\n",
    "    \n",
    "    def enqueue(self, value, priority):\n",
    "        assert priority >= 0 and priority < len(self.bpqlist), \"priority out of range\"\n",
    "        \n",
    "        self.bpqlist[priority].enqueue(value)\n",
    "        self.size += 1\n",
    "        \n",
    "    def dequeue(self):\n",
    "        i = 0\n",
    "        highp = len(self.bpqlist) - 1\n",
    "        \n",
    "        while self.bpqlist[highp].isEmpty() and i < highp:\n",
    "            highp -= 1\n",
    "        print(self.bpqlist[highp].dequeue())\n",
    "        self.size -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Purple\n",
      "Yellow\n",
      "Orange\n",
      "Black\n",
      "Green\n",
      "White\n"
     ]
    }
   ],
   "source": [
    "pq = BPQueue(6)\n",
    "pq.enqueue(\"Purple\",5)\n",
    "pq.enqueue(\"Black\",1)\n",
    "pq.enqueue(\"Orange\",3)\n",
    "pq.enqueue(\"White\",0)\n",
    "pq.enqueue(\"Green\",1)\n",
    "pq.enqueue(\"Yellow\",5)\n",
    "pq.dequeue()\n",
    "pq.dequeue()\n",
    "pq.dequeue()\n",
    "pq.dequeue()\n",
    "pq.dequeue()\n",
    "pq.dequeue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BTNode:\n",
    "    def __init__(self, val):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = val\n",
    "\n",
    "class BTree:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "    \n",
    "    def add(self, val):\n",
    "        if self.root is None:\n",
    "            self.root = BTNode(val)\n",
    "        else:\n",
    "            self._add(val, self.root)\n",
    "    \n",
    "    def _add(self, val, node):\n",
    "        if val < node.val:\n",
    "            if node.left is not None:\n",
    "                self._add(val, node.left)\n",
    "            else:\n",
    "                node.left = BTNode(val)\n",
    "        else:\n",
    "            if node.right is not None:\n",
    "                self._add(val, node.right)\n",
    "            else:\n",
    "                node.right = BTNode(val)\n",
    "                \n",
    "    def printTree(self):\n",
    "        if self.root is not None:\n",
    "            self._printTree(self.root)\n",
    "            \n",
    "    def _printTree(self, node):\n",
    "        if node is not None:\n",
    "            self._printTree(node.left)\n",
    "            print(str(node.val) + ' ')\n",
    "            self._printTree(node.right)\n",
    "            \n",
    "    def find(self, val):\n",
    "        if self.root is not None:\n",
    "            # exception handling because `_find` returns to `find` so we have to handle the return from `find`\n",
    "            try:\n",
    "                return self._find(self.root, val)\n",
    "            except AttributeError as e:\n",
    "                return False      \n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def _find(self, node, val):\n",
    "        if node.val == val:\n",
    "            return node\n",
    "        elif val < node.val:\n",
    "            self._find(node.left, val)\n",
    "        elif val > node.val:\n",
    "            self._find(node.right, val)\n",
    "            \n",
    "    def deleteTree(self):\n",
    "        self.root = None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 \n",
      "2 \n",
      "3 \n",
      "4 \n",
      "8 \n",
      "<__main__.BTNode object at 0x7fd32c418c70>\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "tree = BTree()\n",
    "tree.add(3)\n",
    "tree.add(4)\n",
    "tree.add(0)\n",
    "tree.add(8)\n",
    "tree.add(2)\n",
    "tree.printTree()\n",
    "print(tree.find(3))\n",
    "print(tree.find(10))\n",
    "tree.deleteTree()\n",
    "tree.printTree()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Search Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSTNode:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def getLeft(self):\n",
    "        return self.left\n",
    "\n",
    "    def getRight(self):\n",
    "        return self.right\n",
    "\n",
    "\n",
    "class BSTree:\n",
    "    def __init__(self, data):\n",
    "        self.root = BSTNode(data)\n",
    "\n",
    "    def getData(self):\n",
    "        return self.root.data\n",
    "\n",
    "    def insert(self, root, node):  # node arg here is node-data\n",
    "        if root is None:\n",
    "            root = node\n",
    "        else:\n",
    "            if root.data > node.data:\n",
    "                if root.left == None:\n",
    "                    root.left = node\n",
    "                else:\n",
    "                    self.insert(root.left, node)\n",
    "            else:\n",
    "                if root.right == None:\n",
    "                    root.right = node\n",
    "                else:\n",
    "                    self.insert(root.right, node)\n",
    "\n",
    "    def find(self, root, data):\n",
    "        curNode = root\n",
    "        while curNode is not None and curNode.data != data:\n",
    "            if data > curNode.data:\n",
    "                curNode = curNode.right\n",
    "        return curNode\n",
    "\n",
    "    def findMin(self, root):\n",
    "        curNode = root\n",
    "        if curNode.left is None:\n",
    "            return curNode.data\n",
    "        else:\n",
    "            return self.findMin(curNode.left)\n",
    "\n",
    "    def findMax(self, root):\n",
    "        curNode = root\n",
    "        if curNode.right is None:\n",
    "            return curNode.data\n",
    "        else:\n",
    "            return self.findMax(curNode.right)\n",
    "\n",
    "    def findMinNonRecursive(self, root):\n",
    "        curNode = root\n",
    "        while curNode.left is not None:\n",
    "            curNode = curNode.left\n",
    "        return curNode.data\n",
    "\n",
    "    def findMaxNonRecursive(self, root):\n",
    "        curNode = root\n",
    "        while curNode.right is not None:\n",
    "            curNode = curNode.right\n",
    "        return curNode.data\n",
    "   \n",
    "    def inOrder(self, root):\n",
    "        if root == None:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        print(root.data, sep=\"->\", end=\"->\")\n",
    "        self.inOrder(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n",
      "25\n",
      "9\n",
      "25\n"
     ]
    }
   ],
   "source": [
    "b = BSTree(20)\n",
    "b.insert(b.root, BSTNode(13))\n",
    "b.insert(b.root, BSTNode(22))\n",
    "b.insert(b.root, BSTNode(25))\n",
    "b.insert(b.root, BSTNode(21))\n",
    "b.insert(b.root, BSTNode(15))\n",
    "b.insert(b.root, BSTNode(9))\n",
    "print(b.findMin(b.root))\n",
    "print(b.findMax(b.root))\n",
    "print(b.findMinNonRecursive(b.root))\n",
    "print(b.findMaxNonRecursive(b.root))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Heaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `2. Algorithms`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Searching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linear Search\n",
    "* Searching for element with a single pass through.\n",
    "* Time complexity: $O(n)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unorderedSearch(arr ,target):\n",
    "    for i in range(len(arr)):\n",
    "        if arr[i] == target:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "# For sorted array\n",
    "def orderedSearch(arr, target):\n",
    "    for i in range(len(arr)):\n",
    "        if arr[i] == target:\n",
    "            return True\n",
    "        elif arr[i] > target:\n",
    "            return False\n",
    "    return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [2, 16, 37, 89]\n",
    "unorderedSearch(lst, 37)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Search\n",
    "* Dividing the problem into half each time\n",
    "* Time complexity: $O(log n)$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binarySearch(arr ,target):\n",
    "    low = 0\n",
    "    high = len(arr) - 1\n",
    "    \n",
    "    while low <= high:\n",
    "        mid = (low + high) // 2\n",
    "        if arr[mid] == target:\n",
    "            return True\n",
    "        elif arr[mid] > target:\n",
    "            high = mid - 1\n",
    "        else:\n",
    "            low = mid + 1\n",
    "            \n",
    "    return False\n",
    "\n",
    "def binarySearchRecursive(arr, target):\n",
    "    low = 0\n",
    "    high = len(arr) - 1\n",
    "    \n",
    "    while low <= high:\n",
    "        mid = (low + high) // 2\n",
    "        if arr[mid] == target:\n",
    "            return True\n",
    "        elif target < arr[mid]:\n",
    "            return binarySearchRecursive(arr[:mid], target)\n",
    "        else:\n",
    "            return binarySearchRecursive(arr[mid+1:], target)\n",
    "        \n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [2, 16, 37, 89]\n",
    "binarySearch(lst, 37)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Interpolation Search\n",
    "* Elements need to be uniformly distributed if the value of the key is closer to the last element, interpolation search is likely to start search towards the end side.\n",
    "* The idea of formula is to return higher value of pos \n",
    "* when element to be searched is closer to arr[hi]. And\n",
    "* smaller value when closer to arr[lo]\n",
    "* Probe position formula: $pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]$\n",
    "* Complexity => $O(log(log n))$, Worst case => $O(n)$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def interpolationSearch(arr ,target):\n",
    "    low = 0\n",
    "    high = len(arr) - 1\n",
    "    \n",
    "    while arr[low] <= target and arr[high] >= target:\n",
    "        mid = int(low +((target - arr[low]) * (high - low))/(arr[high]-arr[low]))\n",
    "        if arr[mid] == target:\n",
    "            return True\n",
    "        elif arr[mid] < target:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            high = mid - 1\n",
    "\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "interpolationSearch([3,4,5,6], 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Jump Search\n",
    "* Jumping a range of elements\n",
    "* If target lies in first and last element of range perform linear search on that range.\n",
    "* Complexity => $O((n/m)+(m-1))$ == $O(sqrt(n))$ , n=no of elements, m=no of steps\n",
    "* LinearSearch > JumpSearch > BinarySearch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def jumpSearch(arr, target):\n",
    "    step_size = math.sqrt(len(arr))\n",
    "    prev = 0\n",
    "    while arr[int(min(step_size, len(arr)) - 1)] < target: # generating the end bound as step_size or len(arr)(in case of last element)\n",
    "# above step checks for final jump end bound. If the jump size goes beyond array,\n",
    "# the bound of the array is replaced as arr[prev: len(arr)]\n",
    "        prev = step_size\n",
    "        step_size += math.sqrt(len(arr))\n",
    "        if prev >= len(arr):\n",
    "            return False\n",
    "    while arr[int(prev)] < target:\n",
    "        prev += 1\n",
    "        if prev == min(step_size, n):\n",
    "            return False\n",
    "\n",
    "    if arr[int(prev)] == target:\n",
    "         return True\n",
    "\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "print(jumpSearch([2,3,4,5,6,7,8,9,10,11,12,13], 12))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fibonacci Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exponential Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bubble Sort\n",
    "* Time complexity: $O(n^2)$\n",
    "* Space complexity: $O(1)$ (in place sorting)\n",
    "* Bubbles out the greater element to the end by comparing adjacent elements (with j)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(arr):\n",
    "    for i in range(len(arr)):\n",
    "        for j in range(i+1, len(arr)):\n",
    "            if arr[i] > arr[j]:\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 41, 51]\n"
     ]
    }
   ],
   "source": [
    "print(bubble_sort([3,41,51,2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Selection Sort\n",
    "* Time complexity: $O(n^2)$\n",
    "* Space complexity: $O(1)$ (in place sorting)\n",
    "* Select one element and compare rest of the array to it.\n",
    "* Put the smaller element at the beginning of array. Then pick the next smallest element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(arr):\n",
    "    for i in range(len(arr)):\n",
    "        min_ndx = i\n",
    "        for j in range(i+1, len(arr)):\n",
    "            if arr[min_ndx] > arr[j]:\n",
    "                min_ndx = j\n",
    "        arr[i], arr[min_ndx] = arr[min_ndx], arr[i]\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted array:  [2, 3, 7, 41, 51]\n"
     ]
    }
   ],
   "source": [
    "print('Sorted array: ',selection_sort([3, 41, 51, 7, 2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Insertion Sort\n",
    "* Time complexity: $O(n^2)$\n",
    "* Space complexity: $O(1)$\n",
    "* Sorting the cards in hands.\n",
    "* Suppose we have two sub arrays sorted and unsorted. Initially sorted will be empty.\n",
    "* We will be manipulating the same array and considering only unsorted section to be sorted.\n",
    "* At each ith step we will be adding one element to sorted section\n",
    "* Better than Bubble and Selection sort because no. of comparisons are better."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(arr):\n",
    "    for i in range(1,len(arr)):\n",
    "        picked = arr[i] # pick one element to be sorted.\n",
    "        j = i - 1 # reverse traversing and comaring the sorted subarr\n",
    "        while j >= 0 and picked < arr[j]: # j condition is to handle first element\n",
    "            arr[j+1] = arr[j]\n",
    "            j -= 1\n",
    "        arr[j+1] = picked\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted array:  [2, 3, 32, 41, 52, 62]\n"
     ]
    }
   ],
   "source": [
    "print('Sorted array: ', insertion_sort([41, 2, 3, 52, 32, 62]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Merge Sort\n",
    "* Time complexity: $O(nlogn)$\n",
    "* Space complexity: $O(n)$ (requires extra array to store copies)\n",
    "* Follows divide and conquer strategy.\n",
    "* Steps:\n",
    "    1. Break down every list similar to binary search.(L, R)\n",
    "    2. Merge the smaller components by arranging them in sorted fashion.\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeSort(arr):\n",
    "    if len(arr) < 2:\n",
    "        return \n",
    "    \n",
    "    mid = len(arr) // 2\n",
    "    L = arr[:mid]\n",
    "    R = arr[mid:]\n",
    "    \n",
    "    mergeSort(L)\n",
    "    mergeSort(R)\n",
    "    return mergeFunc(L, R, arr)\n",
    "    \n",
    "def mergeFunc(L, R, arr):\n",
    "    i = j = k = 0\n",
    "    \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",
    "    \"\"\"Only one of the 2 while loops will run. These are to cover any left elementsin L or R.\"\"\"\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",
    "    \n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted array:  [3, 4, 7, 10, 19, 41, 52]\n"
     ]
    }
   ],
   "source": [
    "print('Sorted array: ', mergesort([3,41,52,7,4,10,19]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quick Sort\n",
    "* Time complexity: average - $O(nlogn)$ worst - $O(n^2)$\n",
    "* Space complexity: $O(1)$\n",
    "* Divide and conquer strategy\n",
    "* Despite having a $O(n^2)$ in worst case, QS is very useful in practical scenarios and the worst case can be avoided with high probability by using randomized version of quick sort.\n",
    "* The choice of the pivot actually determines the performance of quicksort.\n",
    "* Most programming language libraries use some implementation of quicksort."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quicksort(arr, start, end):\n",
    "    if start < end: # exit when start >= end\n",
    "        pi = partition(arr, start, end)\n",
    "        quicksort(arr, start, pi - 1)\n",
    "        quicksort(arr, pi + 1, end)\n",
    "\n",
    "def partition(arr, start, end):\n",
    "    pivot = arr[end]\n",
    "    pindex = start # keeping track of the pos where the pivot should be \n",
    "    for i in range(start,end):\n",
    "        if arr[i] <= pivot:\n",
    "            arr[i], arr[pindex] = arr[pindex], arr[i]\n",
    "            pindex += 1\n",
    "    arr[pindex], arr[end] = arr[end], arr[pindex]\n",
    "    return pindex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted array:  [2, 3, 11, 23, 26, 41, 51, 71]\n"
     ]
    }
   ],
   "source": [
    "arrr = [3,51,2,41,71,23,26,11]\n",
    "quicksort(arrr, 0, 7)\n",
    "print('Sorted array: ', arrr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Counting Sort\n",
    "* One of the fastest sorting algorithms.\n",
    "* Drawback: Only works for non-negative whole numbers.\n",
    "* Time complexity: $O(n+k)$, n=no. of elements to be sorted, k=no. of possible values.\n",
    "* Steps:\n",
    " 1. count array stores the total number of occurences of a certain element.\n",
    " 2. cumulative count arr decides where the position of the element will be in sorted array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countingsort(arr, k):\n",
    "    k += 1\n",
    "    B = [0] * len(arr)\n",
    "    C = [0] * k\n",
    "\n",
    "    for i in range(len(arr)):\n",
    "        C[arr[i]] += 1\n",
    "    for i in range(1,k):\n",
    "        C[i] = C[i] + C[i-1]\n",
    "    for i in arr:\n",
    "        temp = C[i]\n",
    "        C[i] -= 1\n",
    "        B[temp - 1] = i\n",
    "    return B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 6, 7, 8]\n",
      "[1, 1, 2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "print(countingsort([8,3,2,6,7],8))\n",
    "print(countingsort([2,1,4,1,3],4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Heap Sort\n",
    "* Time complexity: $O(nlogn)$\n",
    "* Space complexity: $O(1)$\n",
    "\n",
    "#### Array Representation of Binary Tree:\n",
    "* If Node is at index -> i\n",
    "* It's left child is at index -> 2*i\n",
    "* It's right child is at index -> 2*i+1\n",
    "* It's parent is at -> i/2\n",
    "\n",
    "#### Terminologies.\n",
    "* Full Binary Tree -> Binary tree with maximum number of nodes is a full binary.\n",
    "* Complete Binary Tree -> When a binary tree is represented as an array and there are no missing elements in between then it is a complete binary tree. In layman terms, A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. \n",
    "* A Heap is a complete binary tree.\n",
    "* There are two types of heaps:\n",
    "\n",
    "#### Min-heap:\n",
    "Every node is having elements smaller than or equal to it's all it's descendents\n",
    "\n",
    "#### Max-heap:\n",
    "Every node is having elements greater than or equal to all it's descendents.\n",
    "\n",
    "* Insertion in a heap depends on it's height which $log(n)$. So insertion time complexity is $O(log n))$\n",
    "* The time for sorting complexity is same as the time taken to insertion, since we're only doing heapify.\n",
    "\n",
    "Procedure of Heap sort:\n",
    "  1. given an array first create a heap (max or min).\n",
    "  2. then delete all the elements in an heap."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heapify(arr, n, i): #builds a max heap\n",
    "    largest = i\n",
    "    l = 2*i+1\n",
    "    r = 2*i+2\n",
    "    if l < n and arr[largest] < arr[l]:\n",
    "        largest = l\n",
    "\n",
    "    if r < n and arr[largest] < arr[r]:\n",
    "        largest = r\n",
    "\n",
    "    if largest != i:\n",
    "        arr[i], arr[largest] = arr[largest], arr[i]\n",
    "\n",
    "def heapsort(arr):\n",
    "    n = len(arr)\n",
    "\n",
    "    for i in range(n//2 -1, -1, -1): # only get the nodes that have child nodes\n",
    "        print(\"i\",i)\n",
    "        heapify(arr, n, i)\n",
    "\n",
    "    for i in range(n-1, 0, -1):\n",
    "        arr[i], arr[0] = arr[0], arr[i]\n",
    "        heapify(arr, i, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i 2\n",
      "i 1\n",
      "i 0\n",
      "[3, 6, 7, 8, 10, 11, 13]\n"
     ]
    }
   ],
   "source": [
    "arr = [10,8,7,3,11,13,6]\n",
    "heapsort(arr)\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tree Sort\n",
    "* Tree sort takes the element of an array and creates a binary search tree with it.\n",
    "* Then it performs inOrder traversal.\n",
    "* Average Case Time Complexity : $O(n log n)$\n",
    "* Worst Case Time Complexity : $O(n2)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def treesort(arr):\n",
    "    bst = BSTree(arr[0])\n",
    "    for i in range(1,len(arr)):\n",
    "        bst.insert(bst.root, BSTNode(arr[i]))\n",
    "    bst.inOrder(bst.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Inorder on BST gives sorted sequence of [12, 4, 5, 3, 24, 31] :\n",
      "3->4->5->12->24->31->"
     ]
    }
   ],
   "source": [
    "arr = [12,4,5,3,24,31]\n",
    "print(f'Inorder on BST gives sorted sequence of {arr} :') \n",
    "treesort(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph\n",
    "* The selection of graph based search algorithm mainly depends on the type of graph/tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Breadth First Search\n",
    "* We start at starting node and traverse it's neighbours\n",
    "* Use when shortest path is needed.\n",
    "* Complexity: $O(V + E)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.graph = defaultdict(list)\n",
    "        self.visited = set()\n",
    "    \n",
    "    def addEdge(self, u, v):\n",
    "        self.graph[u].append(v)\n",
    "        \n",
    "    def BFS(self, start):\n",
    "        queue = [start]\n",
    "        print(start, ' -> ', end=' ')\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            \n",
    "            for n in self.graph[node]:\n",
    "                if n not in self.visited:\n",
    "                    print(n, ' -> ', end=' ')\n",
    "                    queue.append(n)\n",
    "                    self.visited.add(n)\n",
    "                    \n",
    "    def BFSPaths(self, start, end): # find a path using bfs\n",
    "        pass\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Traversal:  1  ->  2  ->  3  ->  4  ->  5  ->  6  ->  "
     ]
    }
   ],
   "source": [
    "g = Graph()\n",
    "g.addEdge(1, 2)\n",
    "g.addEdge(1, 3)\n",
    "g.addEdge(2, 4)\n",
    "g.addEdge(2, 5)\n",
    "g.addEdge(3, 5)\n",
    "g.addEdge(4, 6)\n",
    "g.addEdge(5, 6)\n",
    "\n",
    "print(\"Traversal: \", end=\" \")\n",
    "g.BFS(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Depth First Search\n",
    "* Recursive\n",
    "* Traverses the connected vertices one after other\n",
    "* Use when we want to exhaust all possibilities, and check which one is the best/count the number of all possible ways.\n",
    "* Complexity: $O(V + E)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.graph = defaultdict(list)\n",
    "        self.visited = set()\n",
    "    \n",
    "    def addEdge(self, u, v):\n",
    "        self.graph[u].append(v)\n",
    "        \n",
    "    def DFS(self, start):\n",
    "        self.visited.add(start)\n",
    "        print(start, ' -> ', end=' ')\n",
    "        \n",
    "        for n in self.graph[start]:\n",
    "            if n not in self.visited:\n",
    "                self.DFS(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Traversal:  1  ->  2  ->  4  ->  6  ->  5  ->  3  ->  "
     ]
    }
   ],
   "source": [
    "g = Graph()\n",
    "g.addEdge(1, 2)\n",
    "g.addEdge(1, 3)\n",
    "g.addEdge(2, 4)\n",
    "g.addEdge(2, 5)\n",
    "g.addEdge(3, 5)\n",
    "g.addEdge(4, 6)\n",
    "g.addEdge(5, 6)\n",
    "\n",
    "print(\"Traversal: \", end=\" \")\n",
    "g.DFS(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dijkstras"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Topological Sort\n",
    "* For Directed Acyclic Graph\n",
    "* There can be more than one topological sorting for a graph.\n",
    "* First vertex in TopSort is always the one with in-degree of 0, i.e. 0 incoming edges.\n",
    "* In topological sorting, we need to print a <b>vertex before its adjacent vertices</b>, all vertices follow this rule. \n",
    "* Topological is not unique\n",
    "* Complexity => $O(V+E)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "class Graph:\n",
    "    def __init__(self, vertices):\n",
    "        self.grid = defaultdict(list)\n",
    "        self.vertices = vertices\n",
    "        self.visited = set()\n",
    "\n",
    "    def addEdge(self, u, v):\n",
    "        self.grid[u].append(v)\n",
    "\n",
    "    def TopologicalSortUtil(self, node, stack):\n",
    "        self.visited.add(node)\n",
    "\n",
    "        for edge in self.grid[node]:\n",
    "            if edge not in self.visited:\n",
    "                self.TopologicalSortUtil(edge, stack)\n",
    "        stack.insert(0,node)\n",
    "\n",
    "    def TopSort(self):\n",
    "        stack = []\n",
    "        for i in range(self.vertices):\n",
    "            if i not in self.visited:\n",
    "                self.TopologicalSortUtil(i, stack)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 4, 2, 3, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "d = Graph(6)\n",
    "d.addEdge(5,0)\n",
    "d.addEdge(5,2)\n",
    "d.addEdge(2,3)\n",
    "d.addEdge(3,1)\n",
    "d.addEdge(4,0)\n",
    "d.addEdge(4,1)\n",
    "print(d.TopSort())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bellman-Ford"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Kruskal-Wallis minimum spanning tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prim's minimum spanning tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 Tree"
   ]
  },
  {
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}