HW_3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=\"4\" style=\"color:red;\"> **IMPORTANT: ** When submitting this homework notebook, please modify only the cells that start with:</font>\n",
    "\n",
    "```python\n",
    "# modify this cell\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Note:* No packages should be imported for this assignment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sets: The Inclusion-Exclusion Principle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 1.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img style=\"float: right;width:300px;height:200px\" src=\"figs/Venn2.jpg\">\n",
    "The inclusion-exclusion principle states that for two sets $A$ and $B$,\n",
    "\n",
    "$$|A\\cup B|=|A|+|B|-|A\\cap B|.$$\n",
    "\n",
    "Write the following functions to determine $|A\\cup B|$ in two different ways.\n",
    "\n",
    "A function **union** that determines first $A\\cup B$ and then evaluates the union's size.\n",
    "Output the ordered pair $(A\\cup B, |A\\cup B|)$.\n",
    "\n",
    "<font  style=\"color:blue\"> * **Sample run** *</font>\n",
    "```python\n",
    "A = {1, 2, 3}\n",
    "B = {3, -6, 2, 0}\n",
    "print union(A, B)\n",
    "```\n",
    "\n",
    "<font  style=\"color:magenta\"> * **Expected Output** *</font>\n",
    "```\n",
    "({-6, 0, 1, 2, 3}, 5)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# modify this cell\n",
    "\n",
    "def union(A, B):\n",
    "    # inputs: A and B are of type 'set'\n",
    "    # output: a tuple of the type (set, set_length)\n",
    "    \n",
    "    C= A.union(B)\n",
    "    return(C, len(C))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "ex1",
     "locked": true,
     "points": "5",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "A = {1,4,-3, \"bob\"}\n",
    "B = {2,1,-3,\"jill\"}\n",
    "assert union(A,B) == ({-3, 1, 2, 4, 'bob', 'jill'}, 6)\n",
    "\n",
    "#\n",
    "# AUTOGRADER TEST - DO NOT REMOVE\n",
    "#\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 1.2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A function **inclusion_exclusion** that first deterimines $|A|$, $|B|$, $A\\cap B$, and $|A\\cap B|$, and then uses the inclusion-exclusion formula to determine $|A\\cup B|$. \n",
    "Output the tuple $(|A|, |B|, |A\\cap B|, |A\\cup B|)$.\n",
    "\n",
    "<img style=\"float: right;width:400px;height:266px\" src=\"figs/Venn3.jpg\">\n",
    "<font  style=\"color:blue\"> * **Sample run:** *</font>\n",
    "```python\n",
    "A = {1, 2, 3}\n",
    "B = {3, -6, 2, 0}\n",
    "print inclusion_exclusion(A, B)\n",
    "print \"notice: 3 + 4 - 2 == 5\"\n",
    "```\n",
    "\n",
    "<font  style=\"color:magenta\"> * **Expected Output:** *</font>\n",
    "```\n",
    "(3, 4, 2, 5)\n",
    "notice: 3 + 4 - 2 == 5\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# modify this cell\n",
    "\n",
    "def inclusion_exclusion(A, B):\n",
    "    # inputs: A and B are of type 'set'\n",
    "    # output: a tuple of four integers\n",
    "    C= A.intersection(B)\n",
    "    D= A.union(B)\n",
    "    return(len(A),len(B),len(C),len(D))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "ex2",
     "locked": true,
     "points": "5",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Check Function\n",
    "\n",
    "A = {1, 2, 3, 4, 5}\n",
    "B = {0, 2, -6, 5, 8, 9}\n",
    "assert inclusion_exclusion(A, B) == (5, 6, 2, 9)\n",
    "\n",
    "#\n",
    "# AUTOGRADER TEST - DO NOT REMOVE\n",
    "#\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The inclusion-exclusion principle says that for three sets $A$, $B$ and $C$, \n",
    "\n",
    "$$|A\\cup B\\cup C|=|A|+|B|+|C|-|A\\cap B|-|B\\cap C|-|C\\cap A|+|A\\cap B\\cap C|$$\n",
    "\n",
    "We will write the following functions to determine $|A\\cup B\\cup C|$ in two different ways."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 2.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write function **union3** that first determines $A\\cup B\\cup C$ and then evaluates the size of this union.\n",
    "Output the tuple $(A\\cup B\\cup C, |A\\cup B\\cup C|)$.\n",
    "\n",
    "<font  style=\"color:blue\"> * **Sample run:** *</font>\n",
    "```python\n",
    "A = {1, 2, 3, 4, 5}\n",
    "B = {0, 2, -6, 5, 8, 9}\n",
    "C = {2, 10}\n",
    "union3(A, B, C)\n",
    "```\n",
    "\n",
    "\n",
    "<font  style=\"color:magenta\"> * **Expected Output:** *</font>\n",
    "```\n",
    "({-6, 0, 1, 2, 3, 4, 5, 8, 9, 10}, 10)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# modify this cell\n",
    "\n",
    "def union3(A, B, C):\n",
    "    # inputs: A, B and C are of type 'set'\n",
    "    # output: a tuple of the type (set, set_length)\n",
    "    D= A.union(B.union(C))\n",
    "    return(D, len(D))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "ex3",
     "locked": true,
     "points": "5",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# check Function\n",
    "A = {1, 2, 4, 5, 10}\n",
    "B = {5, 2, -6, 5, 8, 9}\n",
    "C = {2, 10, 13}\n",
    "assert union3(A,B,C) == ({-6, 1, 2, 4, 5, 8, 9, 10, 13}, 9)\n",
    "\n",
    "#\n",
    "# AUTOGRADER TEST - DO NOT REMOVE\n",
    "#\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 2.2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A function **inclusion_exclusion3** that first deterimines the sizes of $A$, $B$, $C$ and their mutual intersections, and then uses the inclusion-exclusion principle to determine the size of the union. Output the tuple $(|A\\cap B\\cap C|, |A\\cup B\\cup C|)$. Note that for brevity we are asking you to output the intermediate answer just for $A\\cap B\\cap C$, but you need to calculate all. \n",
    "\n",
    "<font  style=\"color:blue\"> * **Sample run:** *</font>\n",
    "```python\n",
    "A = {1, 2, 3, 4, 5}\n",
    "B = {0, 2, -6, 5, 8, 9}\n",
    "C = {2, 10}\n",
    "print inclusion_exclusion3(A, B, C)\n",
    "```\n",
    "\n",
    "\n",
    "<font  style=\"color:magenta\"> * **Expected Output:** *</font>\n",
    "```\n",
    "(1, 10)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# modify this cell\n",
    "\n",
    "def inclusion_exclusion3(A, B, C):\n",
    "    # inputs: A, B and C are of type 'set'\n",
    "    # output: a tuple of two integers\n",
    "    D= A.intersection(B.intersection(C))\n",
    "    E= A.union(B.union(C))\n",
    "    return(len(D),len(E))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "ex4",
     "locked": true,
     "points": "5",
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Check Function\n",
    "\n",
    "A = {1, 2, 4, 5, 10}\n",
    "B = {5, 2, -6, 5, 8, 9, 10}\n",
    "C = {2, 10, 13}\n",
    "assert inclusion_exclusion3(A,B,C) == (2, 9)\n",
    "\n",
    "#\n",
    "# AUTOGRADER TEST - DO NOT REMOVE\n",
    "#\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "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.5"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "48px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}