{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MCL summer workshop in graph theory\n",
    "# Lab 6/27/16\n",
    "\n",
    "## Introducing your first iPython notebook!\n",
    "\n",
    "Now that you've got the hang of running Python programs through the terminal, let me introduce you to a much easier option: iPython notebooks!  These allow you to run blocks of Python code right in your browser and to integrate blocks of code with text (as I'm doing now).\n",
    "\n",
    "To open an iPython notebook, navigate to the file containing it in your terminal and type \n",
    "\n",
    "```\n",
    "ipython notebook fileName.ipynb\n",
    "```\n",
    "\n",
    "To run a block of code, click somewhere in it and press `Shift-Enter`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(\"Hello, iPython!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Compound boolean expressions\n",
    "\n",
    "In Python you can combine boolean expressions to create more complex conditionals using the keywords `and`, `or`, and `not` (equivalent to `&&`, `||`, and `!` in Java).  For example,\n",
    "\n",
    "```python\n",
    "    (x < 10) and not (x % 3 == 0)\n",
    "```\n",
    "\n",
    "will evaluate to `True` if and only if `x` is less than 10 and not a multiple of 3.\n",
    "\n",
    "Note: using parentheses to separate parts of compound conditionals makes them much more readable.\n",
    "\n",
    "### Exercise 1\n",
    "\n",
    "Complete the following code to print out all integers less than 100 which are either\n",
    "1. At most 20\n",
    "2. A multiple of 3 but not a multiple of 5 or 7."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i in range(100):\n",
    "    # Replace 'True' with the appropriate conditional\n",
    "    if True:\n",
    "        print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Lists\n",
    "\n",
    "So far we have learned about several types of objects in Python: numbers, strings, booleans (`True`/`False`), etc.  Another type of object is the *list*&mdash;an object which contains a collection of other objects (even other lists!).  This is similar to the mathematical concept of a set, except that *order matter* in a list.  Lists are the equivalent of arrays in Java.\n",
    "\n",
    "Lists are defined using square brackets `[]`:\n",
    "```python\n",
    "L = [1, 3 * 5, \"cat\", \"dog\", [3.14, \"pie\"]]\n",
    "```\n",
    "Note that the expression `3 * 5` will be evaluated and the result stored in `L`, not the string `\"3 * 5\"`.\n",
    "\n",
    "Here is some stuff you can do with lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Define a new list\n",
    "L = [\"Bilal\", \"dylan\", \"Ethan\"]\n",
    "\n",
    "print(L)\n",
    "\n",
    "# Get the length of the list (number of elements)\n",
    "print(len(L))\n",
    "\n",
    "# Get an individual element of the list\n",
    "print(L[0])\n",
    "L[1] = \"Dylan\"\n",
    "print(L)\n",
    "\n",
    "# Notice that the indices start at 0, not 1, and go up to len(L) - 1\n",
    "\n",
    "\n",
    "# Add an element to the end of the list\n",
    "L.append(\"Ginger\")\n",
    "print(L)\n",
    "print(len(L))\n",
    "\n",
    "# Sublists\n",
    "print(L[1:3])\n",
    "\n",
    "# Iterate through a list\n",
    "# You can use any variable name you want instead of 'person'\n",
    "for person in L:\n",
    "    print(person + \" stinks!\")\n",
    "    \n",
    "# Another way of iterating through the list\n",
    "for i in range(len(L)):\n",
    "    print(L[i] + \" stinks really bad!\")\n",
    "\n",
    "# Create a new list using a for loop\n",
    "# This is called \"list comprehension\"\n",
    "A = [True for i in range(10)] # 10 copies of True\n",
    "\n",
    "B = [i for i in range(10)] # Integers 0 through 9\n",
    "\n",
    "C = [2 * i for i in range(10)] # Even integers 0 through 18\n",
    "\n",
    "print(A)\n",
    "print(B)\n",
    "print(C)\n",
    "\n",
    "print(\"\")\n",
    "\n",
    "### 2D lists ###\n",
    "\n",
    "# A 10 x 20 array of 0s\n",
    "# I.e., a list of 10 lists of length 20\n",
    "A = [[0 for j in range(20)] for i in range(10)]\n",
    "\n",
    "print(A)\n",
    "\n",
    "print(\"\")\n",
    "\n",
    "# A prettier way of printing A\n",
    "# Each \"row\" of A is one of the inner lists of \n",
    "for row in A:\n",
    "    print(row)\n",
    "\n",
    "for i in range(10):\n",
    "    for j in range(20):\n",
    "        A[i][j] = i + j # Change the (i, j)the entry of A to i + j\n",
    "        \n",
    "print(\"\")\n",
    "    \n",
    "for row in A:\n",
    "    print(row)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2\n",
    "\n",
    "Repeat Exercise 1, but instead of printing out each number add it to a list and print the list at the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Start with an empty list\n",
    "L = []\n",
    "\n",
    "# Your code here\n",
    "\n",
    "print(L)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Functions\n",
    "\n",
    "In math, a function is an operation that takes an *input*, does some computations, then gives you an *output*.  For example, the function $f(x) = 3x + 5$ takes the input $3$, computes $3 \\cdot 3 + 5$, and spits out the output $14$.  The beauty of functions is that you can give them many different inputs and they will compute the output for each one!\n",
    "\n",
    "Here is how we would define this function in Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    return 3 * x + 5\n",
    "\n",
    "print(f(3))\n",
    "print(f(2.1))\n",
    "\n",
    "n = float(input(\"Enter a number: \")) # float converts your input from a string to a decimal\n",
    "print(\"f(\" + str(n) + \") == \" + str(f(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice how a single function definition is enough to compute the function for any input we throw at it!\n",
    "\n",
    "In the code above:\n",
    "* `f` is the *name* of the function.  You can name a function anything you like; it doesn't have to just be a single letter.  For example, we could have called our function `times3Plus5(x)`.\n",
    "* `x` is the *argument* to the function.  It is a variable which acts as a placeholder for whatever input you give the function (3, 2.1, etc.).  Again, you can choose the name of this variable.  Functions can have multiple arguments, and they can be any data type (number, string, boolean, etc.).\n",
    "* The `return` statement determines the output of the function.  The output is sometimes called the *return value*.\n",
    "* When we use our function, we say that we are *calling* it.  When we call `f(3)` we say that we are *passing* the value 3 to the function.\n",
    "\n",
    "**Functions are one of the most important concepts in programming, so make sure you understand them!**  Don't be afraid to ask questions if something doesn't make sense to you!\n",
    "\n",
    "### Exercise 3\n",
    "\n",
    "Implement the function $g(x, y) = x^2 + xy + y^2$ in Python.  You can compute `x`$^2$ by doing either `x * x` or `x ** 2`.  Write some code to test your function (similar to the code above)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Your code here\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sometimes functions involve more complicated computations.  For example, here is a function which computes $n!$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    fact = 1 # Start with 1\n",
    "    \n",
    "    # Multiply by all the integers up to n\n",
    "    for i in range(1, n + 1):\n",
    "        fact = fact * i\n",
    "    \n",
    "    # The number computed is the output\n",
    "    return fact\n",
    "\n",
    "theNum = int(input(\"Enter an integer: \"))\n",
    "print(fact(theNum))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The variable `fact` is called a *local variable*.  It is defined inside the function to help with computations, and it goes away when the function returns.  Try adding some code that uses it ouside the function and see what happens...\n",
    "\n",
    "### \"Extra credit\"\n",
    "\n",
    "Implement a recusive version of `factorial`.\n",
    "\n",
    "### Exercise 4\n",
    "\n",
    "The *Fibonacci numbers* are a sequence of integers $F_0, F_1, F_2, \\ldots$, where $F_0 = F_1 = 1$ and $F_n = F_{n - 1} + F_{n - 2}$.  In other words, each number in the sequence is the sum of the two previous numbers.  The first few Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, 21, ...\n",
    "\n",
    "Write a function `fib(` $n$ `)` which returns the $n$th Fibonacci number.\n",
    "\n",
    "Hints:\n",
    "* Use a `for` loop to compute $F_0, F_1, \\ldots, F_n$.\n",
    "* Use two local variables to store the previous two Fibonacci numbers, and update them in each iteration of the loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    \n",
    "    # Your code here\n",
    "    \n",
    "    # Return the appropriate value instead of 0\n",
    "    return 0\n",
    "\n",
    "n = int(input(\"Enter an integer: \"))\n",
    "print(\"F_\" + str(n) + \" == \" + str(fib(n)))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now write another function, `fibs(` $n$ `)`, which retuns a *list* of the Fibonacci numbers $F_0, F_1, \\ldots, F_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fibs(n):\n",
    "    L = []\n",
    "    \n",
    "    # Your code here\n",
    "    \n",
    "    return L\n",
    "\n",
    "n = int(input(\"Enter an integer: \"))\n",
    "print(fibs(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## A simple graph class\n",
    "\n",
    "I implemented a basic graph class for you to play around with.  You can download it [here](http://homepages.math.uic.edu/~scole3/summer2016/labs/graphs.py) (save it in the same directory as this iPython notebook).  You can take a look at the code if you are curious about what classes look like in Python, but otherwise don't worry about it.  This implementation allows loops but not multiple edges.\n",
    "\n",
    "Below is a simple example illustrating its basic functionality:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from graphs import Graph # This line imports the Graph class from graphs.py; you won't be able to use it otherwise\n",
    "\n",
    "G = Graph(3) # Create a new graph with vertices 0, 1, and 2\n",
    "\n",
    "G.addVertex(\"cat\") # Add a new vertex called \"cat\"\n",
    "\n",
    "# Add an edge from cat to each other vertex\n",
    "for i in range(3):\n",
    "    G.addEdge(\"cat\", i)\n",
    "\n",
    "print(G) # Display the graph G by listing each vertex and its list of neighbors\n",
    "\n",
    "print(G.numVertices()) # Number of vertices\n",
    "print(G.numEdges()) # Number of edges\n",
    "\n",
    "print(G.neighbors(\"cat\")) # Print cat's list of neighbors\n",
    "print(G.degree(0)) # Print degree of vertex 0\n",
    "\n",
    "# Remove vertex 1 and all of its incident edges\n",
    "G.removeVertex(1)\n",
    "\n",
    "# Remove the edge from cat to 0\n",
    "G.removeEdge(\"cat\", 0)\n",
    "\n",
    "print(\"\")\n",
    "\n",
    "print(G)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5\n",
    "\n",
    "Run the block of code below and draw a picture of the graph from the output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from graphs import Graph\n",
    "\n",
    "G = Graph(4)\n",
    "for v in range(3):\n",
    "    G.addEdge(v, (v + 1) % 3)\n",
    "G.addVertex(\"v\")\n",
    "G.addEdge(\"v\", 2)\n",
    "\n",
    "print(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 6\n",
    "\n",
    "Write a function `Path(` $n$ `)` which returns a path of length $n$, i.e. a graph with vertices $0, 1, \\ldots, n$ and edges $01, 12, \\ldots, (n - 1)n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from graphs import Graph\n",
    "\n",
    "def Path(n):\n",
    "    G = Graph(n + 1) # Why n + 1 and not n?\n",
    "    \n",
    "    # To do: add edges!\n",
    "    \n",
    "    return G\n",
    "\n",
    "print(Path(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7\n",
    "\n",
    "Write a function `Cycle(` $n$ `)` which returns a cycle of length $n$.  Be sure to test your code.\n",
    "\n",
    "Hint: a cycle of length $n$ is a path of length $n - 1$, plus one extra edge.  Use your function from the previous exercise!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from graphs import Graph\n",
    "\n",
    "# Your code here\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 8\n",
    "\n",
    "Write a function `CompleteGraph(` $n$ `)` which returns the complete graph $K_n$.  This graph should have all possible edges EXCEPT loops."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from graphs import Graph\n",
    "\n",
    "# Your code here\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 9\n",
    "\n",
    "Write a function `RandomGraph(` $n$ `)` which returns a *random graph* on $n$ vertices.  By this I mean the following:\n",
    "* Create an empty graph with $n$ vertices.\n",
    "* For each *possible* edge $uv$, not including loops, simulate a coin flip using `random.randInt(0, 1)`.\n",
    "* If heads (i.e. 1), add edge $uv$.\n",
    "* Be careful to try each pair only once (i.e., don't flip a coin for both $uv$ and $vu$)!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from graphs import Graph\n",
    "\n",
    "# Your code here\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 10\n",
    "\n",
    "Write a function `isWalk(` $G, W$ `)` which takes a graph $G$ and a list of vertices $W$ and returns `True` iff. $W$ represents a walk in $G$.  This means that each pair of consecutive elements of $W$ must be an edge in $G$.\n",
    "\n",
    "Hint: iterate through the list until you find a pair that's not an edge; if you make it all the way through, return `True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from graphs import Graph\n",
    "\n",
    "# Your code here\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 11\n",
    "\n",
    "Similarly, write functions `isPath(` $G, W$ `)`, `isCircuit(` $G, W$ `)`, and `isCycle(` $G, W$ `)` based on the definitions we covered in class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from graphs import Graph\n",
    "\n",
    "# Your code here\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 12\n",
    "\n",
    "Write a function `randomWalk(` $G, k, v$ `)` which computes a *random walk* of length $k$ in $G$, starting with vertex $v$.  In other words, start at $v$, and randomly bounce along the edges of $G$.  More formally, at each step, pick a random neighbor of the current vertex and move to that vertex.  Add the vertices visited to a list as you go along, and have your function return the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from graphs import Graph\n",
    "\n",
    "# Your code here\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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}