Review.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 1: Arrays and Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary:\n",
    "* ask if the character set is either ASCII or Unicode\n",
    "* see if you can do upfront work by maniuplating the string first, then go on with the rest of the algorithm\n",
    "* see if you can use a hash table to keep count of number of chars or if you know it is ASCII, initialize an array with 128 elements in length, then get the character code and do array[charCode] = true or false\n",
    "    - remember that arrays are also as fast as hash tables for lookup if you know the index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 2: Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked Lists(LL):\n",
    "* a data structure that stores items in a linear fashion where each element has a pointer that points to the next element in the list\n",
    "    - this pointer (usually called next) can either point to the next node in the list or null\n",
    "* singly LL: contains only 1 pointer that points to the next item in the list\n",
    "* doubly LL: contains 2 pointers that points to the previous and next items in the list\n",
    "\n",
    "### Why Use a Linked List? \n",
    "* linked lists were used to save on memory back when computers had limited space. this is because they only allocate what's needed for the elements. in some languages like C, we tell the computer how much space to reserve for an array. if it doesn't need all of the space it reserved, the space is still not usable by other programs\n",
    "* linked lists were also used when people didn't know how many elements were going to be in a list. instead of guessing how much space to allocate, linked lists could add or delete elements at will without all the guesswork\n",
    "* nowadays, we have dynamically sized arrays so the use of linked lists isn't as prevalent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation of a Singly Linked List:\n",
    "* each node only has a \"next\" pointer pointing to the next node in the list\n",
    "* operations: \n",
    "    -insertion: O(1) at the head and O(n) at the tail\n",
    "    - deletions: O(1) at the head and O(n) at the tail\n",
    "    - searching: worst case O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "// a linked list node that will be inserted into an LL\n",
    "class LinkedListNode {\n",
    "    constructor(data) {\n",
    "        this.data = data;\n",
    "        this.next = null;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "const head = Symbol(\"head\");\n",
    "const size = Symbol(\"size\");\n",
    "\n",
    "class LinkedList {\n",
    "    constructor() {\n",
    "        this[head] = null;\n",
    "        this[size] = 0;\n",
    "    }\n",
    "    \n",
    "    // sets current node as the head\n",
    "    // and traverses through the list using a while loop\n",
    "    // and accessing the next node until it is null\n",
    "    // if the node is valid, return it \n",
    "    get(index) {\n",
    "        if(index > -1) {\n",
    "            let current = this[head];\n",
    "            let i = 0;\n",
    "            \n",
    "            while(current !== null && (i < index)) {\n",
    "                current = current.next;\n",
    "                i++;\n",
    "            }\n",
    "            \n",
    "            return current !== null ? current : undefined;\n",
    "        }\n",
    "        else {\n",
    "            return undefined;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // same principle as get but this time, if there is no this[head],\n",
    "    // then we make it the current head\n",
    "    // if there is a current head, we traverse the list until we reached the end\n",
    "    // where there is no more nodes left and add a node there\n",
    "    push(data) {\n",
    "        const newNode = new LinkedListNode(data);\n",
    "        \n",
    "        if(this[head] === null) {\n",
    "            this[head] = newNode;\n",
    "        }\n",
    "        else {\n",
    "            let current = this[head];\n",
    "            while(current.next !== null) {\n",
    "                current = current.next;\n",
    "            }\n",
    "            \n",
    "            current.next = newNode;\n",
    "        }\n",
    "        this[size]++;\n",
    "    }\n",
    "    \n",
    "    // adds to the head of the linked list\n",
    "    // all we do is check if there is a head\n",
    "    // if there is, then we set the newnode's next pointer to \n",
    "    // point to \n",
    "    unshift(data) {\n",
    "        const newNode = new LinkedListNode(data);\n",
    "        \n",
    "        if(this[head] === null) {\n",
    "            this[head] = newNode;\n",
    "        }\n",
    "        else {\n",
    "            newNode.next = this[head];\n",
    "            this[head] = newNode;\n",
    "        }\n",
    "        this[size]++;\n",
    "    }\n",
    "    \n",
    "    // removes an ll node at a certain index\n",
    "    remove(index) {\n",
    "        if(this[head] === null || index < 0) {\n",
    "            throw new RangeError(`Index ${index} does not exist in the list.`);\n",
    "        }\n",
    "        \n",
    "        // if index is 0, return the head and set the next node to be the new head\n",
    "        if(index === 0) {\n",
    "            const data = this[head].data;\n",
    "            this[head] = this[head].next;\n",
    "            this[size]--;\n",
    "            return data;\n",
    "        }\n",
    "        \n",
    "        let current = this[head];\n",
    "        let previous = null; // pointer to the node before current\n",
    "        let i = 0;\n",
    "        \n",
    "        while( (current !== null) && (i < index)) {\n",
    "            previous = current;\n",
    "            current = current.next;\n",
    "            i++;\n",
    "        }\n",
    "        \n",
    "        if(current !== null) {\n",
    "            previous.next = current.next;\n",
    "            this[size]--;\n",
    "            return current.data;\n",
    "        }\n",
    "        \n",
    "        // if node wasn't found, then throw an error\n",
    "        throw new RangeError(`Index ${index} does not exist in the list`);\n",
    "    }\n",
    "    \n",
    "    // the asterisk before a function indicates that this is a generator function\n",
    "    // just traverses the list and yields the data of each element\n",
    "    *values() {\n",
    "        let current = this[head];\n",
    "        while(current !== null) {\n",
    "            yield current.data;\n",
    "            current = current.next;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "    \n",
    "    isEmpty() {\n",
    "        return this[size] === 0;\n",
    "        // or can do this[head] === null\n",
    "    }\n",
    "    \n",
    "    // the get keyword will allow us to do something like:\n",
    "    // list.size instead of list.size()\n",
    "    //with the size property, this makes it O(1)\n",
    "    // if we didn't have it, we would have to traverse and count\n",
    "    // the number of elements which would be O(n)\n",
    "    get size() {\n",
    "        return this[size];\n",
    "    }\n",
    "    \n",
    "    indexOf(data) {\n",
    "        let current = this[head];\n",
    "        let index = 0;\n",
    "        while(current !== null) {\n",
    "            if(current.data === data) {\n",
    "                return index;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    clear() {\n",
    "        this[head] = null;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "red\n",
      "orange\n",
      "yellow\n"
     ]
    }
   ],
   "source": [
    "var list = new LinkedList();\n",
    "list.push('red');\n",
    "list.push('orange');\n",
    "list.push('yellow');\n",
    "\n",
    "for(var color of list) {\n",
    "    console.log(color)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation of Doubly Linked List\n",
    "* each node has a pointer to the next node in the list and the previous node in the list\n",
    "* operations:\n",
    "    - insertion: insertion is O(1) at the head or the tail\n",
    "    - deletion: O(1) at the head/tail but O(n) anywhere else\n",
    "    - search: still O(n)\n",
    "* not much of an advantage over a SLL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DoublyLinkedListNode extends LinkedListNode{\n",
    "    constructor(data) {\n",
    "        super(data);\n",
    "        this.previous = null;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DoublyLinkedList {\n",
    "    constructor() {\n",
    "        this[head] = null;\n",
    "        this[tail] = null;\n",
    "    }\n",
    "    \n",
    "    // exactly the same as singly LL\n",
    "    get(index) {\n",
    "        if(index > -1) {\n",
    "            let i = 0;\n",
    "            while(current !== null && i < index) {\n",
    "                current = current.next;\n",
    "                i++;\n",
    "            }\n",
    "            \n",
    "            return current !== null ? current.data : undefined;\n",
    "        }\n",
    "        else {\n",
    "            return undefined;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // adds data to tail of DLL\n",
    "    push(data) {\n",
    "        const newNode = new DoublyLinkedListNode(data);\n",
    "        \n",
    "        // if list is empty, then just make newnode as head\n",
    "        if(this[head] === null) {\n",
    "            this[head] = newNode;\n",
    "        }\n",
    "        // else just access tail pointer and set next to newnode\n",
    "        // then set newnode's previous to tail\n",
    "        // this sets up a connection between them\n",
    "        else {\n",
    "            this[tail].next = newNode;\n",
    "            newNode.previous = this[tail];\n",
    "        }\n",
    "        // then you set the tail as the newnode\n",
    "        // for an empty list, it is the tail and the head\n",
    "        this[tail] = newNode;\n",
    "    }\n",
    "    \n",
    "    unshift(data) {\n",
    "        const newNode = new DoublyLinkedListNode(data);\n",
    "        if(this[head] === null) {\n",
    "            this[head] = newNde;\n",
    "            this[tail] = newNode;\n",
    "        }\n",
    "        else {\n",
    "            newNode.next = this[head];\n",
    "            this[head] = newNode;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    remove(index) {\n",
    "        if( this[head] === null || index < 0 ) {\n",
    "            throw new RangeError(`Index ${index} does not exist in the list.`)\n",
    "        }\n",
    "        \n",
    "        if(index === 0) {\n",
    "            const data = this[head].data;\n",
    "            \n",
    "            this[head] = this[head].next;\n",
    "            \n",
    "            // if we removed the only item in the list,\n",
    "            // then the head and tail should be null\n",
    "            if(this[head] === null) {\n",
    "                this[tail] === null;\n",
    "            }\n",
    "            else {\n",
    "                this[head].previous = null;\n",
    "            }\n",
    "            return data;\n",
    "        }\n",
    "        \n",
    "        let current = this[head];\n",
    "        let i = 0;\n",
    "        \n",
    "        while(current !== null && i < index) {\n",
    "            current = current.next;\n",
    "            i++;\n",
    "        }\n",
    "        \n",
    "        if(current !== null) {\n",
    "            current.previous.next = current.next;\n",
    "            \n",
    "            if(this[tail] === current) {\n",
    "                this[tail] = current.previous;\n",
    "            }\n",
    "            else {\n",
    "                current.next.previous = current.previous;\n",
    "            }\n",
    "            return current.data;\n",
    "        }\n",
    "        \n",
    "        throw new RangeError(`Index ${index} does not exist in the list`);\n",
    "    }\n",
    "    \n",
    "    // prints the list in reverse\n",
    "    *reverse() {\n",
    "        let current = this[tail];\n",
    "        while(current !== null) {\n",
    "            yield current.data;\n",
    "            current = current.previous;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        let current = this[head];\n",
    "        while(current !== null) {\n",
    "            yield current.data\n",
    "            current = current.next;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CircularDoublyLinkedList {\n",
    "    constructor() {\n",
    "        this[head] = null;\n",
    "    }\n",
    "    \n",
    "    get(index) {\n",
    "        if(index > -1 && this[head] !== null) {\n",
    "            let current = this[head];\n",
    "            let i = 0;\n",
    "            \n",
    "            // do while loop b/c it would immediately terminate since\n",
    "            // the condition current !== this[head] would be false\n",
    "            // since the first item IS the head\n",
    "            // we do a do while to make sure it checks the head, then\n",
    "            // proceeds with the rest of the loop\n",
    "            // once it makes a full pass back to the head, then it'll\n",
    "            // terminate if it doesn't find anything\n",
    "            do {\n",
    "                if(i === index) {\n",
    "                    return current.data;\n",
    "                }\n",
    "                current = current.next;\n",
    "                i++;\n",
    "            }while (current !== this[head] && i <= index);\n",
    "        }\n",
    "        return undefined;\n",
    "    }\n",
    "    \n",
    "    add(data) {\n",
    "        const newNode = new CircularDoublyLinkedList(data);\n",
    "        \n",
    "        // no items in the list yet\n",
    "        // newNode is the head and the tail and will point to itself\n",
    "        \n",
    "        if(this[head] === null) {\n",
    "            this[head] = newNode;\n",
    "            newNode.next = newNode;\n",
    "            newNode.previous = newNode;\n",
    "        }\n",
    "        // adds the item towards the tail end of the LL\n",
    "        else {\n",
    "            const tail = this[head].previous\n",
    "            \n",
    "            tail.next = newNode;\n",
    "            newNode.previous = tail;\n",
    "            newNode.next = this[head];\n",
    "            this[head].previous = newNode;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    remove(index) {\n",
    "        if(this[head] === null || index < 0) {\n",
    "            throw new RangeError(`Index ${index} does not exist in the list.`);\n",
    "        }\n",
    "        \n",
    "        let current = this[head];\n",
    "        \n",
    "        if(index === 0) {\n",
    "            // if there is only 1 node in the list\n",
    "            if(current.next === this[head]) {\n",
    "                this[head] = null;\n",
    "            }\n",
    "            else {\n",
    "                const tail = this[head].previous;\n",
    "                tail.next = current.next;\n",
    "                current.next.previous = tail;\n",
    "                this[head] = tail.next;\n",
    "            }\n",
    "            return current.data;\n",
    "        }\n",
    "        \n",
    "        let i = 0;\n",
    "        \n",
    "        do {\n",
    "            current = current.next;\n",
    "            i++;\n",
    "        } while (current !== this[head] && i < index);\n",
    "        \n",
    "        if(current !== this[head]) {\n",
    "            current.previous.next = current.next;\n",
    "            current.next.previous = current.previous;\n",
    "            return current.data;\n",
    "        }\n",
    "        \n",
    "        throw new RangeError(`Index ${index} does not exist in the list.`);\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        if(this[head] !== null) {\n",
    "            //only 1 item in the list\n",
    "            if(this[head].next === this[head]) {\n",
    "                yield this[head].data;\n",
    "            }\n",
    "        }\n",
    "        else {\n",
    "            let current = this[head];\n",
    "            do {\n",
    "                yield current.data;\n",
    "                current = current.next\n",
    "            }while(current !== this[head]);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursive Algorithms with Linked Lists\n",
    "* recursive definition: a linked list is either:\n",
    "    - null\n",
    "    - or a node pointing to a linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "function recAlgorithm(node) {\n",
    "    if(node === null) {\n",
    "        /*\n",
    "        base case\n",
    "        do something simple here\n",
    "        */\n",
    "    }\n",
    "    else {\n",
    "        // recursive case\n",
    "        // do something at head of list, then call method on the rest of the list\n",
    "        recAlgorithm(node.next)\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recursive Methods\n",
    "* O(n) time complexity b/c they traverse the list recursively\n",
    "* O(n) space complexity b/c of the use of a stack in recursion so there are O(n) function calls on the stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node {\n",
    "    constructor(data, next = null) {\n",
    "        this.data = data;\n",
    "        this.next = next;\n",
    "    }\n",
    "}\n",
    "\n",
    "class SLL {\n",
    "    constructor() {\n",
    "        this[head] = null;\n",
    "    }\n",
    "    \n",
    "    get(index) {\n",
    "        let current = this[head];\n",
    "        if(index > - 1) {\n",
    "            let i = 0;\n",
    "            while(current !== null && i < index) {\n",
    "                current = current.next;\n",
    "                i++;\n",
    "            }\n",
    "            return current !== null ? current : undefined;\n",
    "        }\n",
    "        else {\n",
    "            return undefined;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    add(data) {\n",
    "        const newNode = new Node(data);\n",
    "        if(this[head] === null) {\n",
    "            this[head] = newNode;\n",
    "        }\n",
    "        else {\n",
    "            newNode.next = this[head];\n",
    "            this[head] = newNode;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        let current = this[head];\n",
    "        while(current !== null) {\n",
    "            yield current.data;\n",
    "            current = current.next;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "    \n",
    "    \n",
    "    \n",
    "    // recursive methods\n",
    "    \n",
    "    get length() {\n",
    "        return this.findLength(this[head]);\n",
    "    }\n",
    "    \n",
    "    findLength(node) {\n",
    "        if(node === null) {\n",
    "            return 0;\n",
    "        }\n",
    "        else {\n",
    "            return 1 + this.findLength(node.next);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    member(key) {\n",
    "        return this.findMember(this[head], key);\n",
    "    }\n",
    "    \n",
    "    findMember(node, key) {\n",
    "        // if reached end of list, then return -1\n",
    "        if(node === null) {\n",
    "            return -1;\n",
    "        }\n",
    "        // if we found it, return true;\n",
    "        else if (node.data === key) {\n",
    "            return true;\n",
    "        }\n",
    "        // calls on the \n",
    "        else {\n",
    "            return this.findMember(node.next, key);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    printList(order) {\n",
    "        if(order === 'regular') {\n",
    "            this.printHelper(this[head]);\n",
    "        }\n",
    "        else if (order === 'reverse') {\n",
    "            this.printHelperReverse(this[head]);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // difference between regular and reverse is the order of the console.log()\n",
    "    // print before calling is regular order b/c it will print,\n",
    "    // put function on stack, and call it again\n",
    "    \n",
    "    printHelper(node) {\n",
    "        if(node !== null) {\n",
    "            console.log(node.data);\n",
    "            this.printHelper(node.next);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // this will print in reverse because once the recursion reaches\n",
    "    // the end of the list, then we can print the values\n",
    "    // last in, first out with recursion (implicit stack)\n",
    "    // so the last node to get reached will be the first to be printed\n",
    "    \n",
    "    printHelperReverse(node) {\n",
    "        if(node !== null) {\n",
    "            this.printHelperReverse(node.next);\n",
    "            console.log(node.data);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recursive List Reconstruction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "// simple way to reconstruct a list\n",
    "// able to do lots of non-trivial things with it though\n",
    "\n",
    "function construct(node) {\n",
    "    if(node === null) {\n",
    "        return null;\n",
    "    }\n",
    "    else {\n",
    "        node.next = construct(node.next);\n",
    "        return node;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "// addone: traverses list and adds 1 to every item in the list\n",
    "function addOne(node) {\n",
    "    if(node === null) {\n",
    "        return null;\n",
    "    }\n",
    "    else {\n",
    "        node.next = addOne(node.next);\n",
    "        node.data++;\n",
    "        return node;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "// copy a list\n",
    "function copy(node) {\n",
    "    if(node === null) {\n",
    "        return null;\n",
    "    }\n",
    "    else {\n",
    "        // assumes we also set the next\n",
    "        // attribute in the Node class as well\n",
    "        return new Node(node.item, copy(node.next));\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "// inserting an item into a sorted list\n",
    "// spcial case of empty lists and insertion at the beginning do not\n",
    "// occur with 'reconstruct the list' paradigm and algorithm is much simpler\n",
    "\n",
    "\n",
    "// assumes that new Node(data, node) where node = next\n",
    "\n",
    "// will return a node so that node.next = returned node\n",
    "function insertInOrder(data, node) {\n",
    "    if(node === null) {\n",
    "        // sets next to null\n",
    "        return new Node(data, null);\n",
    "    }\n",
    "    else if (node.data >= data) {\n",
    "        // if current node is greater than or equal to data\n",
    "        // then the new node should have the current node as its\n",
    "        // successor\n",
    "        // so we insert before the current node;\n",
    "        \n",
    "        // prev --> newNode --> node\n",
    "        return new Node(data, node);\n",
    "    }\n",
    "    else {\n",
    "        // else if current node is less than the data\n",
    "        // keep traversing until we reach appropriate place\n",
    "        // once we've returned, node.next will be et with the element\n",
    "        // in the right order\n",
    "        node.next = insertInOrder(data, node.next);\n",
    "        return node;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "// delete first occurrence of an item in a list\n",
    "\n",
    "function remove(data, node) {\n",
    "    // if null, return null\n",
    "    // or if the list is already sorted\n",
    "    // and we have surpassed the current value\n",
    "    if(node === null || node.data > data) {\n",
    "        return node;\n",
    "    }\n",
    "    else if (node.data === data) {\n",
    "        return node.next;\n",
    "    }\n",
    "    else {\n",
    "        node.next = remove(data, node.next);\n",
    "        return node;\n",
    "    }\n",
    "}\n",
    "\n",
    "// delete all instances of p in an unordered list\n",
    "\n",
    "function removeAll(data, node) {\n",
    "    if(node === null) {\n",
    "        return node;\n",
    "    }\n",
    "    \n",
    "    // essentially, this skips over the current node\n",
    "    // and just calls the function again\n",
    "    // which would return the next node once the recursion resolves\n",
    "    else if (node.data === data) {\n",
    "        return removeAll(data, node.next);\n",
    "    }\n",
    "    \n",
    "    // normally would return the current node\n",
    "    // if data is not the same\n",
    "    else {\n",
    "        node.next = removeAll(data, node.next);\n",
    "        return node;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "// delete last element in the list\n",
    "\n",
    "function deleteLast(node = this[head]) {\n",
    "    // p === null checks if list is empty\n",
    "    // the actual condition that will delete the last element\n",
    "    // is p.next === null\n",
    "    if(node === null || node.next === null) {\n",
    "        return null;\n",
    "    }\n",
    "    else {\n",
    "        node.next = deleteLast(node.next);\n",
    "        return node;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "// append 2 lists \n",
    "\n",
    "function append(node1 = this[head], node2) {\n",
    "    if(node1 === null) {\n",
    "        // if we have reached the end of list 1, just append\n",
    "        // entire list 2 to it\n",
    "        // remember that the first node of list 2 is the HEAD\n",
    "        // so if we attach the head, we have acces to the rest of the list\n",
    "        return node2;\n",
    "    }\n",
    "    else {\n",
    "        // else, keep appending until we reach the end of the list\n",
    "        node1.next = append(node1.next, node2);\n",
    "        return node1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "// zipping 2 lists together\n",
    "// alternate elements of 2 lists into 1 list\n",
    "// ex: 1 -> 3 -> 5 + 2 -> 4 -> 6 will be: 1 -> 2 -> 3 -> 4 -> 5 -> 6\n",
    "\n",
    "function zip(node1 = this[head], node2) {\n",
    "    // if we reached end of list 1, return list 2\n",
    "    if(node1 === null) {\n",
    "        return node2;\n",
    "    }\n",
    "    else if (node2 === null) {\n",
    "        return node1;\n",
    "    }\n",
    "    // since we always return p, we can just set p.next = q;\n",
    "    // and we can set q.next = zip(pNext, qNext) which would just be:\n",
    "    // q.next = p;\n",
    "    else {\n",
    "        node1Next = node1.next;\n",
    "        node2Next = node2.next;\n",
    "        node1.next = node2;\n",
    "        node2.next = zip(node1Next, node2Next);\n",
    "        return node1;\n",
    "    }\n",
    "}\n",
    "\n",
    "// alternative\n",
    "// more elegant\n",
    "function zipAlt(node1, node2) {\n",
    "    if(node1 === null) {\n",
    "        return node2;\n",
    "    }\n",
    "    else {\n",
    "        // this alternates the list parameters\n",
    "        // so node2 becomes node1 and node1 becomes node2 and vice versa\n",
    "        // everytime it is called\n",
    "        node1.next = zip(node2, node1.next);\n",
    "        return node1;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "// merge 2 sorted lists\n",
    "\n",
    "function merge(node1, node2) {\n",
    "    // if first list is empty, just return second list b/c they're sorted anyways\n",
    "    if(node1 === null) {\n",
    "        return node2;\n",
    "    }\n",
    "    // if node2 is empty, just return first lis\n",
    "    else if (node2 === null) {\n",
    "        return node1;\n",
    "    }\n",
    "    // else if node1 < node2, keep node2 the same and compare with next\n",
    "    //element in first list\n",
    "    else if (node1.data < node2.data) {\n",
    "        node1.next = merge(node1.next, node2);\n",
    "        return node1;\n",
    "    }\n",
    "    // if node2 < node1, keep node1 the same and compare with next\n",
    "    // element in second list\n",
    "    else {\n",
    "        node2.next = merge(node1, node2.next);\n",
    "        return node;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "// calculate running sum and recurse back up list\n",
    "// once we reach the end of the list, then we add in reverse\n",
    "// so if we have 1 --> 2 --> 3, it would add 3 + 2 + 1\n",
    "\n",
    "function sumList(node = this[head]) {\n",
    "    if(node === null) {\n",
    "        return 0;\n",
    "    }\n",
    "    else {\n",
    "        return node.data + sumList(node.next);\n",
    "    }\n",
    "}\n",
    "\n",
    "// tail recursion when we sum on the way down the list\n",
    "// adds elements in the list in the same direction as the traversal\n",
    "// so 1 --> 2 --> 3 would lead to 1 + 2 + 3\n",
    "\n",
    "function sumListDown(node = this[head]) {\n",
    "    return sumListHelper(node, 0);\n",
    "}\n",
    "\n",
    "function sumListHelper(node, sum) {\n",
    "    if(node === null) {\n",
    "        return sum;\n",
    "    }\n",
    "    else {\n",
    "        sum += node.data;\n",
    "        return sumListHelper(node.next, sum);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "// reversing a list\n",
    "// add node to end of the list\n",
    "\n",
    "function addToEnd(node = this[head], list) {\n",
    "    if(list === null) {\n",
    "        node.next = null;\n",
    "        return node;\n",
    "    }\n",
    "    else {\n",
    "        list.next = addToEnd(node, list.next);\n",
    "        return list;\n",
    "    }\n",
    "}\n",
    "\n",
    "function reverseList(list) {\n",
    "    if(list === null) {\n",
    "        return null;\n",
    "    }\n",
    "    else {\n",
    "        let temp = reverseList(list.next);\n",
    "        return addToend(list, temp);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "// reversing a linked list using a stack\n",
    "function reverse(node = this[head]) {\n",
    "    return reverseHelper(node, null);\n",
    "}\n",
    "\n",
    "function reverseHelper(node1, node2) {\n",
    "    if(node1 === null) {\n",
    "        return node2;\n",
    "    }\n",
    "    else {\n",
    "        let rest = node1.next;\n",
    "        node1.next = node2;\n",
    "        \n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "// checking if 2 lists are identical\n",
    "\n",
    "function identical(node1, node2) {\n",
    "    if(node1 === null && node2 === null) {\n",
    "        return true;\n",
    "    }\n",
    "    else if (node1.data === node2.data) {\n",
    "        return identical(node1.next, node2.next);\n",
    "    }\n",
    "    else {\n",
    "        return false;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "// finds the largest number in the list\n",
    "function largestNum(node, largest = 0) {\n",
    "    if(node === null) {\n",
    "        return largest;\n",
    "    }\n",
    "    else if (node.data > largest) {\n",
    "        largest = node.data;\n",
    "        return largestNum(node.next, largest);\n",
    "    }\n",
    "    else {\n",
    "        return largestNum(node.next, largest);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1, 2, 3, 4 ]\n",
      "[ 4, 3, 2, 1 ]\n"
     ]
    }
   ],
   "source": [
    "class LinkedListNode {\n",
    "    constructor(data) {\n",
    "        this.data = data;\n",
    "        this.next = null;\n",
    "    }\n",
    "}\n",
    "\n",
    "function printList(node) {\n",
    "    let current = node;\n",
    "    let arr = [];\n",
    "    while(current !== null) {\n",
    "        arr.push(current.data);\n",
    "        current = current.next;\n",
    "    }\n",
    "    console.log(arr)\n",
    "}\n",
    "\n",
    "function reverseList(node) {\n",
    "    let current = node;\n",
    "    let previous = null;\n",
    "    let following = null;\n",
    "    \n",
    "    while(current !== null) {\n",
    "        following = current.next;\n",
    "        current.next = previous;\n",
    "        previous = current;\n",
    "        current = following;\n",
    "    }\n",
    "    return;\n",
    "}\n",
    "\n",
    "// reverse a linked list\n",
    "var node1 = new LinkedListNode(1);\n",
    "var node2 = new LinkedListNode(2);\n",
    "var node3 = new LinkedListNode(3);\n",
    "var node4 = new LinkedListNode(4);\n",
    "\n",
    "node1.next = node2;\n",
    "node2.next = node3;\n",
    "node3.next = node4;\n",
    "\n",
    "// original list: 1, 2, 3\n",
    "printList(node1); // head\n",
    "\n",
    "//reversed it\n",
    "reverseList(node1);\n",
    "\n",
    "// reversed list: 3, 2, 1\n",
    "printList(node4); // head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stacks:\n",
    "* LIFO Ordering Principle: the last element inserted into the list is the first one out\n",
    "* very important data structure when you want to reverse the order of things\n",
    "* recursive algorithms implicitly use a stack\n",
    "* operations:\n",
    "    - push(item) = inserts item to the top of the stack O(1)\n",
    "    - pop = removes item from top of stack and returns it O(1)\n",
    "    - peek = returns the top item fro the stack without removing it O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack {\n",
    "    constructor() {\n",
    "        this.items = [];\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    push(item) {\n",
    "        this.items.push(item);\n",
    "        this.size++;\n",
    "    }\n",
    "    \n",
    "    pop(item) {\n",
    "        this.size--;\n",
    "        return this.items.pop();\n",
    "    }\n",
    "    \n",
    "    peek() {\n",
    "        return this.items[this.size - 1];\n",
    "    }\n",
    "    \n",
    "    get length() {\n",
    "        return this.size;\n",
    "    }\n",
    "    \n",
    "    isEmpty() {\n",
    "        return this.items === [];\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Queue:\n",
    "* FIFO Ordering Principle: \n",
    "    - the first element inserted into a queue will also be the first element removed from a queue\n",
    "    - think of it like waiting in line at the bars. the first person in the line will enter first while the last person in line will enter last\n",
    "* helps with implementing breadth first search\n",
    "* operations:\n",
    "    - enqueue(item) = adds a new item to the rear of the queue\n",
    "        - depending on implementation, will be O(1) or O(n)\n",
    "    - dequeue = removes item from the font of the queue and returns it\n",
    "        - also O(1) or O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "// implementation of a queue using an array\n",
    "// enqueue = O(n) and dequeue O(1)\n",
    "// beginning of array = beginning of queue\n",
    "// end of array = end of queue\n",
    "\n",
    "class Queue {\n",
    "    constructor() {\n",
    "        this.items = [];\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    // O(n) b/c we insert to front of array using .unshift()\n",
    "    // which is an O(n) b/c it moves everything to make\n",
    "    // space for this item\n",
    "    // so we move n items first, then add new item to front\n",
    "    enqueue(item) {\n",
    "        this.items.unshift(item);\n",
    "        this.size++;\n",
    "    } \n",
    "    \n",
    "    // O(1) b/c we just remove at the end\n",
    "    dequeue() {\n",
    "        this.size--;\n",
    "        return this.items.pop();\n",
    "    }\n",
    "    \n",
    "    get length() {\n",
    "        return this.size;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "/*\n",
    "implementation of a queue using an array\n",
    "however, enqueue is O(1) and dequeue is O(n)\n",
    "the front of an array is the rear of the queue and the\n",
    "back of the array is the front of the queue\n",
    "so we insert at the back using .push() and we remove\n",
    "from the front using .shift()\n",
    "*/\n",
    "\n",
    "class Queue2 {\n",
    "    constructor() {\n",
    "        this.items = [];\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    // O(1) b/c .push() adds to the back of the array\n",
    "    // which would at as the back of the queue\n",
    "    enqueue(item) {\n",
    "        this.items.push(item);\n",
    "        this.size++;\n",
    "    }\n",
    "    \n",
    "    // O(n) b/c .shift() removes from the front of the array\n",
    "    // and this would shift all the elements to the front\n",
    "    dequeue() {\n",
    "        this.size--;\n",
    "        return this.items.shift();\n",
    "    }\n",
    "    \n",
    "    isEmpty() {\n",
    "        return this.size === 0;\n",
    "    }\n",
    "    \n",
    "    get length() {\n",
    "        return this.size;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "// implementation of a queue using a doubly linked list with head/tail pointers\n",
    "// this will have an O(1) enqueue and an O(1) dequeue\n",
    "\n",
    "class node {\n",
    "    constructor(data) {\n",
    "        this.data = data;\n",
    "        this.next = null;\n",
    "        this.previous = null;\n",
    "    }\n",
    "}\n",
    "\n",
    "const head = Symbol('head');\n",
    "const tail = Symbol('tail');\n",
    "\n",
    "class Queue3 {\n",
    "    constructor() {\n",
    "        this[head] = null;\n",
    "        this[tail] = null;\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    enqueue(item) {\n",
    "        const newNode = new node(item);\n",
    "        if(this[head] === null) {\n",
    "            this[head] = newNode;\n",
    "            this[tail] = newNode;\n",
    "        }\n",
    "        else {\n",
    "            newNode.next = this[head];\n",
    "            this[head].previous = newNode;\n",
    "            this[head] = newNode;\n",
    "        }\n",
    "        this.size++;\n",
    "    }\n",
    "    \n",
    "    dequeue() {\n",
    "        if(this[head] !== null) {\n",
    "            let data;\n",
    "            if(this[head].next === null) {\n",
    "                data = this[head].data;\n",
    "                this[head] = null;\n",
    "                this[tail] = null;\n",
    "            }\n",
    "            else {\n",
    "                data = this[tail].data;\n",
    "                this[tail].previous.next = null;\n",
    "                this[tail] = this[tail].previous;\n",
    "            }\n",
    "            this.size--;\n",
    "            return data;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    isEmpty() {\n",
    "        return this[head] === null;\n",
    "    }\n",
    "    \n",
    "    get length() {\n",
    "        return this.size;\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        let current = this[head];\n",
    "        while(current !== null) {\n",
    "            yield current.data;\n",
    "            current = current.next;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Trees:\n",
    "* defintion 1: a tree consists of a set of nodes and a set of edges that connect pairs of nodes\n",
    "    - has a root node\n",
    "    - every node has a parent except the root node\n",
    "    - each node has a unique path from the root to itself\n",
    "    - if each node has a max of 2 children, it is a binary tree\n",
    "* definition 2: recursive\n",
    "    - base case: a tree is either empty\n",
    "    - recursive case: or consists of a root and zero or more subtrees, each of which is also a tree\n",
    "### Components of a Tree:\n",
    "* path = ordered list of nodes that are connected by edges\n",
    "* leaf node = node that has no outgoing edges/children\n",
    "* level = the level of a node n is the number of edges on that path from the root to n\n",
    "* height = equal to the max level of any node in three. so if we have a root node that has 2 children, the max level and thus height would be 1, because there is 1 edge between the root and its children"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tree Traversals\n",
    "* preorder: root --> left --> right\n",
    "* inorder: left --> root --> right\n",
    "* postorder: left --> right --> root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "function preOrder(node) {\n",
    "    if (node !== null) {\n",
    "        console.log(node.data);\n",
    "        preOrder(node.left);\n",
    "        preOrder(node.right);\n",
    "    }\n",
    "}\n",
    "\n",
    "function inOrder(node) {\n",
    "    if(node !== null) {\n",
    "        inOrder(node.left);\n",
    "        console.log(node.data);\n",
    "        inOrder(node.right);\n",
    "    }\n",
    "}\n",
    "\n",
    "function postOrder(node) {\n",
    "    if(node !== null) {\n",
    "        postOrder(node.left);\n",
    "        postOrder(node.right);\n",
    "        console.log(node.data);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Priority Queues with Binary Heaps\n",
    "* similar to a queue except that the front of the queue contains high priority items while the rear contains low priority items\n",
    "* a way to implement a priority queue is by using a binary heap which is like a binary tree\n",
    "    - a binary heap will allow enqueue and dequeue to be O(log n)\n",
    "* we can implement a heap using a single array\n",
    "* common variations of a binary heap:\n",
    "    - min heap: smallest key at the front\n",
    "    - max heap: largest key at the front \n",
    "* binary heap operations (for min but is symmetric with max):\n",
    "    - insert(k): adds a new item, k, to the heap\n",
    "    - findMin: returns item with min key value and removes it from the heap\n",
    "    - delMin: returns item with min key value and removes it from the heap\n",
    "    - buildHeap(list): builds a new heap from a list of keys\n",
    "* implementation details:\n",
    "    - to ensure logarithmic performance on operations, the tree will have to be balanced by creating a complete binary tree\n",
    "        - complete meaning that each level of the tree is filled in except for the rightmost position in the bottom level\n",
    "    - can represent this heap using a single list\n",
    "        - parent = index p;\n",
    "        - left child = index 2p;\n",
    "        - right child = index 2p + 1;\n",
    "        - and t find a parent f a nde n, it is integer division n/2 or Math.floor(n / 2)\n",
    "* heap order property:\n",
    "    - for every node x with parent p, p.key <= x.key\n",
    "* heap operations:\n",
    "    - insert:\n",
    "        - we insert the new node at the rear of the heap (essentially the bottom of the binary tree)\n",
    "        - then we use a helper function to move the new item up the tree until it is in the right place\n",
    "        - essentially, the new node will compare itsvalue with its parent's value, then if new < parent, then swap places between parent and new\n",
    "    - delMin:\n",
    "        - put value of root into a variable min\n",
    "        - put last item in heap into the root\n",
    "        - move this item down the tree, swapping with items that are smaller than it\n",
    "        - then return the min value\n",
    "* build heap from an array in O(n) operations\n",
    "    - starting from the middle of the array and moving backwards, we essentially percolate the items down\n",
    "    - starting from the middle ensures that the largest item is moved down the entire tree\n",
    "    - b/c the heap is a complete binary tree, any nodes past the halfway point of the array will be leaves\n",
    "    - the reason why it is O(n) is because log n is derived from the height of the tree, and the tree is actually shorter than log n for most of the work in building a heap from the array\n",
    "    - this is useful for sorting using a heap in O(n log n) time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "// implementation of a min heap\n",
    "\n",
    "class BinHeap {\n",
    "    constructor() {\n",
    "        // zero in the array not used but\n",
    "        // is there so that simple integer division can be used\n",
    "        // in later methods\n",
    "        this.heapList = [0];\n",
    "        this.currentSize = 0;\n",
    "    }\n",
    "    \n",
    "    insert(k) {\n",
    "        this.heapList.append(k);\n",
    "        this.currentSize++;\n",
    "        this.percUp(this.currentSize);\n",
    "    }\n",
    "    \n",
    "    percUp(i) {\n",
    "        let p = Math.trunc(i / 2); //parent node\n",
    "        while(p > 0) {\n",
    "            if(this.heapList[i] < this.heapList[p]) {\n",
    "                let temp = this.heapList[p];\n",
    "                this.heapList[p] = this.heapList[i];\n",
    "                this.heapList[i] = temp;\n",
    "            }\n",
    "            i = p;\n",
    "            p = Math.trunc(i / 2);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    delMin() {\n",
    "        // we have the zero at heapList[0] for easier int. dvsn\n",
    "        const retVal = this.heapList[1];\n",
    "        this.heapList[1] = this.heapList[this.currentSize];\n",
    "        this.currentSize--;\n",
    "        this.heapList.pop();\n",
    "        this.percDown(1);\n",
    "        return retVal;\n",
    "    }\n",
    "    \n",
    "    percDown(i) {\n",
    "        while ( (i * 2) < this.currentSize ) {\n",
    "            let mc = this.minChild(i);\n",
    "            if(this.heapList[i] > this.heapList[mc]) {\n",
    "                let temp = this.heapList[i];\n",
    "                this.heapList[i] = this.heapList[mc];\n",
    "                this.heapList[mc] = temp;\n",
    "            }\n",
    "            i = mc;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    minChild(i) {\n",
    "        let leftChild = i * 2;\n",
    "        let rightChild = (i * 2) + 1;\n",
    "        \n",
    "        // if there is no right child, return left child\n",
    "        if(rightChild > this.currentSize) {\n",
    "            return leftChild;\n",
    "        }\n",
    "        // else if there is right and left children\n",
    "        // return the smallest of the 2 in value\n",
    "        else {\n",
    "            return this.heapList[leftChild] < this.heapList[rightChild] ? leftChild : rightChild;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    buildHeap(alist) {\n",
    "        let i = Math.trunc( alist.length / 2);\n",
    "        this.currentSize = alist.length;\n",
    "        this.heapList = [0].concat(alist);\n",
    "        while(i > 0) {\n",
    "            this.percDown(i);\n",
    "            i--;\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search Trees\n",
    "* Operations:\n",
    "    - put = inserts a new item into the bst\n",
    "        - limiting factor = height of the tree\n",
    "        - worst case of a balanced binary tree is O(log n) b/c half of the elements will be less than the root and the other half will be greater than the root\n",
    "        - if the keys were inserted in sorted order, then we will have the tree be skewed in one direction and thus it will be O(n) since the tree will have more nodes in either the left or right subtree by a substantial amount\n",
    "    - del = deletes an item in the bst\n",
    "        - also O(log n) b/c it has to find the successor which is about O(logn) as well\n",
    "    - get = returns the value at a node with matching key. accepts key as param\n",
    "        - also O(log n) b/c it has to traverse the tree to find the right one\n",
    "* BST Property:\n",
    "    - key values less than its parent are in the left subtree\n",
    "    - key values greater than its parent are in the right subtree\n",
    "    - this property applies for every node in the tree\n",
    "* three cases to consider when we want to delete a node containing the key we want deleted:\n",
    "    - 1. node to be deleted has no children\n",
    "        - easiest b/c it is a leaf\n",
    "        - so just remove any reference of it from the parent\n",
    "    - 2. node to be deleted has only 1 child\n",
    "        - replace the current node with its child\n",
    "    - 3. node to be deleted has 2 children\n",
    "        - then we go into the current node's right subtree and find its successor\n",
    "        - then we go into teh current node's right subtree and find its successor\n",
    "        - basically, we find the min value in the right subtree so that we find the next largest item after our current node\n",
    "        - if the successor is literally the right child of our current node, we can just replace our current node with it\n",
    "        - if the successor is not the right child, we replace the successor by its own right child, then we replace the current node with the successor to maintain bst property\n",
    "* on average, all operations are O(log n) where height of bst = log n\n",
    "    - if the keys are inserted into a binary tree in SORTED ORDER, then we will be skewing the tree in either the left or right subtrees substantially, and thus performance will be reduced to O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode {\n",
    "    constructor(key, val, left = null, right = null, parent = null) {\n",
    "        this.key = key;\n",
    "        this.payload = val;\n",
    "        this.left = left;\n",
    "        this.right = right;\n",
    "        this.parent = parent;\n",
    "    }\n",
    "    \n",
    "    hasLeftChild() {\n",
    "        return this.left !== null;\n",
    "    }\n",
    "    \n",
    "    hasRightChild() {\n",
    "        return this.right !== null;\n",
    "    }\n",
    "    \n",
    "    isLeftChild() {\n",
    "        return this.parent !== null && this.parent.left === this;\n",
    "    }\n",
    "    \n",
    "    isRightChild() {\n",
    "        return this.parent !== null && this.parent.right === this;\n",
    "    }\n",
    "    \n",
    "    isRoot() {\n",
    "        return this.parent === null;\n",
    "    }\n",
    "    \n",
    "    isLeaf() {\n",
    "        return !( this.hasAnyChildren() );\n",
    "    }\n",
    "    \n",
    "    hasAnyChildren() {\n",
    "        return this.hasLeftChild() || this.hasRightChild();\n",
    "    }\n",
    "    \n",
    "    hasBothChildren() {\n",
    "        return this.hasLeftChild() && this.hasRightChild();\n",
    "    }\n",
    "    \n",
    "    replaceNodeData(key, value, left, right) {\n",
    "        this.key = key;\n",
    "        this.payload = value;\n",
    "        this.left = left;\n",
    "        this.right = right;\n",
    "        if(this.hasLeftChild()) {\n",
    "            this.left.parent = this;\n",
    "        }\n",
    "        if(this.hasRightChild()) {\n",
    "            this.right.parent = this;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    findSuccessor() {\n",
    "        let successor;\n",
    "        \n",
    "        // if current node has a right subtree, find the minimum of\n",
    "        // right subtree\n",
    "        if(this.hasRightChild()) {\n",
    "            successor = this.right.findMin();\n",
    "        }\n",
    "        \n",
    "        // else if it does not have a right subtree, then it will have an ancestor\n",
    "        // who is a left child of its parent\n",
    "        // and the parent is the successor\n",
    "        // else if it is a right child, keep going up the tree\n",
    "        \n",
    "        else {\n",
    "            if(this.parent !== null) {\n",
    "                if(this.isLeftChild()) {\n",
    "                    successor = this.parent;\n",
    "                }\n",
    "            }\n",
    "            else {\n",
    "                // we remove our node from the tree temporarily\n",
    "                // find the successor again\n",
    "                // then add it back\n",
    "                // this is because we call findSuccessor on the parent\n",
    "                // and since it has a rightChild (previous node), then it will assign\n",
    "                // the successor to the current node\n",
    "                // so we remove it temporarily until we find the correct node\n",
    "                this.parent.right = null;\n",
    "                successor = this.parent.findSuccessor();\n",
    "                this.parent.right = this;\n",
    "            }\n",
    "        }\n",
    "        return successor;\n",
    "    }\n",
    "    \n",
    "    // the minimum in a binary search tree is the leftmode node in the tree\n",
    "    findMin() {\n",
    "        let current = this;\n",
    "        while(current.hasLeftChild()) {\n",
    "            current = current.left;\n",
    "        }\n",
    "        return current;\n",
    "    }\n",
    "    \n",
    "    spliceOut() {\n",
    "        // if the node is a leaf, then change the parent's child\n",
    "        // reference to be null depending on whether it was a \n",
    "        // right of left child\n",
    "        if(this.isLeaf()) {\n",
    "            if(this.isLeftChild()) {\n",
    "                this.parent.left = null;\n",
    "            }\n",
    "            else {\n",
    "                this.parent.right = null;\n",
    "            }\n",
    "        }\n",
    "        else if (this.hasAnyChild()) {\n",
    "            if(this.hasLeftChild()) {\n",
    "                if(this.isLeftChild()) {\n",
    "                    this.parent.left = this.left;\n",
    "                }\n",
    "                else {\n",
    "                    this.parent.right = this.left;\n",
    "                }\n",
    "                this.left.parent = this.parent;\n",
    "            }\n",
    "            else {\n",
    "                if(this.isLeftChild()) {\n",
    "                    this.parent.left = this.right;\n",
    "                }\n",
    "                else {\n",
    "                    this.parent.right = this.right;\n",
    "                }\n",
    "                this.right.parent = this.parent;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "const root = Symbol('root');\n",
    "\n",
    "class BinarySearchTree {\n",
    "    constructor() {\n",
    "        this[root] = null;\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    get length() {\n",
    "        return this.size;\n",
    "    }\n",
    "    \n",
    "    // prints out the bst in correct order\n",
    "    inOrder(node = this[root]) {\n",
    "        if(node !== null) {\n",
    "            this.inOrder(node.left);\n",
    "            console.log(node.payload);\n",
    "            this.inOrder(node.right);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // inserting items into bst\n",
    "    put(key, val) {\n",
    "        // if the tree is not empty, then find the correct position\n",
    "        // for it\n",
    "        if(this[root] !== null) {\n",
    "            this._put(key, val, this[root]);\n",
    "        }\n",
    "        // else if the tree is empty, just put the new node\n",
    "        // as the root of the tree\n",
    "        else {\n",
    "            this[root] = new TreeNode(key,val);\n",
    "        }\n",
    "        this.size++;\n",
    "    }\n",
    "    \n",
    "    //recursive function that helps find the correct position for the new item.\n",
    "    // it will move left or right depending on value of new node and parent\n",
    "    // until it reaches a node that does not have a child or both children\n",
    "    _put(key, val, currentNode) {\n",
    "        if(key < currentNode.key) {\n",
    "            if(currentNode.hasLeftChild()) {\n",
    "                this._put(key, val, currentNode.left);\n",
    "            }\n",
    "            else {\n",
    "                currentNode.left = new TreeNode(key, val, null, null, currentNode);\n",
    "            }\n",
    "        }\n",
    "        else {\n",
    "            if(currentNode.hasRightChild()) {\n",
    "                this._put(key, val, currentNode.right);\n",
    "            }\n",
    "            else {\n",
    "                currentNode.right = new TreeNode(key, val, null, null, currentNode);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // returns the value of the node at the current key\n",
    "    // if the tree is not empty, calls a recursive function _get\n",
    "    // to traverse the tree to find it\n",
    "    get(key) {\n",
    "        if(this[root] === null) {\n",
    "            return undefined;\n",
    "        }\n",
    "        const result = this._get(key, this[root]);\n",
    "        return result ? result.payload : undefined;\n",
    "    }\n",
    "    \n",
    "    // recursive function that will traverse the tree until it finds the key\n",
    "    // if the key is less than the parent, go left\n",
    "    // if the key is greater than the parent, go right\n",
    "    _get(key, currentNode) {\n",
    "        if(currentNode === null) {\n",
    "            return undefined;\n",
    "        }\n",
    "        else if (currentNode.key === key) {\n",
    "            return currentNode;\n",
    "        }\n",
    "        else if (key < currentNode.key) {\n",
    "            return this._get(key, currentNode.left);\n",
    "        }\n",
    "        else {\n",
    "            return this._get(key, currentNode.right);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    del(key) {\n",
    "        if(this.size > 1) {\n",
    "            const nodeToRemove = this._get(key, this[root]);\n",
    "            if(nodeToRemove) {\n",
    "                this.remove(nodeToRemove);\n",
    "                this.size--;\n",
    "            }\n",
    "            else {\n",
    "                return undefined;\n",
    "            }\n",
    "        }\n",
    "        else if (this.size === 1 && this[root].key === key) {\n",
    "            this[root] = null;\n",
    "            this.size--;\n",
    "        }\n",
    "        else {\n",
    "            return undefined;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    remove(currentNode) {\n",
    "        if(currentNode.isLeaf()) {\n",
    "            if(currentNode.isLeftChild()) {\n",
    "                currentNode.parent.left = null;\n",
    "            }\n",
    "            else {\n",
    "                currentNode.parent.right = null;\n",
    "            }\n",
    "        }\n",
    "        // else if currentnode has 2 children\n",
    "        // find the successor, splice it out\n",
    "        // and replace currentNode with successor\n",
    "        else if (currentNode.hasBothChildren()) {\n",
    "            let successor = currentNode.findSuccessor();\n",
    "            successor.spliceOut();\n",
    "            currentNode.key = successor.key;\n",
    "            currentNode.payload = successor.payload;\n",
    "        }\n",
    "        // node has only 1 child\n",
    "        else {\n",
    "            if(currentNode.hasLeftChild()) {\n",
    "                if(currentNode.isLeftChild()) {\n",
    "                    currentNode.left.parent = currentNode.parent;\n",
    "                    currentNode.parent.left = currentNode.left;\n",
    "                }\n",
    "                else if (currentNode.isRightChild()){\n",
    "                    currentNode.left.parent = currentNode.parent;\n",
    "                    currentNode.parent.right = currentNode.left;\n",
    "                }\n",
    "                else {\n",
    "                    currentNode.replaceNodeData(currentNode.left.key,\n",
    "                                                currentNode.left.payload,\n",
    "                                                currentNode.left.left,\n",
    "                                                currentNode.left.right)\n",
    "                }\n",
    "            }\n",
    "            else {\n",
    "                if(currentNode.isLeftChild()) {\n",
    "                    currentNode.right.parent = currentNode.parent;\n",
    "                    currentNode.parent.left = currentNode.right;\n",
    "                }\n",
    "                else if (currentNode.isRightChild()) {\n",
    "                    currentNode.right.parent = currentNode.parent;\n",
    "                    currentNode.parent.right = currentNode.right;\n",
    "                }\n",
    "                else {\n",
    "                    currentNode.replaceNodeData(currentNode.right.key.\n",
    "                                                currentNode.right.payload,\n",
    "                                                currentNode.right.left,\n",
    "                                                currentNode.right.right)\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    }  \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Balanced Binary Search Trees:\n",
    "* easiest way to create a balanced binary search tree given an array of keys is to:\n",
    "    1. sort the array of keys. this will be O(n log n) if you use something like merge sort\n",
    "    2. then you first insert the middle element in the array to act as the root\n",
    "        - since it is already sorted, the middle element will be able to split the list of elements in half on either side\n",
    "    3. then you split the arrays into left, and right subarrays and find the middle of those to insert into the tree\n",
    "    4. you can do the left and right splits recursively by inserting from the middle in the left subarray first, then move onto the middle of the right subarray\n",
    "    * thus, this method will be O(n log n) to create a balanced binary tree from a list of random keys\n",
    "    * if we inserted the keys randomly, we cannot guarantee that the root will be able to split the list of elements evenly, and thus operations might degrade to O(n)\n",
    "* however, there is a variation of the bst that allows for balancing on every insert\n",
    "    - this is called an AVL TREE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## AVL Tree:\n",
    "* keeps track of a balance factor of each node by looking at the heights of the left and right subtrees of each node\n",
    "    - balance factor (bf) = height(leftSubtree) - height(rightSubtree)\n",
    "    - if bf = -1, 0, 1, then the tree is balanced\n",
    "    - if bf > 1, tree is left-heavy, meaning there are more nodes in the left subtree than the right\n",
    "    - if the buf < -1, then the tree is right-heavy, meaning there are more nodes in the right subtree than the left\n",
    "* searching in our AVL tree will ensure O(logn) performance b/c at any time, the ieght of the tree is equal to 1.44 * log N where N = number of nodes in the tree\n",
    "    - since we discard constants when thinking about big O, this essentially means the height in our tree will be logN at any time, and thus searching is limited to O(log N) since this operation is dependent on the height of the tree\n",
    "* implementation details:\n",
    "    - if new node is a left child, increase bf by 1\n",
    "    - if new node is a right child, decrease bf by 1\n",
    "    - updating bf can be done recursively, here are base cases:\n",
    "        - recursive call reached root of tree\n",
    "        - bf of parent has been adjusted to zero. once the parent has a bf of zero, then we can assume that the balance of its ancesotr nodes does not change\n",
    "* how do we actually rebalance a tree?\n",
    "    - we perform rotations on it\n",
    "    - left rotation:\n",
    "        1. promote right child to be root of subtree\n",
    "        2. move old root to be left child of new root\n",
    "        3. if new root had a left child, make it the right child of the new left child\n",
    "    - right rotation:\n",
    "        1. promote left child to be root of subtree\n",
    "        2. move old root to be right child of new root\n",
    "        3. if new root had a right child, make it the left child of the new right child"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graphs\n",
    "* vertex: essentially a node like in a tree with a key and some values\n",
    "* edge: an edge connects 2 vertices together and can either by 1-way or 2-way\n",
    "    - 1-way edges are called directed edges\n",
    "    - if all edges in a graph are 1-way, then it is a directed graph\n",
    "    - 2-way edges are undirected\n",
    "    - if all edges are undirected, then it is an undirected graph\n",
    "* weight: the cost associated with going through an edge that connects 1 node to another node\n",
    "    - node1 node2\n",
    "    - going from node1 to node2 via that edge has a weight of 6\n",
    "* defintion: a graph G can be represented by G = (V, E) where V is a set of vertices and E is a set of edges\n",
    "    - each edge is a tuple (v, w) where v, w both belong to the set of vertices\n",
    "    - can also add a weight to the edges as well so E = (v, w, c) where c is the weight\n",
    "* path: sequences of vertices that connected by edges from one vertex to another\n",
    "* cycle: cycle in a directed graph is a path that starts and ends at the same vertex\n",
    "    - DAG = directed acyclic graph = directed graph with no cycles\n",
    "* operations:\n",
    "    - addVertex(vert): adds an instance of vertex to the graph\n",
    "    - addEdge(fromVert, toVert): adds a new, directed edge to the graph that connects 2 vertices\n",
    "    - addEdge(fromVert, toVert, weight): adds a new, weighted, directed edge to the graph that connects 2 vertices\n",
    "    - getVertex(vertKey): finds the vertex in the graph named vertKey\n",
    "    - getVertices(): returns list to all vertices in the graph\n",
    "    - in: returns True for a state of the form vertex in graph, if the vertex is in the graph, false otherwise\n",
    "* main ways to implement a graph:\n",
    "    - adjacency matrix\n",
    "    - adjacency list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adjacency Matrix\n",
    "* 2D matrix to represent a graph\n",
    "* value stored at row v and column w represent an edge between them, meaning those 2 nodes are adjacent to each other\n",
    "* advantage:\n",
    "    - simple\n",
    "    - easy to see node connections\n",
    "    - good to use when the number of edges in a graph are large\n",
    "* disadvantage:\n",
    "    - not great for 'sparse' data meaning that the data does not fill out the grid entirely so there's a lot of empty space\n",
    "    - would essentially need a graph that has |V|^2 edges to be efficient"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adjacency List\n",
    "* has a list of all vertices in the graph\n",
    "    - each vertex also has a list of other vertices that it is connected to\n",
    "* our implementation will use a hash table rather than an array\n",
    "* advantage:\n",
    "    - compactly represents sparse data\n",
    "    - able to look at a vertex and know about every other node it is connected to. unlike an adjacency matrix, you don't have to iterate through the entire matrix to find that info out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "// adjacency list implementation\n",
    "\n",
    "class Vertex {\n",
    "    constructor(key) {\n",
    "        this.id = key;\n",
    "        this.connectedTo = new Map();\n",
    "    }\n",
    "    \n",
    "    // adds a neighbor to this vertex\n",
    "    // weight is default 0 if unweighted\n",
    "    addNeighbor(nbr, weight = 0) {\n",
    "        this.connectedTo.set(nbr, weight);\n",
    "    }\n",
    "    \n",
    "    // returns list of connections to this vertex via the keys\n",
    "    // in the connectedTo object\n",
    "    getConnections() {\n",
    "        return this.connectedTo;\n",
    "    }\n",
    "    \n",
    "    getId() {\n",
    "        return this.id;\n",
    "    }\n",
    "    \n",
    "    // returns the weight of an edge between this node and a neighbor\n",
    "    getWeight(nbr) {\n",
    "        return this.connectedTo.get(nbr);\n",
    "    }\n",
    "}\n",
    "\n",
    "class Graph {\n",
    "    constructor() {\n",
    "        this.vertList = new Map();\n",
    "        this.numVertices = 0;\n",
    "    }\n",
    "    \n",
    "    addVertex(key) {\n",
    "        this.numVertices++;\n",
    "        const newVertex = new Vertex(key);\n",
    "        this.vertList.set(key, newVertex);\n",
    "        return newVertex;\n",
    "    }\n",
    "    \n",
    "    getVertex(key) {\n",
    "        return this.vertList.has(key) ? this.vertList.get(key) : undefined;\n",
    "    }\n",
    "    \n",
    "    addEdge(from, to, weight = 0) {\n",
    "        if(!this.vertList.has(from)) {\n",
    "            this.addVertex(from);\n",
    "        }\n",
    "        if(!this.vertList.has(to)) {\n",
    "            this.addvertex(to);\n",
    "        }\n",
    "        this.vertList.get(from).addNeighbor(this.vertList.get(to), weight);\n",
    "    }\n",
    "    \n",
    "    getVertices() {\n",
    "        return this.vertList.keys();\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        for(let [key, value] of this.vertList) {\n",
    "            yield value;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing Breadth First Search (BFS)\n",
    "* breadth first search finds all nodes 1 level at a time starting from some node s\n",
    "    - so given a node s, BFS will find all adjacent nodes to s, then for each of these adjacent nodes, it will find adjacent nodes to those adjacent nodes\n",
    "* BFS colors each vertex white, gray, or black\n",
    "    - every node is initially white\n",
    "    - if it is discovered, then it becomes gray\n",
    "    - when every node adjacent to that node is discovered, then it becomes black so no white nodes adjacent to it, only gray or black ones\n",
    "* BFS USES A QUEUE TO DETERMINE WHICH NODE TO DISCOVER NEXT!!!\n",
    "    - rememeber BBQ\n",
    "    - B = breadth first search, and the Q = queue\n",
    "* Analysis:\n",
    "    - the while loop iterates through every node in the graph once so it is O(V)\n",
    "    - the for loop iterates through every edge of that particular vertex and we only do it for a node that has been dequeued, therefore it is O(E)\n",
    "    - total = O(V + E)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "// adjacency list implementation\n",
    "\n",
    "// this new vertex implementation for bfds to work contains 3 new class fields\n",
    "// distance = distance from starting node\n",
    "// predecessor = the node that is befre it and has an edge to it\n",
    "// color = the color of the node to determine whether it has been fully explored\n",
    "\n",
    "class Vertex {\n",
    "    constructor(key) {\n",
    "        this.id = key;\n",
    "        this.connectedTo = new Map();\n",
    "        this.dist = null;\n",
    "        this.predecessor = null;\n",
    "        this.colour = 'white';\n",
    "    }\n",
    "    \n",
    "    addNeighbor(nbr, weight = 0) {\n",
    "        this.connectedTo.set(nbr, weight);\n",
    "    }\n",
    "    \n",
    "    getConnections() {\n",
    "        return this.connectedTo;\n",
    "    }\n",
    "    \n",
    "    getId() {\n",
    "        return this.id;\n",
    "    }\n",
    "    \n",
    "    getWeight(nbr) {\n",
    "        this.connectedTo.get(nbr);\n",
    "    }\n",
    "    \n",
    "    get color() {\n",
    "        return this.colour;\n",
    "    }\n",
    "    \n",
    "    set color(value) {\n",
    "        this.colour = value;\n",
    "    }\n",
    "    \n",
    "    get distance() {\n",
    "        return this.dist;\n",
    "    }\n",
    "    \n",
    "    set distance(value) {\n",
    "        this.dist = value;\n",
    "    }\n",
    "    \n",
    "    get pred() {\n",
    "        return this.predecessor;\n",
    "    }\n",
    "    \n",
    "    set pred(value) {\n",
    "        this.predecessor = value;\n",
    "    }\n",
    "}\n",
    "\n",
    "class Graph {\n",
    "    constructor() {\n",
    "        this.vertList = new Map();\n",
    "        this.numVertices = 0;\n",
    "    }\n",
    "    \n",
    "    addVertex(key) {\n",
    "        this.numVertices++;\n",
    "        const newVertex = new Vertex(key);\n",
    "        this.vertList.set(key, newVertex);\n",
    "        return newVertex;\n",
    "    }\n",
    "    \n",
    "    getVertex(key) {\n",
    "        return this.vertList.has(key) ? this.vertList.get(key) : undefined;\n",
    "    }\n",
    "    \n",
    "    addEdge(from, to, weight = 0) {\n",
    "        if(!this.vertList.has(from)) {\n",
    "            this.addVertex(from);\n",
    "        }\n",
    "        if(!this.vertList.has(to)) {\n",
    "            this.addVertex(to);\n",
    "        }\n",
    "        this.vertList.get(from).addNeighbor(this.vertList.get(to), weight);\n",
    "    }\n",
    "    \n",
    "    getVertices() {\n",
    "        return this.vertList.keys();\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        for(let [key, value] of this.vertList) {\n",
    "            yield value;\n",
    "        }    \n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "}\n",
    "\n",
    "class Queue {\n",
    "    constructor() {\n",
    "        this.items = [];\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    enqueue(item) {\n",
    "        this.items.push(item);\n",
    "        this.size++;\n",
    "    }\n",
    "    \n",
    "    dequeue(item) {\n",
    "        this.size--;\n",
    "        return this.items.shift();\n",
    "    }\n",
    "    \n",
    "    get length() {\n",
    "        return this.size;\n",
    "    }    \n",
    "}\n",
    "\n",
    "function bfs(g,start) {\n",
    "    start.distance = 0;\n",
    "    start.predecessor = null;\n",
    "    let queue = new Queue();\n",
    "    queue.enqueue(start);\n",
    "    \n",
    "    while(queue.size > 0) {\n",
    "        // get current node from queue\n",
    "        let currentVert = queue.dequeue();\n",
    "        // for every nbr of the current vertex\n",
    "        // if the nbr's color is white, then change it to gray\n",
    "        // set its distance to current distance + 1;\n",
    "        // set pred as the current vertex\n",
    "        // and add it to the queue to explore it some more\n",
    "        for(let [nbr, value] of currentVert.getConnections()) {\n",
    "            if(nbr.color === 'white') {\n",
    "                nbr.color = 'gray';\n",
    "                nbr.distance = currentVert.distance + 1;\n",
    "                nbr.pred = currentVert;\n",
    "                queue.enqueue(nbr);\n",
    "            }\n",
    "        }\n",
    "        // once all of the current vertex's nbrs have been discovered\n",
    "        // then set the color to black\n",
    "        currentVert.color = 'black';\n",
    "    }\n",
    "}\n",
    "\n",
    "\n",
    "// starting at any node\n",
    "// follow its predecessor until it reaches the root\n",
    "function traverse(node) {\n",
    "    let x = node;\n",
    "    while(x.pred !== null) {\n",
    "        console.log(x.getId());\n",
    "        x = x.pred;\n",
    "    }\n",
    "    console.log(x.getId());\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing Depth First Search (DFS)\n",
    "* goal is to search as deeply as possible starting from one node, then moving onto subsequent nodes\n",
    "* uses recursion to do the job so it implicitly uses a stack\n",
    "* it essentially creates a tree or maybe even several trees\n",
    "    - several trees = depth first forest\n",
    "* uses 2 additional instance variables: discovery and finish times\n",
    "    - discovery: tracks number of steps in algorithm before a vertex is first encountered\n",
    "    - finish: number of steps in algorithm before a vertex is colored black\n",
    "* parenthesis property: all children of a particular node in a depth first tree have later discovery times and earlier finish times than their parents\n",
    "    - for example, the deepest node in a branch is the first one to finish being explored and will hvae a lower finish time than its parent who will be explored last\n",
    "* Analysis:\n",
    "    - both loops in dfs run in O(V) time b/c they iterate over all vertices in the graph\n",
    "    - the loop in dfsvisit is executed once for each edge in the adjacency list of the current vertex of the current vertex and is only called if the vertex is white. it will only execute a max of once for every edge in the graph so it is O(E)\n",
    "    - total = O(V + E)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Vertex {\n",
    "    constructor(key) {\n",
    "        this.id = key;\n",
    "        this.connectedTo = new Map();\n",
    "        this.dist = null;\n",
    "        this.predecessor = null;\n",
    "        this.colour = 'white';\n",
    "        this.disc = null;\n",
    "        this.fin = null;\n",
    "    }\n",
    "    \n",
    "    //adds a neighbor to this vertex\n",
    "    // weight is default 0 if unweighted\n",
    "    addNeighbor(nbr, weight = 0) {\n",
    "        this.connectedTo.set(nbr, weight);\n",
    "    }\n",
    "    \n",
    "    // returns list of connections to this vertex via the keys\n",
    "    // in the connectedTo object\n",
    "    getConnections() {\n",
    "        return this.connectedTo;\n",
    "    }\n",
    "    \n",
    "    getId() {\n",
    "        return this.id;\n",
    "    }\n",
    "    \n",
    "    // returns the weight of an edge between this node and a neighbor\n",
    "    getWeight(nbr) {\n",
    "        return this.connectedTo.get(nbr);\n",
    "    }\n",
    "    \n",
    "    get color() {\n",
    "        return this.colour;\n",
    "    }\n",
    "    \n",
    "    set color(value) {\n",
    "        this.colour = value;\n",
    "    }\n",
    "    \n",
    "    get distance() {\n",
    "        return this.dist;\n",
    "    }\n",
    "    \n",
    "    set distance(value) {\n",
    "        this.dist = value;\n",
    "    }\n",
    "    \n",
    "    get pred() {\n",
    "        return this.predecessor;\n",
    "    }\n",
    "    \n",
    "    set pred(value) {\n",
    "        this.predecessor = value;\n",
    "    }\n",
    "    \n",
    "    get discovery() {\n",
    "        return this.disc;\n",
    "    }\n",
    "    \n",
    "    set discovery(value) {\n",
    "        this.disc = value;\n",
    "    }\n",
    "    \n",
    "    get finish() {\n",
    "        return this.fin;\n",
    "    }\n",
    "    \n",
    "    set finish(value) {\n",
    "        this.fin = value;\n",
    "    }\n",
    "}\n",
    "\n",
    "class Graph {\n",
    "    constructor(){\n",
    "        this.vertList = new Map();\n",
    "        this.numVertices = 0;\n",
    "    }\n",
    "    \n",
    "    addVertex(key) {\n",
    "        this.numVertices++;\n",
    "        const newVertex = new Vertex(key);\n",
    "        this.vertList.set(key, newVertex);\n",
    "        return newVertex;\n",
    "    }\n",
    "    \n",
    "    getVertex(key) {\n",
    "        return this.vertList.has(key) ? this.vertList.get(key) : undefined;\n",
    "    }\n",
    "    \n",
    "    addEdge(from, to, weight = 0) {\n",
    "        if(! this.vertList.has(from) ) {\n",
    "            this.addVertex(from);\n",
    "        }\n",
    "        if(! this.vertList.has(to) ) {\n",
    "            this.addVertex(to);\n",
    "        }\n",
    "        this.vertList.get(from).addNeighbor(this.vertList.get(to), weight);\n",
    "    }\n",
    "    \n",
    "    getVertices() {\n",
    "        return this.vertList.keys();\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        for(let [key, value] of this.vertList) {\n",
    "            yield value;\n",
    "        };\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "}\n",
    "\n",
    "class DFSGraph extends Graph {\n",
    "    constructor() {\n",
    "        super();\n",
    "        this.time = 0;\n",
    "    }\n",
    "    \n",
    "    dfs() {\n",
    "        // initializes each vertex with a color 'white'\n",
    "        // and a pred of -1 (basically no pred)\n",
    "        for(let [key, vertex] of this.vertList) {\n",
    "            vertex.color = 'white';\n",
    "            vertex.pred = -1;\n",
    "        }\n",
    "        for(let [key, vertex] of this.vertList) {\n",
    "            if(vertex.color === 'white') {\n",
    "                this.dfsvisit(vertex);\n",
    "            } \n",
    "        }\n",
    "    }\n",
    "    \n",
    "    dfsvisit(startVertex) {\n",
    "        // set the current vertex's color to gray b/c it is explored\n",
    "        startVertex.color = 'gray';\n",
    "        this.time++;\n",
    "        startVertex.discovery = this.time;\n",
    "        // for every nbr of the current node\n",
    "        // if it has not been explored yet, then call dfsvisit on it\n",
    "        // and explore it\n",
    "        for(let [nextVertex, value] of startVertex.getConnections()) {\n",
    "            if(nextVertex.color === 'white') {\n",
    "                nextVertex.pred = startVertex;\n",
    "                this.dfsvisit(nextVertex);\n",
    "            }\n",
    "        }\n",
    "        // once it has reached the deepest node it can in the current branch\n",
    "        // and returned to the currentVertex, then all of its descendants have been\n",
    "        // explored (gray or black)\n",
    "        // and this vertex can be colored black\n",
    "        startVertex.color = 'black';\n",
    "        this.time++;\n",
    "        startVertex.finish = this.time;\n",
    "    }\n",
    "}    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Topological Sort\n",
    "* takes a directed ayclic graph and sorts it by vertices\n",
    "* so if you have a graph with an edge (v,w), then sort would have the ordering be v --> w\n",
    "* good if you have a graph with multiple steps and you want to find the right order of steps or for making schedules\n",
    "* algorithm:\n",
    "    1. call dfs on a graph to compute finish times\n",
    "    2. stores each vertex in a list in decreasing order of finish time\n",
    "        - so the first vertex to be fully explored (colored black) will be the one that is last in the list\n",
    "        - and the last vertex to be fully explored will be the first one in this list\n",
    "    3. return ordered list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Vertex {\n",
    "    constructor(key) {\n",
    "        this.id = key;\n",
    "        this.connectedTo = new Map();\n",
    "        this.dist = null;\n",
    "        this.predecessor = null;\n",
    "        this.colour = 'white';\n",
    "        this.disc = null;\n",
    "        this.fin = null;\n",
    "    }\n",
    "    \n",
    "    //adds a neighbor to this vertex\n",
    "    // weight is default 0 if unweighted\n",
    "    addNeighbor(nbr, weight = 0) {\n",
    "        this.connectedTo.set(nbr, weight);\n",
    "    }\n",
    "    \n",
    "    // returns list of connections to this vertex via the keys\n",
    "    // in the connectedTo object\n",
    "    getConnections() {\n",
    "        return this.connectedTo;\n",
    "    }\n",
    "    \n",
    "    getId() {\n",
    "        return this.id;\n",
    "    }\n",
    "    \n",
    "    // returns the weight of an edge between this node and a neighbor\n",
    "    getWeight(nbr) {\n",
    "        return this.connectedTo.get(nbr);\n",
    "    }\n",
    "    \n",
    "    get color() {\n",
    "        return this.colour;\n",
    "    }\n",
    "    \n",
    "    set color(value) {\n",
    "        this.colour = value;\n",
    "    }\n",
    "    \n",
    "    get distance() {\n",
    "        return this.dist;\n",
    "    }\n",
    "    \n",
    "    set distance(value) {\n",
    "        this.dist = value;\n",
    "    }\n",
    "    \n",
    "    get pred() {\n",
    "        return this.predecessor;\n",
    "    }\n",
    "    \n",
    "    set pred(value) {\n",
    "        this.predecessor = value;\n",
    "    }\n",
    "    \n",
    "    get discovery() {\n",
    "        return this.disc;\n",
    "    }\n",
    "    \n",
    "    set discovery(value) {\n",
    "        this.disc = value;\n",
    "    }\n",
    "    \n",
    "    get finish() {\n",
    "        return this.fin;\n",
    "    }\n",
    "    \n",
    "    set finish(value) {\n",
    "        this.fin = value;\n",
    "    }\n",
    "}\n",
    "\n",
    "class Graph {\n",
    "    constructor(){\n",
    "        this.vertList = new Map();\n",
    "        this.numVertices = 0;\n",
    "    }\n",
    "    \n",
    "    addVertex(key) {\n",
    "        this.numVertices++;\n",
    "        const newVertex = new Vertex(key);\n",
    "        this.vertList.set(key, newVertex);\n",
    "        return newVertex;\n",
    "    }\n",
    "    \n",
    "    getVertex(key) {\n",
    "        return this.vertList.has(key) ? this.vertList.get(key) : undefined;\n",
    "    }\n",
    "    \n",
    "    addEdge(from, to, weight = 0) {\n",
    "        if(! this.vertList.has(from) ) {\n",
    "            this.addVertex(from);\n",
    "        }\n",
    "        if(! this.vertList.has(to) ) {\n",
    "            this.addVertex(to);\n",
    "        }\n",
    "        this.vertList.get(from).addNeighbor(this.vertList.get(to), weight);\n",
    "    }\n",
    "    \n",
    "    getVertices() {\n",
    "        return this.vertList.keys();\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        for(let [key, value] of this.vertList) {\n",
    "            yield value;\n",
    "        };\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "}\n",
    "\n",
    "class DFSGraph extends Graph {\n",
    "    constructor() {\n",
    "        super();\n",
    "        this.time = 0;\n",
    "        this.topSortArray = [];\n",
    "    }\n",
    "    \n",
    "    dfs() {\n",
    "        for(let [key, vertex] of this.vertList) {\n",
    "            vertex.color = 'white';\n",
    "            vertex.pred = -1;\n",
    "        }\n",
    "        for(let [key, vertex] of this.vertList) {\n",
    "            if(vertex.color === 'white') {\n",
    "                this.dfsvisit(vertex);\n",
    "            } \n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // modified this for topological sort so that\n",
    "    // once a vertex has been fully explored, it will\n",
    "    // be put at the front of the topSortArray using unshift() method\n",
    "    // this ensures that finish times are in desc order\n",
    "    dfsvisit(startVertex) {\n",
    "        startVertex.color = 'gray';\n",
    "        this.time++;\n",
    "        startVertex.discovery = this.time;\n",
    "        for(let [nextVertex, value] of startVertex.getConnections()) {\n",
    "            if(nextVertex.color === 'white') {\n",
    "                nextVertex.pred = startVertex;\n",
    "                this.dfsvisit(nextVertex);\n",
    "            }\n",
    "        }\n",
    "        startVertex.color = 'black';\n",
    "        this.time++;\n",
    "        startVertex.finish = this.time;\n",
    "        this.topSortArray.unshift(startVertex); // happens here\n",
    "        // O(V) but could see a performance increase to O(1) if you use a stack\n",
    "    }\n",
    "    \n",
    "    // calls the function here\n",
    "    topSort() {\n",
    "        this.dfs();\n",
    "        // returns the order\n",
    "        return this.topSortArray;\n",
    "    }\n",
    "    \n",
    "    // probably the reason why we return a list of vertices in desc order of finish times\n",
    "    // is because the first item to be fully explored is the node that is the DEEPEST within its branch\n",
    "    // therefore, it will be the last step\n",
    "    // and the last item to be fully explored is the first node in the graph\n",
    "    // therefore, it will be the first step\n",
    "}    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Strongly Connected Components Algorithm\n",
    "* strongly connected component: a strongly connected component is a part of the graph where every pair of vertices (v, w) has a path from v --> w and w --> v\n",
    "* it is essentially a subgraph within a larger graph that has 1 node that connects to another scc\n",
    "* we will be making use of the reversed graph, GR\n",
    "    - this is where all the edges are reversed\n",
    "    - so if there is an edge from v --> w, then in GR, the edge is now from w --> v\n",
    "* Algorithm:\n",
    "    1. call dfs for the graph G to compute finish times for each vertex\n",
    "    2. compute GR\n",
    "    3. call dfs for GR but in the MAIN LOOP of DFS, explore each vertex in decreasing order of finish time\n",
    "    4. each tree in the forest computed in step 3 is a strongly connected component. just print the ids for each vertex in each tree in the forest\n",
    "* create a transposition of the graph:\n",
    "    1. iterate through the vertList of the grap you want to transpose\n",
    "    2. for each vertex, iterate through its adjacency list\n",
    "    3. for each neighbor in the adjacency list, add an edge from it to the currentVertex\n",
    "* Analysis:\n",
    "    - initial dfs over graph G is O(V + E)\n",
    "    - computing transposition of graph G to make GR is also O(V + E)\n",
    "    - and calling dfs for graph GR is also O(V + E)\n",
    "    - total is about O(V + E) to find SCC of a graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Vertex {\n",
    "    constructor(key) {\n",
    "        this.id = key;\n",
    "        this.connectedTo = new Map();\n",
    "        this.dist = null;\n",
    "        this.predecessor = null;\n",
    "        this.colour = 'white';\n",
    "        this.disc = null;\n",
    "        this.fin = null;\n",
    "    }\n",
    "    \n",
    "    //adds a neighbor to this vertex\n",
    "    // weight is default 0 if unweighted\n",
    "    addNeighbor(nbr, weight = 0) {\n",
    "//         this.connectedTo[nbr] = weight;\n",
    "        this.connectedTo.set(nbr, weight);\n",
    "    }\n",
    "    \n",
    "    // returns list of connections to this vertex via the keys\n",
    "    // in the connectedTo object\n",
    "    getConnections() {\n",
    "        return this.connectedTo;\n",
    "    }\n",
    "    \n",
    "    getId() {\n",
    "        return this.id;\n",
    "    }\n",
    "    \n",
    "    // returns the weight of an edge between this node and a neighbor\n",
    "    getWeight(nbr) {\n",
    "        return this.connectedTo.get(nbr);\n",
    "    }\n",
    "    \n",
    "    get color() {\n",
    "        return this.colour;\n",
    "    }\n",
    "    \n",
    "    set color(value) {\n",
    "        this.colour = value;\n",
    "    }\n",
    "    \n",
    "    get distance() {\n",
    "        return this.dist;\n",
    "    }\n",
    "    \n",
    "    set distance(value) {\n",
    "        this.dist = value;\n",
    "    }\n",
    "    \n",
    "    get pred() {\n",
    "        return this.predecessor;\n",
    "    }\n",
    "    \n",
    "    set pred(value) {\n",
    "        this.predecessor = value;\n",
    "    }\n",
    "    \n",
    "    get discovery() {\n",
    "        return this.disc;\n",
    "    }\n",
    "    \n",
    "    set discovery(value) {\n",
    "        this.disc = value;\n",
    "    }\n",
    "    \n",
    "    get finish() {\n",
    "        return this.fin;\n",
    "    }\n",
    "    \n",
    "    set finish(value) {\n",
    "        this.fin = value;\n",
    "    }\n",
    "}\n",
    "\n",
    "class Graph {\n",
    "    constructor(){\n",
    "        this.vertList = new Map();\n",
    "        this.numVertices = 0;\n",
    "        this.topSortArray = [];\n",
    "    }\n",
    "    \n",
    "    addVertex(key) {\n",
    "        this.numVertices++;\n",
    "        const newVertex = new Vertex(key);\n",
    "        this.vertList.set(key, newVertex);\n",
    "        return newVertex;\n",
    "    }\n",
    "    \n",
    "    getVertex(key) {\n",
    "        return this.vertList.has(key) ? this.vertList.get(key) : undefined;\n",
    "    }\n",
    "    \n",
    "    addEdge(from, to, weight = 0) {\n",
    "        if(! this.vertList.has(from) ) {\n",
    "            this.addVertex(from);\n",
    "        }\n",
    "        if(! this.vertList.has(to) ) {\n",
    "            this.addVertex(to);\n",
    "        }\n",
    "        this.vertList.get(from).addNeighbor(this.vertList.get(to), weight);\n",
    "    }\n",
    "    \n",
    "    getVertices() {\n",
    "        return this.vertList.keys();\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        for(let [key, value] of this.vertList) {\n",
    "            yield value;\n",
    "        };\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "}\n",
    "\n",
    "class DFSGraph extends Graph {\n",
    "    constructor() {\n",
    "        super();\n",
    "        this.time = 0;\n",
    "    }\n",
    "    \n",
    "    dfs() {\n",
    "        for(let [key, vertex] of this.vertList) {\n",
    "            vertex.color = 'white';\n",
    "            vertex.pred = -1;\n",
    "        }\n",
    "        \n",
    "        for(let [key, vertex] of this.vertList) {\n",
    "            if(vertex.color === 'white') {\n",
    "                this.dfsvisit(vertex);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // modified this for topological sort so that\n",
    "    // once a vertex has been fully explored, it will \n",
    "    // be put at the front of the topSortArray using unshift() method\n",
    "    // this ensures that finish times are then \n",
    "    dfsvisit(startVertex) {\n",
    "        startVertex.color = 'gray';\n",
    "        this.time++;\n",
    "        startVertex.discovery = this.time;\n",
    "        for(let [nextVertex, value] of startVertex.getConnections()) {\n",
    "            if(nextVertex.color === 'white') {\n",
    "                nextVertex.pred = startVertex;\n",
    "                this.dfsvisit(nextVertex);\n",
    "            }\n",
    "        }\n",
    "        startVertex.color = 'black';\n",
    "        this.time++;\n",
    "        startVertex.finish = this.time;\n",
    "        this.topSortArray.unshift(startVertex);\n",
    "    }\n",
    "    \n",
    "    topSort() {\n",
    "        this.dfs();\n",
    "        return this.topSortArray;\n",
    "    }\n",
    "    \n",
    "    printGraph() {\n",
    "        for(let [key, currentVertex] of this.vertList) {\n",
    "            console.log({key});\n",
    "            for(let [nbr, value] of currentVertex.getConnections()) {\n",
    "                console.log({nbr: nbr.id});\n",
    "            }\n",
    "            console.log('\\n');\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    printFinishTimes() {\n",
    "        this.topSortArray.forEach(el => {\n",
    "            console.log(el.fin);\n",
    "        })\n",
    "    }\n",
    "    \n",
    "    reverse() {\n",
    "        const RGraph = new DFSGraph();\n",
    "        for(let [key, currentVertex] of this.vertList) {\n",
    "            for(let [nbr, value] of currentVertex.getConnections()) {\n",
    "                RGraph.addEdge(nbr.id, key);\n",
    "            }\n",
    "        }\n",
    "        return RGraph;\n",
    "    }\n",
    "    \n",
    "    dfsSCC(RGraph){\n",
    "        for(let [key, vertex] of RGraph.vertList) {\n",
    "            vertex.color = 'white';\n",
    "            vertex.pred = -1;\n",
    "        }\n",
    "        \n",
    "        this.topSortArray.forEach(vertex => {\n",
    "            let RVertex = RGraph.getVertex(vertex.id);\n",
    "            if(RVertex.color === 'white') {\n",
    "                console.log({SCC: RVertex.id})\n",
    "                this.dfsvisitSCC(RVertex);\n",
    "            }\n",
    "        })\n",
    "    }\n",
    "    \n",
    "    dfsvisitSCC(startVertex) {\n",
    "        startVertex.color = 'gray';\n",
    "        for(let [nextVertex, value] of startVertex.getConnections()) {\n",
    "            if(nextVertex.color === 'white') {\n",
    "                console.log({components: nextVertex.id});\n",
    "                nextVertex.pred = startVertex;\n",
    "                this.dfsvisitSCC(nextVertex);\n",
    "            }\n",
    "        }\n",
    "        startVertex.color = 'black';\n",
    "        startVertex.finish = this.time;\n",
    "    }\n",
    "    \n",
    "    scc() {\n",
    "        this.dfs();\n",
    "        const reverse = this.reverse();\n",
    "        this.dfsSCC(reverse);\n",
    "        return;\n",
    "    }\n",
    " }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dijkstra's Algorithm\n",
    "* finds the shortet path from one starting node to every other node in the graph\n",
    "* similar to bfs\n",
    "* iterates through every vertex once in the graph but the iteration is base on a priority queue\n",
    "    - uses a min-heap that is sorted by DISTANCE\n",
    "    - so the node with the smallest distance from the starting node will be the first to be removed from the queue\n",
    "* implementation WITHOUT decreaseKey method in BinaryHeap\n",
    "    1. set startingnode.distance = 0, and every other node = Number.MAX_VALUE\n",
    "    2. initialize a min priority queue and add the starting node in\n",
    "    3. delete the minimum (first item in min pq) and iterate through its adjacent vertices\n",
    "    4. if the neighbor's current distance > currentVertex.distance + the weight between currentVertex and neighbor, then set neighbors distance to be currentVertex.distance + weight of edge between them\n",
    "    5. also set the predecessor of that neighbor to be currentVertex\n",
    "    6. and add that neighbor the priority queue where it might bubble to the top if it has a low enough distance\n",
    "    7. keep repeating these steps until the priority queue is empty\n",
    "* Analysis:\n",
    "    - deleting minimum takes O(log V) b/c have to restore heap order\n",
    "    - will iterate through every vertex and also every edge as well so it is O(V + E)\n",
    "    - total = O(V + E) * O(log V) = O((V + E)logV)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "function dijkstra(aGraph, start) {\n",
    "    // gives every node a distance of the largest num\n",
    "    for(let [key, vertex] of aGraph.vertList) {\n",
    "        vertex.distance = Number.MAX_VALUE;\n",
    "    }\n",
    "    // set's start to 0\n",
    "    start.distance = 0;\n",
    "    let pq = new BinHeap();\n",
    "    // adds start to min-pq\n",
    "    pq.buildHeap([start]);\n",
    "    \n",
    "    // while the pq is not empty\n",
    "    while(!pq.isEmpty()) {\n",
    "        // gets the currentVert from the pq which has the lowest dist\n",
    "        let currentVert = pq.delMin();\n",
    "        // for every neighboring node to it\n",
    "        // compare its new distance with its current distance\n",
    "        // whichever one is the smallest is now the nextVertex's distance\n",
    "        // set its predecessor to be the currentVertex\n",
    "        // then insert it into the pq where it might come to the top of the queue\n",
    "        // if it has a small distance\n",
    "        for(let [nextVert, weight] of currentVert.getConnections()) {\n",
    "            let newDist = currentVert.distance + weight;\n",
    "            if(newDist < nextVert.distance) {\n",
    "                nextVert.distance = newDist;\n",
    "                nextVert.pred = currentVert;\n",
    "                pq.insert(nextVert);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prim's Spanning Tree Algorithm\n",
    "* this algorithm solves problems where you want to reach all other locations from one location without having to travel too far\n",
    "* so given a router, i want my internet connection to be able to reach all people in my house efficiently\n",
    "* minimum weight spanning tree:\n",
    "    - a tree T for a graph G = (V, E) where T is acyclic\n",
    "    - and all edges connects all vertices in V\n",
    "    - such that the total weight between all edges is minimized\n",
    "* implementation: pretty similar to dijkstra's b/c uses pq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "function prim(aGraph, start) {\n",
    "    for(let [key,vertex] of aGraph.vertList) {\n",
    "        vertex.distance = Number.MAX_VALUE;\n",
    "    }\n",
    "    start.distance = 0;\n",
    "    let pq = new BinHeap();\n",
    "    let list = [start];\n",
    "    for(let [nextVert, nextWeight] of start.getConnections()) {\n",
    "        list.concat(nextVert);\n",
    "    }\n",
    "    pq.buildHeap(list);\n",
    "    \n",
    "    while(!pq.isEmpty()) {\n",
    "        let currentVert = pq.delMin();\n",
    "        for(let [nextVert, nextWeight] of currentVert.getConnections()) {\n",
    "            // if nbring vertex has not been visited and its weight \n",
    "            // is less than its current distance\n",
    "            // then set pred and distance\n",
    "            // add it to the pq\n",
    "            // then move on\n",
    "            if( (!nextVert.visited) && nextWeight < nextVert.distance ) {\n",
    "                nextVert.pred = currentVert;\n",
    "                nextVert.distance = nextWeight;\n",
    "                pq.insert(nextVert);\n",
    "                nextVert.visited = true;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bit Manipulation\n",
    "\n",
    "## Bits\n",
    "* bits can either be a 1 or a 0\n",
    "* there are 8 bits in 1 byte: so 1111 1111 = 8 bits = 1 byte\n",
    "* 1 byte can store 1 character, e.g. 'A' or 'x' or '#'\n",
    "* n bits yields 2^n different patterns of 1s and 0s\n",
    "    - 8 bits = 2^8 = 256 different numbers (0 -> 255)\n",
    "* bytes and characters\n",
    "    * ASCII = encoding representing each typed character as a number\n",
    "        - each number is stored in 1 byte (0 --> 255)\n",
    "        - ex: A is 65, B is 66, a is 97, and space = 32;\n",
    "        - can covnert A + 32 = a\n",
    "        - supports 128 characters only\n",
    "        - 7 bits to rep a character\n",
    "        - requires less space\n",
    "    * Unicode = encoding for mandarin, greek, arabic, etc\n",
    "        - typically 2-bytes (16-bit) per character but can usually use 8-bit or 32-bit as well\n",
    "        - requires more space\n",
    "        - can support a wide variety of characters for various languages\n",
    "* integers can be stored with either 4 or 8 bytes (32-bit or 64-bit)\n",
    "    - can calculate the amount of numbers for each by doing this equal: -2^(n - 1) --> 2^(n - 1) - 1\n",
    "    - so for 4 bytes (32-bits) it is: -2^(32 - 1) --> 2^(32-1) - 1\n",
    "    - positive integers have 1 less number b/c it also accounts for 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tricks\n",
    "\n",
    "### Represent a negative number using Two's Complement\n",
    "1. get binary representation of the absolute value of the number\n",
    "2. get the complement of the number\n",
    "3. add 1 to it\n",
    "\n",
    "***\n",
    "* for example: -3, assuming 4-bit number\n",
    "    1. |-3| = 3 = 0011;\n",
    "    2. ~(0011) = (1100);\n",
    "    3. 1100 + 1 = 1101 = -3\n",
    "***\n",
    "Another way to do it:\n",
    "    1. get absolute value of number\n",
    "    2. subtract by 1\n",
    "    3. get binary representation of it\n",
    "    4. negate it\n",
    "***\n",
    "* for example:\n",
    "    1. |-3| = 3\n",
    "    2. 3 - 1 = 2;\n",
    "    3. 2 = 0010\n",
    "    4. ~(0010) = 1101\n",
    "* this is equivalent to ~(Math.abs(n) - 1)\n",
    "\n",
    "### Bit Subtraction\n",
    "1. negate the subtractor\n",
    "2. add 1 to it\n",
    "3. add the two numbers together\n",
    "***\n",
    "* so if you have 3 - 1, you do 3 + (-1)\n",
    "    1. 1 = 0001\n",
    "    2. ~(0001) = 1100\n",
    "    3. 1110 + 1 = 1111\n",
    "    4. 0011 (3) + 1111 = 0010 (2) with extra bits discarded\n",
    "\n",
    "### JavaScript Representation\n",
    "* can type out binary numbers like this:\n",
    "    - let a = 0b11111111\n",
    "    - this is binary form of 255\n",
    "    - can also do octal and hex if you replace the b with an o or an x\n",
    "    - 0XFF = 255\n",
    "    - 0o377 = 255\n",
    "* toString(base): use this method to return a representation of a number according to the base you give it\n",
    "    - ex: let num = 255;\n",
    "    - num.toString(16) = ff which is hex\n",
    "    - num.toString(2) = 11111111 which is binary\n",
    "    - default = 10; can vary from 2 to 36 though"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bitwise Operators (simple)\n",
    "* bitwise operators treats operands as a sequence of 32 bits (4 bytes)\n",
    "* AND: a & b\n",
    "    - 1 & 1 = 1\n",
    "    - 1 & 0 = 0\n",
    "* OR: a | b\n",
    "    - 1 | 0 = 1\n",
    "* XOR: a ^ b\n",
    "    - 1 ^ 0 = 1\n",
    "    - 1 ^ 1 = 0\n",
    "    - 0 ^ 0 = 0\n",
    "* NOT: ~a\n",
    "    - ~(101) = 010"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bitwise Operators (shifting)\n",
    "* Left Shift: a << b\n",
    "    - a << b is essentially a * 2^b\n",
    "    - shifts all digits in binary representation of a to the left b number of times\n",
    "    - shifts in 0s from the right\n",
    "* Arithmetic Right Shift: a >> b\n",
    "    - a >> b is essentially a / 2^b\n",
    "    - shifts all digits in binary representation of a to the right b number of times\n",
    "    - shifts in 0s from the left\n",
    "    - keeps the sign of the number so if it is a negative number, it will still be negative, i.e. the most significant bit (sign bit) is carried over\n",
    "* Logical Right Shift: a >>> b\n",
    "    - shifts a to the right b number of times and shifts in 0s frm the left\n",
    "    - the difference between logical and arithmetic right shift is that the sign bit is not carried over\n",
    "    - the sign bit is instead replaced with a 0, so the result is always non-negative"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Common Bit Tasks (Get, Set, Clear, Update)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Get Bit: gets bit at the ith position\n",
    "1. left shift 1 by i to create a mask: 1 << i\n",
    "2. num & mask, then see if it is equal to 0\n",
    "    - the left shift moves 1 to the ith position. so if we have 1 << 4, then we have: 0000 1000;\n",
    "    - then when we num & mask, the ith bits are compared. then when we return whether that value is not equal to 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function getBit(num, i) {\n",
    "    let mask = 1 << i;\n",
    "    let value = num & mask;\n",
    "    //true = 1, false = 0\n",
    "    return value !== 0;\n",
    "}\n",
    "\n",
    "var a = 0b00010000; // 16\n",
    "getBit(a, 4);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Set Bit: sets bit at the ith position\n",
    "1. create a mask by left shifting 1 by i: 1 << i\n",
    "2. then we do num | mask\n",
    "    - setting = make the bit a 1 while clearing = make the bit a 0\n",
    "    - since 1 | any # is always gonna be 1, when we num | mask, we will keep other bits the same but the ith bit will always be 1 b/c the ith bit in the mask is 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "177\n",
      "true\n"
     ]
    }
   ],
   "source": [
    "function setBit(num, i) {\n",
    "    let mask = 1 << i;\n",
    "    return num | mask;\n",
    "}\n",
    "\n",
    "var a = 0b10100001; // 161\n",
    "var newA = setBit(a, 4);\n",
    "console.log(newA);\n",
    "console.log(getBit(newA, 4));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clear Bit:\n",
    "1. create a mask by left shifting 1 by i then getting its complement\n",
    "    - reason why we do this is b/c left shifting 1 will create something like this: 00010000 where there is only one 1 in the mask\n",
    "    - when we get the complement, we essentially have one 0 and all ones in the number: 11101111\n",
    "2. then we do num & mask\n",
    "    - with the complement, this essentially will clear the ith bit of num b/c the ith bit in the mask is 0 and the rest are 1s\n",
    "    - since the rest are 1s and we num & mask, the 1s in the num will be maintained so the num won't change besides that bit\n",
    "    - this is the only time we use the NOT (~) operator for clearing a bit. we will be using it for another operation though"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "161\n",
      "false\n"
     ]
    }
   ],
   "source": [
    "function clearBit(num, i) {\n",
    "    let mask = ~(1 << i);\n",
    "    return num & mask;\n",
    "}\n",
    "\n",
    "var a = 0b10110001; // 177;\n",
    "var newA = clearBit(a, 4);\n",
    "console.log(newA); // get 161 so it worked\n",
    "console.log(getBit(newA, 4)); // we get false = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clear Bit from Most Significant Bit (MSB) to i (inclusive):\n",
    "1. create a mask by left shifting 1 by i then subtracting it by 1\n",
    "    - when we subtract by 1, the bits from i - 1 --> 0 are turned into 1 whereas the bits from msb --> i are still 0s\n",
    "    - ex:\n",
    "        - if we have a mask 0001 0000 and we subtract by 1, we are essentially adding by -1\n",
    "        - 1111 1111 = -1\n",
    "        - thus when we add them together, we get 1 0000 1111\n",
    "        - the extra 1 on the left gets discarded so we have 0000 1111\n",
    "2. then we do num & mask which would clear bits from msb --> i and keep i - 1 --> 0 bits the same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "function clearMsbToI(num, i) {\n",
    "    let mask = (1 << i) - 1;\n",
    "    return num & mask;\n",
    "}\n",
    "\n",
    "var a = 0b11110000; // 240\n",
    "// we essentially cleared out those four 1s at the beginning\n",
    "// since those were the only bits that added any value, clearing them\n",
    "// made the number become 0\n",
    "var newA = clearMsbToI(a, 4);\n",
    "console.log(newA);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clear Bit from i to 0 (inclusive):\n",
    "1. create a mask by left shifting -1 by i + 1\n",
    "    - the reason why we want to use -1 is b/c -1 = 1111 1111\n",
    "    - when we left shift something, we move every bit to the left and shift a 0 from the right\n",
    "    - so in doing so, we essentially replace all 1s from i --> 0 with 0s\n",
    "    - for example, for i = 4, we left shift it by 5 times: 1111 1111 --> 1111 1110 --> 1111 1100 --> 1111 1000 --> 1111 0000 --> 1110 0000\n",
    "2. then we do num & mask which would mask bits from i --> 0 while keeping msb --> i + 1 the same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "function clearZeroToI(num, i) {\n",
    "    let mask = -1 << (i + 1);\n",
    "    return num & mask;\n",
    "}\n",
    "\n",
    "var a = 0b00011111; // 31\n",
    "// we essentially cleared out the five 1s here\n",
    "// since they were the only ones that had any value\n",
    "// clearing them out turned the number to 0\n",
    "var newA = clearZeroToI(a, 4);\n",
    "console.log(newA);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Update Bit: update the bit at ith position with a given value\n",
    "1. clear the bit at i\n",
    "    - create mask by left shifting 1 by i then getting its complement\n",
    "    - then you do num &= mask so that it clears the ith bit in num\n",
    "2. then you create another mask by shifting the given value by i\n",
    "3. then you do num | value mask\n",
    "    - so if the value bit is 0, then the num will stay 0 since it was cleared\n",
    "    - if the value bit is 1, we know that 1 | 0 = 1, so it'll be set\n",
    "***\n",
    "* in essence, updating a bit is essentially just 2 compounded steps\n",
    "* you clear the bit at i\n",
    "* you set the bit at i but using a mask created by left shifting the given value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "32\n",
      "239\n"
     ]
    }
   ],
   "source": [
    "function updateBit(num, i, bitIs1) {\n",
    "    let value = bitIs1 ? 1 : 0;\n",
    "    let mask = ~(1 << i);\n",
    "    num &= mask;\n",
    "    value <<= i;\n",
    "    return num | value;\n",
    "}\n",
    "\n",
    "var a = 0b00000000;\n",
    "// updating bit at the 5th pos with a 1\n",
    "// since our original value is 0, the 5th bit will be the only one\n",
    "// providing it value\n",
    "// 2 ^ 5 = 32\n",
    "var newA = updateBit(a, 5, 1);\n",
    "console.log(newA);\n",
    "\n",
    "var b = 0b11111111; // 255\n",
    "// clearing the 4th bit from b is like subtracting 16 from it\n",
    "var newB = updateBit(b, 4, 0);\n",
    "console.log(newB);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Common Bit Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Powers of 2\n",
    "1. create a mask by doing x - 1 where x = number we want to evaluate\n",
    "2. then we do x &= mask\n",
    "3. then we see if x is equal to 0\n",
    "    - if it is, return true\n",
    "    - else, it is not a power of 2\n",
    "***\n",
    "* any binary number that is a power of 2 will only have one 1 bit in it\n",
    "    - for example 4 = 0100\n",
    "    - 6 = 0110, which has two 1 bits inside it and is clearly not a power of 2\n",
    "* using this knowledge, we can then assume that the number we are trying to evaluate, x, has only 1 bit in it\n",
    "    - thus when we create a mask using x - 1, we essentially flip every bit to the right of the rightmost 1-bit, including itself\n",
    "    - so if we have 4 = 0100, 3 = 0011, then when we do x & mask, we clear all bits from the rightmost 1-bit to the 0th position\n",
    "* we then compare x to 0. with our assumption, once we do x & mask and x is a power of 2, then the only bit that gives the binary sequence any value is the rightmost 1-bit.\n",
    "    - since we cleared the only 1-bit out, then the binary sequence should return 0\n",
    "    - if it returns a non-zero number, we know that there is more than one 1-bit in the original sequence, and can therefore not be a power of 2\n",
    "* Analysis:\n",
    "    - complexity should be equal to the number of bits in x\n",
    "    - space complexity is O(1), we don't use any large data structure to hold any information"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false\n",
      "true\n"
     ]
    }
   ],
   "source": [
    "function isPowerOfTwo(x) {\n",
    "    return (x & (x - 1)) === 0;\n",
    "}\n",
    "\n",
    "console.log(isPowerOfTwo(65));\n",
    "console.log(isPowerOfTwo(128));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Count the Number of Ones in the Binary Representation of the Given Number\n",
    "1. while n !== 0\n",
    "2. create a mask by doing n - 1\n",
    "3. then update n to be n &= mask\n",
    "4. increment the count\n",
    "***\n",
    "* this uses the same concept as the power of 2 algorithm\n",
    "* what we are doing is flipping every bit from the rightmost 1-bit in n to the 0th position\n",
    "* then when we & the n and the mask, we clearn that bit\n",
    "* we keep doing this until we have cleared all the 1-bits from the original number n and we increment the number of times we do this and return it\n",
    "* Analysis:\n",
    "    - time complexity should be about O(k), where k - number of ones present in the binary form of the given number\n",
    "    - space complexity is also O(1)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "function countOnes(n) {\n",
    "    let count = 0;\n",
    "    while(n !== 0) {\n",
    "        n &= n - 1;\n",
    "        count++;\n",
    "    }\n",
    "    return count;\n",
    "}\n",
    "\n",
    "var num = 0b11111111;\n",
    "console.log(countOnes(num));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Generate All Possible Subsets of a Set\n",
    "* THIS ALGORITHM IS BASICALLY JUST READING FLAGS\n",
    "    - for example: if we have a set {a, b, c, d} then each of these represents a bit position in a number\n",
    "    - so if we have the number 1111, then the set would be {a, b, c, d} b/c all the bits have been set\n",
    "    - 1111 = 15. there are 16 subsets in this set b/c it is 2^4 where set.length = 4;\n",
    "    - another example would be 1011 = 11 and represents the set {a, b, d}\n",
    "    - so in essence, we iterate through every number until we reach the number of possible subsets and each number in binary form represents a sequence of flags that will tell us if a particular element in our set is present\n",
    "* in the for-loop, the reason why we do i < (1 << n) is b/c 1 << nrepresents the number of possible subsets for a given set\n",
    "    - remember that for any set with n length, there are 2^n subsets\n",
    "    - so when we take the length of the set and then we shift 1 by n, we are essentially doing the same thing\n",
    "    - left shifting is similar to multiplying by 2, so if we left shift 1 by n, we are basically doing 1 * 2^n\n",
    "* the second for-loop iterates through every bit in the current numober of the first for-loop\n",
    "    - it then checks whether that bit is set or not\n",
    "    - remember that getBit = num & ( 1 << i ) where i = bit position we want\n",
    "    - so if that particular bit position, j is set, then we also display that element at set[j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{ \n",
      "}\n",
      "\n",
      "{ \n",
      "a \n",
      "}\n",
      "\n",
      "{ \n",
      "b \n",
      "}\n",
      "\n",
      "{ \n",
      "a \n",
      "b \n",
      "}\n",
      "\n",
      "{ \n",
      "c \n",
      "}\n",
      "\n",
      "{ \n",
      "a \n",
      "c \n",
      "}\n",
      "\n",
      "{ \n",
      "b \n",
      "c \n",
      "}\n",
      "\n",
      "{ \n",
      "a \n",
      "b \n",
      "c \n",
      "}\n",
      "\n"
     ]
    }
   ],
   "source": [
    "function possibleSets(set) {\n",
    "    let n = set.length;\n",
    "    \n",
    "    // for let i < number of possible subsets\n",
    "    for(let i = 0; i < (1 << n); i++) {\n",
    "        console.log('{ ');\n",
    "        \n",
    "        // if flag has been set in our current number, i, at pos j\n",
    "        // display set[j]\n",
    "        \n",
    "        for(let j = 0; j < n; j++) {\n",
    "            // gets the bit here\n",
    "            // by making a mask with 1 << j\n",
    "            // then num & mask to get the bit at jth position\n",
    "            if( (i & (1 << j) ) > 0) {\n",
    "                console.log(set[j] + ' ');\n",
    "            }\n",
    "        }\n",
    "        console.log(\"}\\n\");\n",
    "    }\n",
    "}\n",
    "\n",
    "possibleSets(['a', 'b', 'c'])\n",
    "\n",
    "//do remember that the empty set is also a subset\n",
    "// this applies for everything, even for graphs\n",
    "// so the empty graph is also a subgraph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Find the Largest Power of 2 that is Less Than or Equal To the Given Number N\n",
    "* essentially, we round the number up to the next nearest power of 2.\n",
    "* then we add 1 to the number and right shift it by 1 position which is basically dividing the number by 2\n",
    "* for our example, we just 14, which is 1110 and then we do bitwise OR with its right-shifted version by 1\n",
    "    - so 1110 | 0111 = 1111\n",
    "    - all of its bits are now 1 so we get 15\n",
    "    - then we do 15 + 1 = 16 which is the next nearest power of 2\n",
    "    - then we do a right shift: (15 + 1) >> 1 which is just 16 / 2\n",
    "    - and the nearest power of 2 is 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{ n: '1111' }\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function largestPower(n) {\n",
    "    // doing all these ensures that 32 bit ints are covered\n",
    "    n |= n >> 1;\n",
    "    n |= n >> 2;\n",
    "    n |= n >> 4;\n",
    "    n |= n >> 8;\n",
    "    console.log({n : n.toString(2)});\n",
    "    return (n + 1) >> 1;\n",
    "}\n",
    "\n",
    "largestPower(14);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Alternate Way:\n",
    "* we essentially use the same logic as counting the number of 1-bits in the binary sequence\n",
    "* we eliminate the rightmost bit until the original number is 0\n",
    "    - but we keep the value of the number before it reaches 0\n",
    "    - that is what x is for\n",
    "* this one is a little bit faster but only by less than 1%"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{ x: 14 }\n",
      "{ x: 12 }\n",
      "{ x: 8 }\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function largestPowerAlt(n) {\n",
    "    let x;\n",
    "    while(n !== 0) {\n",
    "        x = n;\n",
    "        console.log({x});\n",
    "        n &= (n - 1);\n",
    "    }\n",
    "    return x;\n",
    "}\n",
    "\n",
    "largestPowerAlt(14);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Highest Power of 2 that Divides a Given Number\n",
    "* basically, you're just isolating the rightmost bit of the number and returning it\n",
    "* you can get the rightmost bit by doing:\n",
    "    1. x ^ (x & (x - 1)\n",
    "    2. x & (-x) which is basically what the function is doing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11000000\n",
      "10111111\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "64"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function highestPowerOf2(n) {\n",
    "    let mask = -(n - 1);\n",
    "    console.log(n.toString(2));\n",
    "    console.log((n - 1).toString(2));\n",
    "    return n & mask;\n",
    "}\n",
    "\n",
    "// 192 = 11000000\n",
    "// 191 = 10111111\n",
    "//-191 = 01000000\n",
    "// 192 & 191 = 01000000 = 64\n",
    "highestPowerOf2(192);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 10 Sorting and Searching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search\n",
    "* only works on ordered lists\n",
    "* algorithm:\n",
    "    1. examine the middle item\n",
    "    2. if it is larger than what we are looking for then check arr.slice(0, middleIndex);\n",
    "    3. else, check arr.slice(middleIndex + 1, arr.length);\n",
    "\n",
    "***\n",
    "Analysis:\n",
    "* time complexity: O(log n)\n",
    "    - b/c the algorithm continually splits the array in half every time the item isn't found\n",
    "* space complexity: O(log n) for a recursive approach but is O(1) for an iterative approach\n",
    "    - this is b/c recursive calls get pushed onto a stack and there are going to be log n function calls on the stack\n",
    "    - iterative approach does not implicitly use a stack so just O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// recursive approach\n",
    "\n",
    "function binarySearch(item, arr) {\n",
    "    return _binarySearch(item, arr, 0, arr.length - 1);\n",
    "}\n",
    "\n",
    "function _binarySearch(item, arr, start, end) {\n",
    "    // to prevent int overflow\n",
    "    let mid = Math.trunc(start + ((end - start) / 2));\n",
    "    if(end < start) {\n",
    "        return -1;\n",
    "    }\n",
    "    if(arr[mid] === item) {\n",
    "        return true;\n",
    "    }\n",
    "    else if (arr[mid] > item) {\n",
    "        return _binarySearch(item, arr, start, mid - 1);\n",
    "    }\n",
    "    else {\n",
    "        return _binarySearch(item, arr, mid + 1, end);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bubble Sort\n",
    "* Algorithm:\n",
    "    1. start at the beginning of the list\n",
    "    2. if the current item is larger than the next item, then switch places\n",
    "    3. else, move onto the next item in the list\n",
    "    4. continue doing this until all items are sorted\n",
    "\n",
    "***\n",
    "Analysis:\n",
    "* time complexity: O(n^2)\n",
    "    - this is b/c there will be n - 1 passes through the list to completely sort a list of size n\n",
    "    - and for each pass, there are n - 1 comparisons to be made\n",
    "* space complexity: O(1)\n",
    "\n",
    "***\n",
    "Short Bubble Sort:\n",
    "* variation on bubble sort\n",
    "* allows the algorithm to stop eary if the arr is already sorted\n",
    "    - it can stop early unlike other sorting algorithms which can be an advantage\n",
    "\n",
    "***\n",
    "* think of it like bubbling up so you have to start from the end of the array and comparing arr[j] and arr[j + 1]\n",
    "* easier that way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[\n",
      "  1,  3,  4,  5,  6,\n",
      "  7, 14, 16, 19, 20\n",
      "]\n"
     ]
    }
   ],
   "source": [
    "// starts from back --> front\n",
    "function bubbleSort(arr) {\n",
    "    for(let i = arr.length - 1; i >= 0; i--) {\n",
    "        for(let j = 0; j < i; j++) {\n",
    "            if(arr[j] > arr[j + 1]) {\n",
    "                // destructuring assignment\n",
    "                // that allows for swapping of values\n",
    "                // without a temp variable\n",
    "                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    return arr;\n",
    "}\n",
    "\n",
    "var set = [3, 7, 14, 6, 20, 1, 19, 16, 5, 4];\n",
    "console.log(bubbleSort(set));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "function shortBubbleSort(arr) {\n",
    "    let unsorted = true;\n",
    "    let passesRemaining = arr.length - 1;\n",
    "    \n",
    "    // since we are using a while loop, we need to have\n",
    "    // the passesRemaining to count down like in\n",
    "    // the for loop in regular bubble sort\n",
    "    while(passesRemaining > 0 && unsorted) {\n",
    "        // set this to false\n",
    "        // and if there are no exchanges made, then we\n",
    "        // can assume that the list is already sorted\n",
    "        unsorted = false;\n",
    "        for(let j = 0; j < passesRemaining; j++) {\n",
    "            // if there is ever an exchange, the list is still\n",
    "            // unsorted\n",
    "            if(arr[j] > arr[j + 1]) {\n",
    "                unsorted = true;\n",
    "                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];\n",
    "            }\n",
    "        }\n",
    "        passesRemaining--;\n",
    "    }\n",
    "    return arr;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Selection Sort\n",
    "* similar to selection sort except you make 1 exchange every sort\n",
    "* Algorithm:\n",
    "    1. start index n - 1 (our i value)\n",
    "    2. have a pointer pass through the entire list from 0 --> i\n",
    "    3. if the pointer is placed on an item larger than the current max, then keep track of the pos of the max\n",
    "    4. keep doing this for every index until you reach the ith index and then swap value at i and max\n",
    "\n",
    "***\n",
    "Analysis:\n",
    "* time complexity: O(n^2)\n",
    "    - exactly the same as bubble sort b/c has the same number of passes and the same number of comparisons per pass\n",
    "    - in practice, this sort will be faster than bubble sort due to the smaller number of exchanges\n",
    "* space complexity: O(1)\n",
    "\n",
    "***\n",
    "* it's like sorting through your hand of cards\n",
    "* you make several passes through the entire thing and keep track of the highest and you place it at the spot you want rather than make exchanges along the way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "function selectionSort(arr) {\n",
    "    // this for loop decrements from last index to 0\n",
    "    for(let i = arr.length - 1; i > 0; i--) {\n",
    "        let posMax = 0;\n",
    "        /*\n",
    "            * this for loop moves from 0 --> i to check for max\n",
    "            * reason for j < i + 1 b/c there is a possibility that the arr[i]\n",
    "            is the max for that pass so need to check that too!\n",
    "        */\n",
    "        for(let j = 0; j < i + 1; j++) {\n",
    "            if(arr[j] > arr[posMax]) {\n",
    "                posMax = j;\n",
    "            }\n",
    "        }\n",
    "        [arr[i], arr[posMax]] = [arr[posMax], arr[i]];\n",
    "    }\n",
    "    return arr;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Insertion Sort\n",
    "* has a sublist of sorted elements at the beginning of the list and any new items are then inserted into this list\n",
    "* Algorithm:\n",
    "    1. assume index 0 is already sorted and start with a pointer at index 1\n",
    "    2. you then comparse the value at the pointer and move backwards until you reach 0\n",
    "    3. if the value of the previous values are greater than the one at the pointer, then shift the previous ones up\n",
    "    4. if the value of the previous is less than the one at the pointer, then put the pointer values at that position\n",
    "* so essentially, you only move the pointer one at a time and you insert the value at the pointer in the correct spot in the values before it\n",
    "    - so if you're at index 10, then indices at 0 --> 9 are already sorted\n",
    "    - you just shif the values at those indices up until you find the right position for the current value\n",
    "\n",
    "***\n",
    "Analysis:\n",
    "* time complexity: O(n^2)\n",
    "    - there are n - 1 passes to sort n items\n",
    "    - and there are going to be n - 1 comparisons\n",
    "* space complexity: O(1)\n",
    "* since you only perform one exchange at the end of each pass and shifts are about 1/3 of the work of exchanges, it will have good performance on benchmarks compared to bubble sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "function insertionSort(arr) {\n",
    "    // assumes i = 0 is already sorted\n",
    "    // so starts at i = 1\n",
    "    for(let i = 1; i < arr.length; i++) {\n",
    "        // saves currentValue to do the exchange later\n",
    "        let currentValue = arr[i];\n",
    "        let position = i;\n",
    "        \n",
    "        // this loop finds the position to place the currentValue into\n",
    "        // if we have found the right spot for the current value\n",
    "        // then exit the loop\n",
    "        while(position > 0 && arr[position - 1] > currentValue) {\n",
    "            // shifts the larger item to the right\n",
    "            // since we already have a var to keep track of the\n",
    "            // value at i, we can just override the current position\n",
    "            arr[position] = arr[position - 1];\n",
    "            position--;\n",
    "        }\n",
    "        \n",
    "        arr[position] = currentValue;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shell Sort\n",
    "* improvement on insertion sort by breaking list into smaller sublists\n",
    "* sublists are not contiguous and instead rely on a gap to create a sublist that are a certain value apart\n",
    "* Algorithm:\n",
    "    1. start at index 0\n",
    "    2. figure out the gap that you want to create the sublist\n",
    "        - in this case, we halve the length of the arr until gap is 1\n",
    "        - so if arr.length = 10, then gap = 5, 2, then 1\n",
    "    3. then do an insertion sort with gaps\n",
    "        - normal insertion sort is just gap of 1 for every pass\n",
    "        - but with shellSort, you have large gaps then progressively smaller gaps until the whole list is sorted\n",
    "\n",
    "***\n",
    "Analysis:\n",
    "* time complexity: between O(n) and O(n^2)\n",
    "    - this is b/c the list progressively gets sorted every time and every pass gets more and more efficient\n",
    "    - the gap used is also an indicator on how efficient it is\n",
    "        - with the gap halving every time, it tends to be O(n^2)\n",
    "        - with a gap that uses 2^(k - 1) formula, then it can be at O(n ^ (3/2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "function shellSort(arr) {\n",
    "    // first gap of arr.length / 2\n",
    "    let sublistCount = Math.trunc(arr.length / 2);\n",
    "    \n",
    "    while(sublistCount > 0) {\n",
    "        // the i is used as the start index for gapInsertionSort\n",
    "        // and we use sublistCount as the gap\n",
    "        // the gap doesn't change in this for loop\n",
    "        for(let i = 0; i < sublistCount; i++) {\n",
    "            gapInsertionSort(arr, i, sublistCount);\n",
    "        }\n",
    "        console.log(`After incremenets of size ${sublistCount}, the list is ${arr}`);\n",
    "        sublistcount = Math.trunc(sublistCount / 2);\n",
    "    }\n",
    "    return arr;\n",
    "}\n",
    "\n",
    "function gapInsertionSort(arr, start, gap) {\n",
    "    for(let i = start + gap; i < arr.length; i += gap) {\n",
    "        let currentValue = arr[i];\n",
    "        let position = i;\n",
    "        \n",
    "        while(position >= gap && arr[position - gap] > currentValue) {\n",
    "            arr[position] = arr[position - gap];\n",
    "            position -= gap;\n",
    "        }\n",
    "        \n",
    "        arr[position] = currentValue;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge Sort\n",
    "* continually splits the array in half until the subarrays are empty or has 1 item in it (base case)\n",
    "* then once the halves are sorted, they are merged together to create a larger sorted array\n",
    "* Algorithm:\n",
    "    1. base case: if the length of the list is 0 or 1, then do nothing\n",
    "    2. if the list length > 2, then split the list into two halves: leftHalf and rightHalf\n",
    "    3. recurse on those halves until they are split into subarrays of length 1 or 0\n",
    "    4. then once your two halves are small enough, merge them together\n",
    "        - compare the leftHalf and rightHalf and put the smaller value from both into the list\n",
    "        - increment the index of the half that you got the value from\n",
    "        - then when one of the halves is empty, add the rest of that half into the original list\n",
    "    5. keep repeating until the whole list is sorted\n",
    "\n",
    "***\n",
    "Analysis:\n",
    "* time complexity: O(nlogn)\n",
    "    - the first process continually splits the list in half until it has a length of 0 or 1. this is O(log n)\n",
    "    - the second process merges the two halves together. since it will have to process n elements, i.e. compare elements of the two halves to put into the original list, this is O(n)\n",
    "    - since the merge happens for every split and there are log n splits\n",
    "* space complexity: O(n)\n",
    "    - this is b/c you need space to store the two halves of the array every time it is split\n",
    "    - it is not O(nlogn) space b/c you recurse on the leftHalf first THEN the rightHalf and you never do this in parallel. so by the time you start recursing on the rightHalf, your leftHalf function calls will have returned\n",
    "    - there's also O(log n) function calls in the stack but it's not the dominant term so we remove it\n",
    "* this particular implementation uses the slice operator so there is an O(k) added onto the time complexity as well but this can be removed if we just used pointers and did everything in place"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "function mergeSort(list) {\n",
    "    if(list.length > 1) {\n",
    "        let mid = Math.trunc(list.length / 2);\n",
    "        let leftHalf = list.slice(0, mid);\n",
    "        let rightHalf = list.slice(mid);\n",
    "        \n",
    "        mergeSort(leftHalf);\n",
    "        mergeSort(rightHalf);\n",
    "        \n",
    "        merge(list, leftHalf, rightHalf);\n",
    "    }\n",
    "    return;\n",
    "}\n",
    "\n",
    "function merge(list, leftHalf, rightHalf) {\n",
    "    let leftIndex = 0;\n",
    "    let rightIndex = 0;\n",
    "    let listIndex = 0;\n",
    "    \n",
    "    // compares items from both halves and puts the smallest\n",
    "    // one into the original list\n",
    "    // then we increment the index of the half that we took the\n",
    "    // smaller value from\n",
    "    while(leftIndex < leftHalf.length && rightIndex < rightHalf.length) {\n",
    "        // the <= makes the algorithm stable\n",
    "        // to account for duplicates\n",
    "        if(leftHalf[leftIndex] <= rightHalf[rightIndex]) {\n",
    "            list[listIndex] = leftHalf[leftIndex];\n",
    "            leftIndex++;\n",
    "        }\n",
    "        else {\n",
    "            list[listIndex] = rightHalf[rightIndex];\n",
    "            rightIndex++;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // if we go through all of the elements in the rightHalf\n",
    "    // then add remaining values from the leftHalf\n",
    "    while(leftIndex < leftHalf.length) {\n",
    "        list[listIndex] = leftHalf[leftIndex];\n",
    "        leftIndex++;\n",
    "        listIndex++;\n",
    "    }\n",
    "    \n",
    "    // if we go through all of the elements in the leftHalf\n",
    "    // then add remaining values from the rightHalf\n",
    "    while(rightIndex < rightHalf.length) {\n",
    "        list[listIndex] = rightHalf[rightIndex];\n",
    "        rightIndex++;\n",
    "        listIndex++;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quick Sort\n",
    "* Algorithm:\n",
    "    1. selects a value called the pivot that helps to split the list\n",
    "        - when the list is sorted, the pivot is placed at a split point which divides the list for subsequent calls\n",
    "        - many ways to pick pivot but simplest is to pick first element in the list\n",
    "    2. then the list is partitioned via the pivot\n",
    "        - element < pivot = left side\n",
    "        - element > pivot = right side\n",
    "        - use of 2 pointers called leftmark and rightmark\n",
    "        - if the leftmark > pivot, then we stop it there\n",
    "        - and if the rightmark < pivot, then we stop it there and we switch the values at the leftmark and rightmark\n",
    "        - else, leftmark increments by 1 and rightmark decrements by 1\n",
    "        - when rightmark index < leftmark, we stop and the rightmark is now the split point to place the pivot at\n",
    "    3. the split point will divide the list into 2 halves and we call quicksort on both of them to sort them out\n",
    "        - so the leftHalf = arr.slice(0, splitPoint)\n",
    "        - rightHalf = arr.slice(splitPoint + 1)\n",
    "\n",
    "***\n",
    "Analysis:\n",
    "* time complexity: O(nlogn)\n",
    "    - partition will always split the list in half so there are log n divisions\n",
    "    - finding the split point requires that all the items in the list be checked so that's O(n)\n",
    "* space complexity: O(log n)\n",
    "    - b/c there are log n function calls on the stack due to quicksort being implemented recursively\n",
    "* worse case scenario: O(n^2) time complexity\n",
    "    - this is the case where the chosen pivot does not split the list in half evenly and in fact skews the list to one side\n",
    "    - usually the case when the list is already sorted and you pick one of the elements on the edges\n",
    "* to minimize the risk of quickSort degrading to O(n^2), you can use the Median of Three method:\n",
    "    - pick 3 random indices in the array and choose the median value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "function quickSort(arr) {\n",
    "    return quickSortHelper(arr, 0, arr.length - 1);\n",
    "}\n",
    "\n",
    "function quickSortHelper(arr, first, last) {\n",
    "    if(first < last) {\n",
    "        let splitpoint = partition(arr, first, last);\n",
    "        \n",
    "        quickSortHelper(arr, first, splitpoint - 1);\n",
    "        quickSortHelper(arr, splitpoint + 1, last);\n",
    "    }\n",
    "    return arr;\n",
    "}\n",
    "\n",
    "function partition(arr, first, last) {\n",
    "    // pick pivot value\n",
    "    let pivot = arr[first];\n",
    "    \n",
    "    let leftmark = first + 1;\n",
    "    let rightmark = last;\n",
    "    \n",
    "    let done = false;\n",
    "    \n",
    "    while(!done) {\n",
    "        \n",
    "        // will run until finds a value where leftmark > pivot\n",
    "        // and when leftmark and rightmark haven't crossed\n",
    "        while(leftmark <= rightmark && arr[leftmark] <= pivot) {\n",
    "            leftmark++;\n",
    "        }\n",
    "        \n",
    "        // will run until finds a value where rightmark < pivot\n",
    "        // and when rightmark and leftmark haven't crossed\n",
    "        \n",
    "        while(arr[rightmark] >= pivot && rightmark >= leftmark) {\n",
    "            rightmark--;\n",
    "        }\n",
    "        \n",
    "        // if the two indices have crossed\n",
    "        // then the split point is found\n",
    "        if(rightmark < leftmark) {\n",
    "            done = true;\n",
    "        }\n",
    "        else {\n",
    "            [arr[leftmark], arr[rightmark]] = [arr[rightmark], arr[leftmark]];\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // once the split point is found\n",
    "    // we switch the pivot with the rightmark index\n",
    "    [arr[first], arr[rightmark]] = [arr[rightmark], arr[first]];\n",
    "    \n",
    "    // and we return the splitpoint, which\n",
    "    // is the rightmark index;\n",
    "    return rightmark;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Counting Sort\n",
    "* assume there is some number, k, where each element <= k\n",
    "* when k = O(n) we have a $\\theta$(n) sorting\n",
    "* will have 3 arrays:\n",
    "    1. input arra\n",
    "    2. storage array to store # of occurrences of each value from input array\n",
    "    3. output array\n",
    "* Algorithm:\n",
    "    1. create the storage array with length = k + 1, and fill it up with 0s\n",
    "        - so if k = 5, storage array = [0, 0, 0, 0, 0]\n",
    "    2. go through the input array and keep track of number of occurrences of each value\n",
    "        - input array = [2, 5, 3, 0, 2, 3, 0, 3]\n",
    "        - storage array would be: [2, 0, 2, 3, 0, 1]\n",
    "            - two 0s\n",
    "            - zero 1s\n",
    "            - two 2s\n",
    "            - three 3s\n",
    "            - zero 4s\n",
    "            - one 5\n",
    "        - essentially, each index in the storage array represents a value in the input array and we count the number of times that value appears in the input\n",
    "        - so storage_array[5] = 1 means that tere is one 5 in the input array\n",
    "    3. then we fill in the output array\n",
    "        - keep track of index for storage array starting at 0\n",
    "        - for each position in output array, we put in the storage array index if storage_array[index] > 0\n",
    "            - this is b/c we know that there must be at least 1 occurrence of the storage array index in the input value\n",
    "            - then once we add it in, we decrement value at storage_array[index]\n",
    "        - if storage_array[index] = 0, we know there are no more occurrences of index in the output array so we move on\n",
    "        - example: storage_array = [2, 0, 2, 3, 0, 1]\n",
    "            - output = []\n",
    "            - starting at index 0 for both, we see that storage_array[0] = 2, meaning there are 2 occurrences of the value 0 in the input array\n",
    "            - so we put them both into output: output = [0, 0]\n",
    "            - and we decrement the value at storage_array for each time we put it in, so storage_array[0] = 0\n",
    "            - since it is now at 0, we move to storage_array[1], which also happens to be 0, so we move onto storage_array[2]\n",
    "            - we see that storage_array[2] = 2 so there are 2 occurrences of the value 2 in the input array\n",
    "            - so output is now going to be: [0, 0, 2, 2]\n",
    "            - keep doing this until we reach the end of the output array\n",
    "\n",
    "***\n",
    "Analysis:\n",
    "* time complexity: O(n + k)\n",
    "    - n = number of items in the input array\n",
    "    - k = maximum int. value found in the input array\n",
    "    - when we fill up the tempArray, it takes O(k) time b/c each index represents a value that might be found in the input array\n",
    "    - keeping track of number of occurrences of each value in input array = O(n) b/c we iterate through n items\n",
    "    - filling up the array, in my version, takes O(n + k) b/c we have to find the index in k that has a non-zero value and we do this for every position in output array which is equal to n\n",
    "* space complexity: O(n + k)\n",
    "    - there are n elements in the input array\n",
    "    - and our storage array has k elements, where k = largest int. value in input array\n",
    "* counting sort = STABLE\n",
    "    - this means that duplicate values in input array are put in the same order in output array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "function countingSort(input, largestInt) {\n",
    "    let output = [];\n",
    "    \n",
    "    // filsl up tempArr with 0s\n",
    "    // where tempArr.length = largest integer value in the input array\n",
    "    // so if largestInt = 20, then tempArr.length = 21\n",
    "    // and tempArr[0:20] = 0;\n",
    "    let tempArr = new Array(largestInt + 1).fill(0);\n",
    "    \n",
    "    // goes through the input array and tracks # of occurrences of a value\n",
    "    // so if 2 occurs three times in input\n",
    "    // then tempArr[2] = 3;\n",
    "    input.forEach(num => tempArr[num]++);\n",
    "    \n",
    "    /*\n",
    "        my version:\n",
    "        start from the 0th index on both output and tempArr\n",
    "        at the 0th index, we look at the first value in tempArr that is not 0\n",
    "        so if tempArr = [2, 0, 2, 3, 0, 1] then index 0 has a 2 in it\n",
    "        which means there are two 0s that should be in the output\n",
    "        thus output[0] = 0 and output[1] = 0;\n",
    "        afterwards, we decrement tempArr[0] every time we insert into output\n",
    "        once tempArr[0] = 0, we know there aren't anymore 0s left in the output\n",
    "        so we move to tempArr[1]. we see that tempArr[1] = 0, so we move to tempArr[2] and so on\n",
    "        until we reach tempArr[largestInt] which is the end\n",
    "    */\n",
    "    let tempIndex = 0;\n",
    "    \n",
    "    for(let i = 0; i < input.length; i++) {\n",
    "        while(tempArr[tempIndex] === 0) {\n",
    "            tempIndex++;\n",
    "        }\n",
    "        output[i] = tempIndex;\n",
    "        tempArr[tempIndex]--;\n",
    "    }\n",
    "    \n",
    "    return output;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Radix Sort\n",
    "* starts from the least significantdigit and sorts its way up\n",
    "    - for example: 123, starts at 3, then 2, then 1\n",
    "* requires a STABLE sorting algorithm, like counting sort, as a subroutine b/c as you move from least significant to most significant digit, the list is partially sorted and their order is maintained for every digit\n",
    "    - important b/c if subroutine sorting algorithm is not stable, then it could become unsorted per digit\n",
    "* assumes each element has at most d digits\n",
    "    - d = the highest number of digits of an element in the array\n",
    "    - ex: [1, 23, 33, 555, 1000]. largest # = 1000, and d = 4\n",
    "* Algorithm:\n",
    "    1. find the largest number in the array\n",
    "    2. then find how many digits that number has, i.e. find d\n",
    "    3. for i = 1 to d, use a stable sort to sort all elements\n",
    "        - starts from least significant digit to most significant digit\n",
    "\n",
    "***\n",
    "Analysis:\n",
    "* time complexity: O(d * (n + b))\n",
    "    - d = highest number of digits in the largest number\n",
    "    - n = number of elements in the list\n",
    "    - b = base of the numbers\n",
    "        - in this case, b = 10 b/c we are working in base 10 and each digit is an int. from 0 --> 9\n",
    "        - for base 2, b = 2 b/c each digit is either a 0 or a 1\n",
    "    - essentially: O(d * O(counting sort))\n",
    "        - counting sort = O(n + k)\n",
    "        - but in this case, k = base of the numbers\n",
    "        - for a regular counting sort, the storage array goes from 0 --> highest number in array\n",
    "        - but since we go by digit, it is just 0 --> highest number of a digit for that base\n",
    "* space complexity: O(n + b)\n",
    "    - essentially,we create b number of buckets to store all the elements\n",
    "    - so there are b buckets with n number of elements in all of the buckets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "// digitalocean's version\n",
    "\n",
    "// gets the digit at a specific index\n",
    "function getNum(num, index) {\n",
    "    let strNum = String(num);\n",
    "    let end = strNum.length - 1;\n",
    "    let foundNum = strNum[end - index];\n",
    "    \n",
    "    return foundNum === undefined ? 0 : foundNum;\n",
    "}\n",
    "\n",
    "// finds the largest number in the arr\n",
    "// to find out the # of digits to iterate through\n",
    "function largestNum(arr) {\n",
    "    let largest = 0;\n",
    "    arr.forEach(num => largest = largest < num ? num : largest);\n",
    "    \n",
    "    // returns the # of digits of the largest number in the array\n",
    "    return String(largest).length;\n",
    "}\n",
    "\n",
    "function radixSort(arr) {\n",
    "    let maxLength = largestNum(arr);\n",
    "    \n",
    "    for(let i = 0; i < maxLength; i++) {\n",
    "        // since there are only 10 possible values for each digit\n",
    "        // e.g. 0, 1, 2, 3, ... , 9, we only need a bucket of length 10\n",
    "        let buckets = Array.from({ length: 10}, () => []);\n",
    "        \n",
    "        for(let j = 0; j < arr.length; j++) {\n",
    "            let num = getNum(arr[j], i);\n",
    "            \n",
    "            if(num !== undefined) {\n",
    "                buckets[num].push(arr[j]);\n",
    "            }\n",
    "        };\n",
    "        \n",
    "        arr = buckets.flat();\n",
    "    }\n",
    "    return arr;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bucket Sort\n",
    "* divides the elements of the unsorted array into groups called Buckets\n",
    "* these buckets are sorted and then all of them concatenated\n",
    "* Algorithm:\n",
    "    1. find the largest number in the list and use it to create a divider constant\n",
    "        - in this case divider = Math.ceiling((max + 1) / # buckets)\n",
    "        - num buckets = 10\n",
    "    2. make a pass through the list and put each element into a bucket\n",
    "        - bucket it belongs to = element / divider\n",
    "        so if element = 10 and divider = 5, then 10 / 5 = 2 so element belongs to bucket 2\n",
    "        - we take Math.floor(element / divider)\n",
    "    3. go through each bucket and sort all the elements in them\n",
    "        - can use any sorting algorithm\n",
    "        - we used quickSort in our case\n",
    "    4. concatenate the buckets together\n",
    "        - easiest way with javascript is Array.prototype.flat() which returns a new flattened array\n",
    "        - ex: [ [1,2], [], [3,4] ].flat() = [1, 2, 3, 4]\n",
    "            - great if we have a sparse distribution of elements\n",
    "\n",
    "***\n",
    "Analysis:\n",
    "* time complexity: O(n)\n",
    "    - finding max value to calculate divider = O(n)\n",
    "    - putting all elements into their respective buckets = O(n)\n",
    "    - sorting each bucket will also be O(n) as well since only a portion of the total number of elements is actually sorted and worst case scenario is 1 bucket has most of the elements\n",
    "    - worse case scenario for bucket sort: O(n^2)\n",
    "        - this happens when almost all of the elements in the original array are in one bucket\n",
    "* space complexity: O(n)\n",
    "    - the buckets array holds all the elements of the original array we want sorted so that is O(n)\n",
    "    - and depending on the sorting algorithm, the space complexity is subject to change as well"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "function bucketSort(arr) {\n",
    "    let max = Math.max(...arr);\n",
    "    // # buckets = 10\n",
    "    let divider = Math.ceil( (max + 1) / 10 );\n",
    "    let buckets = Array.from( {length: 10}, () => []);\n",
    "    \n",
    "    // start putting elements in arr into buckets\n",
    "    arr.forEach(num => {\n",
    "        let key = Math.trunc(num / divider);\n",
    "        buckets[key].push(num);\n",
    "    })\n",
    "    \n",
    "    // then sort each bucket using any sorting algorithm\n",
    "    // i used quicksort for this\n",
    "    buckets.forEach(bucket => quickSort(bucket));\n",
    "    \n",
    "    return buckets.flat();\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Javascript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "13.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}