HW0.ipynb

{
  "metadata": {
    "name": ""
  }, 
  "nbformat": 3, 
  "nbformat_minor": 0, 
  "worksheets": [
    {
      "cells": [
        {
          "source": [
            "# Homework 0\n", 
            "\n", 
            "### Due Tuesday, September 10 (but no submission is required)\n", 
            "\n", 
            "---\n", 
            "\n", 
            "Welcome to CS109 / STAT121 / AC209 / E-109 (http://cs109.org/).  In this class, we will be using a variety of tools that will require some initial configuration. To ensure everything goes smoothly moving forward, we will setup the majority of those tools in this homework. While some of this will likely be dull, doing it now will enable us to do more exciting work in the weeks that follow without getting bogged down in further software configuration. This homework will not be graded, however it is essential that you complete it timely since it will enable us to set up your accounts. You do not have to hand anything in, with the exception of filling out the online survey. \n", 
            "\n", 
            "## Class Survey, Piazza, and Introduction\n", 
            "\n", 
            "**Class Survey**\n", 
            "\n", 
            "Please complete the mandatory course survey located [here](https://docs.google.com/spreadsheet/viewform?formkey=dFg1ZFJwLWJ6ZWhWR1JJb0tES3lGMEE6MA#gid=0). It should only take a few moments of your time. Once you fill in the survey we will sign you up to the course forum on Piazza and the dropbox system that you will use to hand in the homework. It is imperative that you fill out the survey on time as we use the provided information to sign you up for these services. \n", 
            "\n", 
            "**Piazza**\n", 
            "\n", 
            "Go to [Piazza](https://piazza.com/harvard/fall2013/cs109/home) and sign up for the class using your Harvard e-mail address. \n", 
            "\n", 
            "You will use Piazza as a forum for discussion, to find team members, to arrange appointments, and to ask questions. Piazza should be your primary form of communication with the staff. Use the staff e-mail (staff@cs109.org) only for individual requests, e.g., to excuse yourself from a mandatory guest lecture. All readings, homeworks, and project descriptions will be announced on Piazza first. \n", 
            "\n", 
            "**Introduction**\n", 
            "\n", 
            "Once you are signed up to the Piazza course forum, introduce yourself to your classmates and course staff with a follow-up post in the introduction thread. Include your name/nickname, your affiliation, why you are taking this course, and tell us something interesting about yourself (e.g., an industry job, an unusual hobby, past travels, or a cool project you did, etc.). Also tell us whether you have experience with data science. \n", 
            "\n", 
            "## Programming expectations\n", 
            "\n", 
            "All the assignments and labs for this class will use Python and, for the most part, the browser-based IPython notebook format you are currently viewing. Knowledge of Python is not a prerequisite for this course, **provided you are comfortable learning on your own as needed**. While we have strived to make the programming component of this course straightforward, we will not devote much time to teaching prorgramming or Python syntax. Basically, you should feel comfortable with:\n", 
            "\n", 
            "* How to look up Python syntax on Google and StackOverflow.\n", 
            "* Basic programming concepts like functions, loops, arrays, dictionaries, strings, and if statements.\n", 
            "* How to learn new libraries by reading documentation.\n", 
            "* Asking questions on StackOverflow or Piazza.\n", 
            "\n", 
            "There are many online tutorials to introduce you to scientific python programming. [Here is one](https://github.com/jrjohansson/scientific-python-lectures) that is very nice. Lectures 1-4 are most relevant to this class.\n", 
            "\n", 
            "## Getting Python\n", 
            "\n", 
            "You will be using Python throughout the course, including many popular 3rd party Python libraries for scientific computing. [Anaconda](http://continuum.io/downloads) is an easy-to-install bundle of Python and most of these libraries. We recommend that you use Anaconda for this course.\n", 
            "\n", 
            "Please visit [this page](https://github.com/cs109/content/wiki/Installing-Python) and follow the instructions to set up Python\n", 
            "\n", 
            "<hline>\n", 
            "\n", 
            "## Hello, Python\n", 
            "\n", 
            "The IPython notebook is an application to build interactive computational notebooks. You'll be using them to complete labs and homework. Once you've set up Python, please <a href=https://raw.github.com/cs109/content/master/HW0.ipynb download=\"HW0.ipynb\">download this page</a>, and open it with IPython by typing\n", 
            "\n", 
            "```\n", 
            "ipython notebook <name_of_downloaded_file>\n", 
            "```\n", 
            "\n", 
            "For the rest of the assignment, use your local copy of this page, running on IPython.\n", 
            "\n", 
            "Notebooks are composed of many \"cells\", which can contain text (like this one), or code (like the one below). Double click on the cell below, and evaluate it by clicking the \"play\" button above, for by hitting shift + enter"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 1, 
          "input": [
            "x = [10, 20, 30, 40, 50]\n", 
            "for item in x:\n", 
            "    print \"Item is \", item"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "## Python Libraries\n", 
            "\n", 
            "We will be using a several different libraries throughout this course. If you've successfully completed the [installation instructions](https://github.com/cs109/content/wiki/Installing-Python), all of the following statements should run."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 2, 
          "input": [
            "#IPython is what you are using now to run the notebook\n", 
            "import IPython\n", 
            "print \"IPython version:      %6.6s (need at least 1.0)\" % IPython.__version__\n", 
            "\n", 
            "# Numpy is a library for working with Arrays\n", 
            "import numpy as np\n", 
            "print \"Numpy version:        %6.6s (need at least 1.7.1)\" % np.__version__\n", 
            "\n", 
            "# SciPy implements many different numerical algorithms\n", 
            "import scipy as sp\n", 
            "print \"SciPy version:        %6.6s (need at least 0.12.0)\" % sp.__version__\n", 
            "\n", 
            "# Pandas makes working with data tables easier\n", 
            "import pandas as pd\n", 
            "print \"Pandas version:       %6.6s (need at least 0.11.0)\" % pd.__version__\n", 
            "\n", 
            "# Module for plotting\n", 
            "import matplotlib\n", 
            "print \"Mapltolib version:    %6.6s (need at least 1.2.1)\" % matplotlib.__version__\n", 
            "\n", 
            "# SciKit Learn implements several Machine Learning algorithms\n", 
            "import sklearn\n", 
            "print \"Scikit-Learn version: %6.6s (need at least 0.13.1)\" % sklearn.__version__\n", 
            "\n", 
            "# Requests is a library for getting data from the Web\n", 
            "import requests\n", 
            "print \"requests version:     %6.6s (need at least 1.2.3)\" % requests.__version__\n", 
            "\n", 
            "# Networkx is a library for working with networks\n", 
            "import networkx as nx\n", 
            "print \"NetworkX version:     %6.6s (need at least 1.7)\" % nx.__version__\n", 
            "\n", 
            "#BeautifulSoup is a library to parse HTML and XML documents\n", 
            "import BeautifulSoup\n", 
            "print \"BeautifulSoup version:%6.6s (need at least 3.2)\" % BeautifulSoup.__version__\n", 
            "\n", 
            "#MrJob is a library to run map reduce jobs on Amazon's computers\n", 
            "import mrjob\n", 
            "print \"Mr Job version:       %6.6s (need at least 0.4)\" % mrjob.__version__\n", 
            "\n", 
            "#Pattern has lots of tools for working with data from the internet\n", 
            "import pattern\n", 
            "print \"Pattern version:      %6.6s (need at least 2.6)\" % pattern.__version__"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "If any of these libraries are missing or out of date, you will need to [install them](https://github.com/cs109/content/wiki/Installing-Python#installing-additional-libraries) and restart IPython"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "## Hello matplotlib"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "The notebook integrates nicely with Matplotlib, the primary plotting package for python. This should embed a figure of a sine wave:"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 3, 
          "input": [
            "#this line prepares IPython for working with matplotlib\n", 
            "%matplotlib inline  \n", 
            "\n", 
            "# this actually imports matplotlib\n", 
            "import matplotlib.pyplot as plt  \n", 
            "\n", 
            "x = np.linspace(0, 10, 30)  #array of 30 points from 0 to 10\n", 
            "y = np.sin(x)\n", 
            "z = y + np.random.normal(size=30) * .2\n", 
            "plt.plot(x, y, 'ro-', label='A sine wave')\n", 
            "plt.plot(x, z, 'b-', label='Noisy sine')\n", 
            "plt.legend(loc = 'lower right')\n", 
            "plt.xlabel(\"X axis\")\n", 
            "plt.ylabel(\"Y axis\")           "
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "If that last cell complained about the `%matplotlib` line, you need to update IPython to v1.0, and restart the notebook. See the [installation page](https://github.com/cs109/content/wiki/Installing-Python)"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "## Hello Numpy\n", 
            "\n", 
            "The Numpy array processing library is the basis of nearly all numerical computing in Python. Here's a 30 second crash course. For more details, consult Chapter 4 of Python for Data Analysis, or the [Numpy User's Guide](http://docs.scipy.org/doc/numpy-dev/user/index.html)"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 4, 
          "input": [
            "print \"Make a 3 row x 4 column array of random numbers\"\n", 
            "x = np.random.random((3, 4))\n", 
            "print x\n", 
            "print\n", 
            "\n", 
            "print \"Add 1 to every element\"\n", 
            "x = x + 1\n", 
            "print x\n", 
            "print\n", 
            "\n", 
            "print \"Get the element at row 1, column 2\"\n", 
            "print x[1, 2]\n", 
            "print\n", 
            "\n", 
            "# The colon syntax is called \"slicing\" the array. \n", 
            "print \"Get the first row\"\n", 
            "print x[0, :]\n", 
            "print\n", 
            "\n", 
            "print \"Get every 2nd column of the first row\"\n", 
            "print x[0, ::2]\n", 
            "print"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Print the maximum, minimum, and mean of the array. This does **not** require writing a loop. In the code cell below, type `x.m<TAB>`, to find built-in operations for common array statistics like this"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 5, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Call the `x.max` function again, but use the `axis` keyword to print the maximum of each row in x."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 6, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Here's a way to quickly simulate 500 coin \"fair\" coin tosses (where the probabily of getting Heads is 50%, or 0.5)"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 7, 
          "input": [
            "x = np.random.binomial(500, .5)\n", 
            "print \"number of heads:\", x"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Repeat this simulation 500 times, and use the [plt.hist() function](http://matplotlib.org/api/pyplot_api.html#matplotlib.pyplot.hist) to plot a histogram of the number of Heads (1s) in each simulation"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 8, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "## The Monty Hall Problem\n", 
            "\n", 
            "\n", 
            "Here's a fun and perhaps surprising statistical riddle, and a good way to get some practice writing python functions\n", 
            "\n", 
            "In a gameshow, contestants try to guess which of 3 closed doors contain a cash prize (goats are behind the other two doors). Of course, the odds of choosing the correct door are 1 in 3. As a twist, the host of the show occasionally opens a door after a contestant makes his or her choice. This door is always one of the two the contestant did not pick, and is also always one of the goat doors (note that it is always possible to do this, since there are two goat doors). At this point, the contestant has the option of keeping his or her original choice, or swtiching to the other unopened door. The question is: is there any benefit to switching doors? The answer surprises many people who haven't heard the question before.\n", 
            "\n", 
            "We can answer the problem by running simulations in Python. We'll do it in several parts.\n", 
            "\n", 
            "First, write a function called `simulate_prizedoor`. This function will simulate the location of the prize in many games -- see the detailed specification below:"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 9, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "simulate_prizedoor\n", 
            "\n", 
            "Generate a random array of 0s, 1s, and 2s, representing\n", 
            "hiding a prize between door 0, door 1, and door 2\n", 
            "\n", 
            "Parameters\n", 
            "----------\n", 
            "nsim : int\n", 
            "    The number of simulations to run\n", 
            "\n", 
            "Returns\n", 
            "-------\n", 
            "sims : array\n", 
            "    Random array of 0s, 1s, and 2s\n", 
            "\n", 
            "Example\n", 
            "-------\n", 
            ">>> print simulate_prizedoor(3)\n", 
            "array([0, 0, 2])\n", 
            "\"\"\"\n", 
            "def simulate_prizedoor(nsim):\n", 
            "    #compute here\n", 
            "    return answer\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Next, write a function that simulates the contestant's guesses for `nsim` simulations. Call this function `simulate_guess`. The specs:"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 10, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "simulate_guess\n", 
            "\n", 
            "Return any strategy for guessing which door a prize is behind. This\n", 
            "could be a random strategy, one that always guesses 2, whatever.\n", 
            "\n", 
            "Parameters\n", 
            "----------\n", 
            "nsim : int\n", 
            "    The number of simulations to generate guesses for\n", 
            "\n", 
            "Returns\n", 
            "-------\n", 
            "guesses : array\n", 
            "    An array of guesses. Each guess is a 0, 1, or 2\n", 
            "\n", 
            "Example\n", 
            "-------\n", 
            ">>> print simulate_guess(5)\n", 
            "array([0, 0, 0, 0, 0])\n", 
            "\"\"\"\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Next, write a function, `goat_door`, to simulate randomly revealing one of the goat doors that a contestant didn't pick."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 11, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "goat_door\n", 
            "\n", 
            "Simulate the opening of a \"goat door\" that doesn't contain the prize,\n", 
            "and is different from the contestants guess\n", 
            "\n", 
            "Parameters\n", 
            "----------\n", 
            "prizedoors : array\n", 
            "    The door that the prize is behind in each simulation\n", 
            "guesses : array\n", 
            "    THe door that the contestant guessed in each simulation\n", 
            "\n", 
            "Returns\n", 
            "-------\n", 
            "goats : array\n", 
            "    The goat door that is opened for each simulation. Each item is 0, 1, or 2, and is different\n", 
            "    from both prizedoors and guesses\n", 
            "\n", 
            "Examples\n", 
            "--------\n", 
            ">>> print goat_door(np.array([0, 1, 2]), np.array([1, 1, 1]))\n", 
            ">>> array([2, 2, 0])\n", 
            "\"\"\"\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Write a function, `switch_guess`, that represents the strategy of always switching a guess after the goat door is opened."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 12, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "switch_guess\n", 
            "\n", 
            "The strategy that always switches a guess after the goat door is opened\n", 
            "\n", 
            "Parameters\n", 
            "----------\n", 
            "guesses : array\n", 
            "     Array of original guesses, for each simulation\n", 
            "goatdoors : array\n", 
            "     Array of revealed goat doors for each simulation\n", 
            "\n", 
            "Returns\n", 
            "-------\n", 
            "The new door after switching. Should be different from both guesses and goatdoors\n", 
            "\n", 
            "Examples\n", 
            "--------\n", 
            ">>> print switch_guess(np.array([0, 1, 2]), np.array([1, 2, 1]))\n", 
            ">>> array([2, 0, 0])\n", 
            "\"\"\"\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Last function: write a `win_percentage` function that takes an array of `guesses` and `prizedoors`, and returns the percent of correct guesses"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 13, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "win_percentage\n", 
            "\n", 
            "Calculate the percent of times that a simulation of guesses is correct\n", 
            "\n", 
            "Parameters\n", 
            "-----------\n", 
            "guesses : array\n", 
            "    Guesses for each simulation\n", 
            "prizedoors : array\n", 
            "    Location of prize for each simulation\n", 
            "\n", 
            "Returns\n", 
            "--------\n", 
            "percentage : number between 0 and 100\n", 
            "    The win percentage\n", 
            "\n", 
            "Examples\n", 
            "---------\n", 
            ">>> print win_percentage(np.array([0, 1, 2]), np.array([0, 0, 0]))\n", 
            "33.333\n", 
            "\"\"\"\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Now, put it together. Simulate 10000 games where contestant keeps his original guess, and 10000 games where the contestant switches his door after a  goat door is revealed. Compute the percentage of time the contestant wins under either strategy. Is one strategy better than the other?"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 14, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Many people find this answer counter-intuitive (famously, PhD mathematicians have incorrectly claimed the result must be wrong. Clearly, none of them knew Python). \n", 
            "\n", 
            "One of the best ways to build intuition about why opening a Goat door affects the odds is to re-run the experiment with 100 doors and one prize. If the game show host opens 98 goat doors after you make your initial selection, would you want to keep your first pick or switch? Can you generalize your simulation code to handle the case of `n` doors?"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }
      ], 
      "metadata": {}
    }
  ]
}