Chapter 3 - Data Structures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 3: Data Structures (Completed 7/29: 24%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stacks, Queues, and Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 [3]\n",
    "\n",
    "A common problem for compilers and text editors is determining whether the\n",
    "parentheses in a string are balanced and properly nested. For example, the string ((())())() contains properly nested pairs of parentheses, which the strings )()( and ()) do not. Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. For full credit, identify the position of the first offending parenthesis if the string is not properly nested and balanced."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "The algorithm will look through a possibly long string $s$, and each left parenthesis \"(\" will be pushed onto a stack, and each right parenthesis \")\" will trigger a \"pop\" from the stack. If the stack is empty during an attempted \"pop\", then there is an extra \")\", and if there is an extra \"(\" on the stack after the end of the string $s$ has been reached, then there was an extra \"(\".\n",
    "\n",
    "$\\hspace{2em} function \\text{ parentheses_check}(s):$  \n",
    "$\\hspace{4em} i = -1$  \n",
    "$\\hspace{4em} stack =  stack$  \n",
    "$\\hspace{4em} \\text{for } c \\text{ in } s:$  \n",
    "$\\hspace{6em} i = i + 1$  \n",
    "$\\hspace{6em} \\text{if } c \\neq \\text{'('} \\text{ and } c \\neq \\text{')'}:$  \n",
    "$\\hspace{8em} continue$  \n",
    "$\\hspace{6em} \\text{if } c = \\text{'('}:$  \n",
    "$\\hspace{8em} stack.push(c)$  \n",
    "$\\hspace{6em} else:$  \n",
    "$\\hspace{8em} try:$  \n",
    "$\\hspace{10em} stack.pop()$  \n",
    "$\\hspace{8em} except \\text{ StackEmpty}:$  \n",
    "$\\hspace{10em} return\\ i$  \n",
    "$\\hspace{4em} return \\text{ True}$  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 [3]\n",
    "\n",
    "Write a program to reverse the direction of a given singly-linked list. In other words, after the reversal all pointers should now point backwards. Your algorithm should take linear time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "$\\hspace{2em} function \\text{ reverse}(node1, node2):$  \n",
    "$\\hspace{4em} p = \\text{target of node2's \"next\" pointer}$  \n",
    "$\\hspace{4em} \\text{Change node2's \"next\" pointer to point to node1}$  \n",
    "$\\hspace{4em} \\text{If p == NULL}:$  \n",
    "$\\hspace{6em} \\text{Return pointer to node2}$  \n",
    "$\\hspace{4em} \\text{Else:}$  \n",
    "$\\hspace{6em} \\text{Return reverse}(node2, p)$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Trees and Other Dictionary Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 [3]\n",
    "\n",
    "Design a dictionary data structure in which search, insertion, and deletion can all be processed in $O(1)$ time in the worst case. You may assume the set elements are integers drawn from a finite set $1, 2, \\ldots , n$, and initialization can take $O(n)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "A hash table of length $n$ that hashs the integer $i$ to value $i$ should do the trick. Searching is constant time, since the number $i$ is in position $i$.\n",
    "\n",
    "Upon insertion is when you would have to worry about collisions. The only way two elements could collide upon hashing in this case is if they are the same number. If such duplicates are allowed (i.e. the problem allows for the same number to be added more than once), then each position in the array should contain a stack, with the duplicates pushed onto the stack upon insertion.\n",
    "\n",
    "Upon deletion, the number $i$ should be popped off of the stack in position $i$.\n",
    "\n",
    "If the problem does not allow for the same number to be added twice, then a static array of size $n$ with the above hash function would work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.5 [3]\n",
    "\n",
    "Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on $n$ nodes:\n",
    "\n",
    "1. All nodes store data, two child pointers, and a parent pointer. The data field requires four bytes and each pointer requires four bytes.\n",
    "2. Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "1.\n",
    "Each node has 1 data item and 3 pointers for a total of 16 bytes. 4 of those bytes are for data, so the overhead fraction is $\\frac{4}{16} = \\frac{1}{4}$.\n",
    "\n",
    "2.\n",
    "Note here that both leaf and internal nodes need 4 bytes. So the total memory storage needed is 4n.\n",
    "\n",
    "The amount of data storage depends on the number of leaf nodes, and differently shaped trees will have different amounts of leaf nodes. If we know the number of leaf nodes $l$, then the overhead is $\\frac{l}{n}$.\n",
    "\n",
    "In the case that we don't know the number of leaf nodes, for simplicity, we'll assume that $n=2^m - 1$ for some integer $m$ and the tree is perfectly balanced. In this case, there will be $2^{m-1}$ leaf nodes where $m =\\lg{(n+1)}$. This can be simplified: $2^{\\lg{(n+1)}-1}=\\frac{n+1}{2}$. For example, if $n=15$, then $m=4$, and there are 1, 2, 4, and 8 nodes at each depth, and therefore $2^3 = \\frac{16}{2}= 8$ nodes in the final row.\n",
    "\n",
    "The overhead in this case is then given by\n",
    "\n",
    "$\\frac{4l}{4n}\n",
    "= \\frac{l}{n}\n",
    "= \\frac{n+1}{2n}\n",
    "\\approx \\frac{1}{2}$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Applications of Tree Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.12 [5]\n",
    "\n",
    "Suppose you are given an input set $S$ of $n$ numbers, and a black box that if given any sequence of real numbers and an integer $k$ instantly and correctly answers whether there is a subset of input sequence whose sum is exactly $k$. Show how to use the black box $O(n)$ times to find a subset of $S$ that adds up to $k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "$\\hspace{2em} \\text{If black_box}(S) == \\text{False}$  \n",
    "$\\hspace{4em} \\text{Return False}$  \n",
    "$\\hspace{2em} \\text{For } i \\text{ from } 0 \\text{ to } n-1, do:$  \n",
    "$\\hspace{4em} s = S[i]$  \n",
    "$\\hspace{4em} \\text{Delete } S[i]$  \n",
    "$\\hspace{4em} \\text{If black_box}(S) == \\text{True}$  \n",
    "$\\hspace{6em} \\text{Continue}$  \n",
    "$\\hspace{4em} \\text{Else}$  \n",
    "$\\hspace{6em} S[i] = s$  \n",
    "$\\hspace{2em} \\text{Return }S$  \n",
    "\n",
    "After checking that a subset does exist that adds up to $k$, sequentially delete items from $S$ and test if a valid (meaning its elements add up to $k$) subset still exists. If it does, move on to the next iteration. Otherwise undo the deletion.\n",
    "\n",
    "After the last iteration, there can be only one remaining valid subset. Elements that do not belong to every possible remaining valid subset would have been deleted, leaving those other sets as still valid subsets that add up to $k$. Only elements that appear in all the remaining valid subsets would be retained. But if all the remaining valid subsets have the same elements, then they are all the same, i.e. there is only 1 such subset remaining in $S$. Since elements that do not appear in *any* valid subset would have been deleted as well, the returned set $S$ is itself a valid subset; its elements add up to $k$.\n",
    "\n",
    "The black box gets used once for every element of the list. So it was used $O(n)$ times, specifically, $n$ times."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation Projects"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interview Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.18 [3]\n",
    "\n",
    "What method would you use to look up a word in a dictionary?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "One method would be binary search. I would open to roughly the middle page of the dictionary, and if the word is not on that page, I would repeat the process on the lower or upper portion of the dictionary depending on whether the word is alphabetically earlier or later than the words on that page.\n",
    "\n",
    "However, if I knew roughly where each letter started in the dictionary, say if it had tabs, then I would isolate that portion of the dictionary corresponding to the first letter of my word, and then perform binary search on that section."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.19 [3]\n",
    "\n",
    "Imagine you have a closet full of shirts. What can you do to organize your shirts for easy retrieval?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution*:\n",
    "\n",
    "It depends on how I pick my shirt in the morning. If I want to wear all my shirts and I don't care about the particular order, then each time I do laundry I'll put the clean shirts on the left, and each morning wear the shirt furthest to the right.\n",
    "\n",
    "Another general option is to sort the shirts. I usually identify them most by color, so I could put them in some order based on color."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}