01_Intro_to_Computing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Computing with Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This section is based on [*Introduction to Computing*](https://computingbook.org/) by D. Evans."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Processes and procedures\n",
    "\n",
    "* A **process** is a sequence of steps. Each step changes the state of the world in some small way, and the result of all the steps produces some goal state.\n",
    "* A **procedure** is a description of a process. A simple process can be described just by listing the steps. The list of steps is the procedure; the act of following them is the process."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question**: can you think of some real-life processes/procedures?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a procedure for making tea, adapted from the directions listed in the [Tetley Tea FAQ](https://www.tetleyusa.com/tetley-tea-faq):\n",
    "1. Start with fresh, cold water.\n",
    "1. Place a tea bag in your favorite cup or mug.\n",
    "1. Bring water to a rolling boil and immediately pour over your tea bag.\n",
    "1. Steep for a good 3 to 5 minutes.\n",
    "1. Remove the tea bag, relax and enjoy!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question**: are there limitations to describing processes by listing steps like this?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithms and computers\n",
    "\n",
    "Computer Science focuses on **information processes** that involve abstract information rather than physical things.\n",
    "\n",
    "* A procedure that can be followed without any thought is called a **mechanical procedure**.\n",
    "* An **algorithm** is a mechanical procedure that is guaranteed to eventually finish.\n",
    "* A **computer** is a machine that can:\n",
    "  1. Accept input.\n",
    "  1. Execute a mechanical procedure.\n",
    "  1. Produce output."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: work through the following instructions *on paper*.\n",
    "\n",
    "1. Use the list `[3, 9, 5, 2, 4]` as input.\n",
    "1. Start a counter at zero.\n",
    "1. Look at the first two numbers in the list; if the first is greater than the second, swap them and increase the counter by one. Repeat for the second and third numbers, then the third and fourth, … until the end of the list.\n",
    "1. If the counter is zero, you're done. If it's not, reset it to zero and repeat the previous step."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question**: what does the algorithm above do?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question**: does the algorithm above 'work' on *any* list?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems\n",
    "\n",
    "When we talk about writing programs to solve problems, we don't just want to solve one instance of a problem, we want an algorithm that can solve *all* instances of a problem.\n",
    "\n",
    "**A problem is defined by its inputs and the desired property of the output.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: solve the following problem *on paper*.\n",
    "\n",
    "> A pair of newly-born male and female rabbits are put in a field.\n",
    "> Rabbits mate at the age of one month and after that procreate every month, so the female rabbit produces a new pair of rabbits at the end of its second month.\n",
    "> Assume rabbits never die and that each female rabbit produces one new pair (one male, one female) every month from her second month on.\n",
    "> How many pairs will there be in one year?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: code your solution in Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: write a function that computes the [Collatz sequence](https://en.wikipedia.org/wiki/Collatz_conjecture) starting from a given number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: simulate multiple rounds of the [Monty Hall game](http://marilynvossavant.com/game-show-problem/) described below. In particular, show the effect of always keeping the first guess compared to always switching.\n",
    "\n",
    "> Suppose you're on a game show, and you're given the choice of three doors: behind one door is a car; behind the others, goats.\n",
    "> You pick a door — say the first — and the host, who knows what's behind the doors, opens another door — say the third — which has a goat.\n",
    "> He says to you: do you want to pick the second door?\n",
    "> Is it to your advantage to switch your choice of doors?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}