4 Decision Trees Todo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# import symbolic capability to Python\n",
    "from sympy import *\n",
    "# print things all pretty\n",
    "from sympy.abc import *\n",
    "from sympy.plotting import plot\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from IPython.display import display\n",
    "init_printing()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercise\n",
    "\n",
    "You have a dataset with $m$ binary columns and $n$ rows. A given decision tree has the depth $d$.\n",
    "\n",
    "## Questions:\n",
    "1. How many different decision trees with depth $d=1$ are possible for a dataset with $m$ binary columns and $n$ rows?\n",
    "2. How many different decision trees with depth $d=2$ are possible for a dataset with $m$ binary columns and $n$ rows?\n",
    "3. How many different decision trees with depth $d=3$ are possible for a dataset with $m$ binary columns and $n$ rows?\n",
    "4. How many different decision trees with depth $d=4$ are possible for a dataset with $m$ binary columns and $n$ rows?\n",
    "5. In general, how many different decision trees with depth $d$ are possible for a dataset with $m$ binary columns and $n$ rows?\n",
    "6. How may different decision trees are possible for $m=4$ and $d=4$?\n",
    "7. In general, how many different decision trees of any depth are possible for a dataset with $m$ binary columns and $n$ rows?\n",
    "8. How many decision trees are possible for $m=4$ binary columns?\n",
    "9. There are $10^{80}$ atoms in the universe. What is the value for $m$ so that the number of decision trees is greater than the number of atoms in the universe?\n",
    "10. How many operations (steps) does the naive testing take of all possible decision trees for a dataset with $m$ binary columns and $n$ rows?\n",
    "11. How many operations (steps) does the naive testing take of all possible decision trees for a dataset with $m=3$ binary columns and $n=100$ rows?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Variables:\n",
    "* $n$: number of rows of the data\n",
    "* $m$: number of binary columns (attributes) of the data\n",
    "* $d$: depth of the decision tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "m = symbols(\"m\", positive=True, integer=True)\n",
    "d = symbols(\"d\", positive=True, integer=True)\n",
    "n = symbols(\"n\", positive=True, integer=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Answers:\n",
    "\n",
    "Todo"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}