{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# EE16A Homework 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sports Rank"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from scipy import ndimage as nd\n",
    "from scipy import misc\n",
    "from scipy import io"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook we will implement the power iteration method to find the dominant eigenvector of a matrix. For the matrix in consideration the dominant eigenvector will correspond to a ranking of the top 25 teams in College football for the 2014 regular season.\n",
    "\n",
    "\n",
    "\n",
    "First we load the wins of all the teams into a matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Creating W (win) Matrix\n",
    "W=np.zeros([26,26])\n",
    "\n",
    "\n",
    "#Alabama\n",
    "count=0\n",
    "W[count,[7,15,18,21]]=1\n",
    "W[count,25]=8.0\n",
    "Teams={count:'ALA'}\n",
    "count=count+1\n",
    "\n",
    "#FSU\n",
    "Teams.update({count:'FSU'})\n",
    "W[1,[9,17,19]]=1\n",
    "W[1,25]=10.0\n",
    "count=count+1\n",
    "\n",
    "#Oregon\n",
    "Teams.update({count:'ORE'})\n",
    "W[2,[6,11,13,22]]=1\n",
    "W[2,25]=8.0\n",
    "count=count+1\n",
    "\n",
    "#Baylor\n",
    "Teams.update({count:'BAY'})\n",
    "W[3,[5,10]]=1\n",
    "W[3,25]=9.0\n",
    "count=count+1\n",
    "\n",
    "#OSU\n",
    "Teams.update({count:'OSU'})\n",
    "W[4,[6,16]]=1\n",
    "W[4,25]=10.0\n",
    "count=count+1\n",
    "\n",
    "#TCU\n",
    "Teams.update({count:'TCU'})\n",
    "W[5,[10]]=1\n",
    "W[5,25]=10.0\n",
    "count=count+1\n",
    "\n",
    "#MSU\n",
    "Teams.update({count:'MSU'})\n",
    "W[6,[24]]=1\n",
    "W[6,25]=9.0\n",
    "count=count+1\n",
    "\n",
    "#MSST\n",
    "Teams.update({count:'MSST'})\n",
    "W[7,[18,21]]=1\n",
    "W[7,25]=8.0\n",
    "count=count+1\n",
    "\n",
    "#MISS\n",
    "Teams.update({count:'MISS'})\n",
    "W[8,[0,7,20]]=1\n",
    "W[8,25]=6.0\n",
    "count=count+1\n",
    "\n",
    "#GT\n",
    "Teams.update({count:'GT'})\n",
    "W[9,[17,12]]=1\n",
    "W[9,25]=8.0\n",
    "count=count+1\n",
    "\n",
    "#KSU\n",
    "Teams.update({count:'KSU'})\n",
    "W[count,25]=9.0\n",
    "count=count+1\n",
    "\n",
    "#ARIZ\n",
    "Teams.update({count:'ARIZ'})\n",
    "W[count,[2,22,14]]=1\n",
    "W[count,25]=7.0\n",
    "count=count+1\n",
    "\n",
    "#UGA\n",
    "Teams.update({count:'UGA'})\n",
    "W[count,[17,15,18]]=1\n",
    "W[count,25]=6.0\n",
    "count=count+1\n",
    "\n",
    "#UCLA\n",
    "Teams.update({count:'UCLA'})\n",
    "W[count,[14,11,23]]=1\n",
    "W[count,25]=6.0\n",
    "count=count+1\n",
    "\n",
    "#ASU\n",
    "Teams.update({count:'ASU'})\n",
    "W[count,[23,22]]=1\n",
    "W[count,25]=7.0\n",
    "count=count+1\n",
    "\n",
    "#MIZZ\n",
    "Teams.update({count:'MIZZ'})\n",
    "W[count,25]=10.0\n",
    "count=count+1\n",
    "\n",
    "#WISC\n",
    "Teams.update({count:'WISC'})\n",
    "W[count,[24]]=1\n",
    "W[count,25]=9.0\n",
    "count=count+1\n",
    "\n",
    "#CLEM\n",
    "Teams.update({count:'CLEM'})\n",
    "W[count,[19]]=1\n",
    "W[count,25]=8.0\n",
    "count=count+1\n",
    "\n",
    "#AUB\n",
    "Teams.update({count:'AUB'})\n",
    "W[count,[10,8,21]]=1\n",
    "W[count,25]=5.0\n",
    "count=count+1\n",
    "\n",
    "#LOU\n",
    "Teams.update({count:'LOU'})\n",
    "W[count,25]=9.0\n",
    "count=count+1\n",
    "\n",
    "#BSU\n",
    "Teams.update({count:'BSU'})\n",
    "W[count,25]=11.0\n",
    "count=count+1\n",
    "\n",
    "#LSU\n",
    "Teams.update({count:'LSU'})\n",
    "W[count,[16,8]]=1\n",
    "W[count,25]=6.0\n",
    "count=count+1\n",
    "\n",
    "#UTAH\n",
    "Teams.update({count:'UTAH'})\n",
    "W[count,[13,23]]=1\n",
    "W[count,25]=6.0\n",
    "count=count+1\n",
    "\n",
    "\n",
    "#USC\n",
    "Teams.update({count:'USC'})\n",
    "W[count,[11]]=1\n",
    "W[count,25]=7.0\n",
    "count=count+1\n",
    "\n",
    "#NEB\n",
    "Teams.update({count:'NEB'})\n",
    "W[count,25]=9.0\n",
    "count=count+1\n",
    "\n",
    "#OTHERS\n",
    "Teams.update({count:'Others'})\n",
    "W[count,[3,4,8,13,14,15,16,18,19,20,21,22,23,24]]=1\n",
    "W[count,[9,12]]=2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Creating Q matrix (accounts for normalization by games played)\n",
    "\n",
    "numrows,numcols=W.shape\n",
    "Q=np.zeros([numrows,numcols])\n",
    "\n",
    "for j in range(0,numrows):\n",
    "    Q[j,:]=W[j,:]/(np.sum(W[:,j])+np.sum(W[j,:])) #sum over column j plus sum over row j is games played by team j\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we discussed earlier the power iteration method can be used to find the dominant eigenvector of a matrix $Q$. If we denote the dominant eigenvector as $\\vec{v_D}$ then we showed that for almost any vector $\\vec{b}$, $\\lim_{n\\to\\infty}  \\frac{Q^n\\vec{b}}{|Q^n\\vec{b}|}=\\frac{c_1\\vec{v}_D}{|c\\vec{v}_D|}$, where $c$ is a nonzero constant. For numerical reasons, it is better to perform this method iteratively: Take the sequance $\\vec{b}_{k+1}=\\frac{Q\\vec{b_k}}{|Q\\vec{b_k}|}$ with $\\vec{b}_0=\\vec{b}$, in the limit it  converges to $\\frac{c_1\\vec{v}_D}{|c_1\\vec{v}_D|}$, i.e.$\\lim_{n\\to\\infty}\\vec{b}_n=\\frac{c\\vec{v}_D}{||c_1\\vec{v}_D||}$. This iterative procedure is precisely the power iteration method.\n",
    "\n",
    "In the next block you will implement the power iteration method. The b vector has already been intialized for you, all you need to do is update it in the for loop, $\\vec{b} \\leftarrow \\frac{Q\\vec{b}}{|Q\\vec{b}|}$. The following functions might be useful:\n",
    "np.dot(A,x) - takes a matrix A and multiplies it by a vector x\n",
    "and np.linalg.norm(x) - returns the norm of a vector x.\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Power Iteration Method\n",
    "\n",
    "#initializing b\n",
    "b = np.ones(numrows)\n",
    "\n",
    "for j in range(0,500):\n",
    "    ### Your code goes here \n",
    "    #In python you must indent any lines in side the for loop\n",
    "    \n",
    "\n",
    "\n",
    "###Don't forget to do this    \n",
    "#set v_D equal to your result\n",
    "    \n",
    "v_D=b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Create rankings\n",
    "\n",
    "v_D=np.absolute(v_D)\n",
    "indices=np.argsort(v_D)\n",
    "ratings=np.sort(v_D)\n",
    "indices=indices[25::-1]\n",
    "\n",
    "ratings=ratings[25::-1]\n",
    "\n",
    "#Printing teams (in order) and their score\n",
    "print('Team','Score')\n",
    "for j in range(0,26):\n",
    "    print(Teams[indices[j]], ratings[j])\n",
    "    "
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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.4.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}