mynotes_chap02.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Latex Header Section: Skip\n",
    "$$\n",
    "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
    "%\n",
    "%  The following are some simple LaTeX macros to give some\n",
    "%  commonly used letters in funny fonts. You may need more or less of\n",
    "%  these\n",
    "%\n",
    "\\newcommand{\\R}{\\mathbb{R}}\n",
    "\\newcommand{\\Q}{\\mathbb{Q}}\n",
    "\\newcommand{\\C}{\\mathbb{C}}\n",
    "\\newcommand{\\N}{\\mathbb{N}}\n",
    "\\newcommand{\\F}{\\mathbb{F}}\n",
    "\\newcommand{\\PP}{\\mathbb{P}}\n",
    "\\newcommand{\\T}{\\mathbb{T}}\n",
    "\\newcommand{\\Z}{\\mathbb{Z}}\n",
    "\\newcommand{\\B}{\\mathfrak{B}}\n",
    "\\newcommand{\\BB}{\\mathcal{B}}\n",
    "\\newcommand{\\M}{\\mathfrak{M}}\n",
    "\\newcommand{\\X}{\\mathfrak{X}}\n",
    "\\newcommand{\\Y}{\\mathfrak{Y}}\n",
    "\\newcommand{\\CC}{\\mathcal{C}}\n",
    "\\newcommand{\\E}{\\mathbb{E}}\n",
    "\\newcommand{\\cP}{\\mathcal{P}}\n",
    "\\newcommand{\\cS}{\\mathcal{S}}\n",
    "\\newcommand{\\A}{\\mathcal{A}}\n",
    "\\newcommand{\\ZZ}{\\mathcal{Z}}\n",
    "\\newcommand{\\cN}{\\mathcal{N}}\n",
    "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
    "%\n",
    "% The following are much more esoteric commands that I have left in\n",
    "% so that this file still processes. Use or delete as you see fit\n",
    "%\n",
    "\\newcommand{\\bv}[1]{\\mbox{BV($#1$)}}\n",
    "\\newcommand{\\comb}[2]{\\left(\\!\\!\\!\\begin{array}{c}#1\\\\#2\\end{array}\\!\\!\\!\\right)\n",
    "}\n",
    "\\newcommand{\\Lat}{{\\rm Lat}}\n",
    "\\newcommand{\\var}{\\mathop{\\rm var}}\n",
    "\\newcommand{\\Pt}{{\\mathcal P}}\n",
    "\\def\\tr(#1){{\\rm trace}(#1)}\n",
    "\\def\\Exp(#1){{\\mathbb E}(#1)}\n",
    "\\def\\Exps(#1){{\\mathbb E}\\sparen(#1)}\n",
    "\\newcommand{\\floor}[1]{\\left\\lfloor #1 \\right\\rfloor}\n",
    "\\newcommand{\\ceil}[1]{\\left\\lceil #1 \\right\\rceil}\n",
    "\\newcommand{\\hatt}[1]{\\widehat #1}\n",
    "\\newcommand{\\modeq}[3]{#1 \\equiv #2 \\,(\\text{mod}\\, #3)}\n",
    "\\newcommand{\\rmod}{\\,\\mathrm{mod}\\,}\n",
    "\\newcommand{\\p}{\\hphantom{+}}\n",
    "\\newcommand{\\vect}[1]{\\mbox{\\boldmath $ #1 $}}\n",
    "\\newcommand{\\reff}[2]{\\ref{#1}.\\ref{#2}}\n",
    "\\newcommand{\\psum}[2]{\\sum_{#1}^{#2}\\!\\!\\!'\\,\\,}\n",
    "\\newcommand{\\bin}[2]{\\left( \\begin{array}{@{}c@{}}\n",
    "\t\t\t\t#1 \\\\ #2\n",
    "\t\t\t\\end{array}\\right)}\n",
    "%\n",
    "%  Macros - some of these are in plain TeX (gasp!)\n",
    "%\n",
    "\\newcommand{\\be}{($\\beta$)}\n",
    "\\newcommand{\\eqp}{\\mathrel{{=}_p}}\n",
    "\\newcommand{\\ltp}{\\mathrel{{\\prec}_p}}\n",
    "\\newcommand{\\lep}{\\mathrel{{\\preceq}_p}}\n",
    "\\def\\brack#1{\\left \\{ #1 \\right \\}}\n",
    "\\def\\bul{$\\bullet$\\ }\n",
    "\\def\\cl{{\\rm cl}}\n",
    "\\let\\del=\\partial\n",
    "\\def\\enditem{\\par\\smallskip\\noindent}\n",
    "\\def\\implies{\\Rightarrow}\n",
    "\\def\\inpr#1,#2{\\t \\hbox{\\langle #1 , #2 \\rangle} \\t}\n",
    "\\def\\ip<#1,#2>{\\langle #1,#2 \\rangle}\n",
    "\\def\\lp{\\ell^p}\n",
    "\\def\\maxb#1{\\max \\brack{#1}}\n",
    "\\def\\minb#1{\\min \\brack{#1}}\n",
    "\\def\\mod#1{\\left \\vert #1 \\right \\vert}\n",
    "\\def\\norm#1{\\left \\Vert #1 \\right \\Vert}\n",
    "\\def\\paren(#1){\\left( #1 \\right)}\n",
    "\\def\\qed{\\hfill \\hbox{$\\Box$} \\smallskip}\n",
    "\\def\\sbrack#1{\\Bigl \\{ #1 \\Bigr \\} }\n",
    "\\def\\ssbrack#1{ \\{ #1 \\} }\n",
    "\\def\\smod#1{\\Bigl \\vert #1 \\Bigr \\vert}\n",
    "\\def\\smmod#1{\\bigl \\vert #1 \\bigr \\vert}\n",
    "\\def\\ssmod#1{\\vert #1 \\vert}\n",
    "\\def\\sspmod#1{\\vert\\, #1 \\, \\vert}\n",
    "\\def\\snorm#1{\\Bigl \\Vert #1 \\Bigr \\Vert}\n",
    "\\def\\ssnorm#1{\\Vert #1 \\Vert}\n",
    "\\def\\sparen(#1){\\Bigl ( #1 \\Bigr )}\n",
    "%\n",
    "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
    "%\n",
    "% These environments allow you to get nice numbered headings\n",
    "%  for your Theorems, Definitions etc.  \n",
    "%\n",
    "%  Environments\n",
    "%\n",
    "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
    "%\n",
    "%\\newtheorem{theorem}{Theorem}[section]\n",
    "%\\newtheorem{lemma}[theorem]{Lemma}\n",
    "%\\newtheorem{proposition}[theorem]{Proposition}\n",
    "%\\newtheorem{corollary}[theorem]{Corollary}\n",
    "%\\newtheorem{conjecture}[theorem]{Conjecture}\n",
    "%\\newtheorem{definition}[theorem]{Definition}\n",
    "%\\newtheorem{example}[theorem]{Example}\n",
    "%\\newtheorem{remark}[theorem]{Remark}\n",
    "%\\newtheorem{question}[theorem]{Question}\n",
    "%\\newtheorem{notation}[theorem]{Notation}\n",
    "%\\numberwithin{equation}{section}\n",
    "%\n",
    "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
    "%\n",
    "%  If you've got some funny special words that LaTeX might not\n",
    "% hyphenate properly, you can give it a helping hand:\n",
    "%\n",
    "%\n",
    "%\\hyphenation{Mar-cin-kie-wicz Rade-macher}\n",
    "%\n",
    "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
    "%\n",
    "% Commands for easier typing\n",
    "%\n",
    "\\newcommand{\\code}[1]{\\texttt{#1}}\n",
    "\\newcommand{\\tit}[1]{\\textit{#1}}\n",
    "\\newcommand{\\tbf}[1]{\\textbf{#1}}\n",
    "\\newcommand{\\mbf}[1]{\\mathbf{#1}}\n",
    "\\newcommand{\\mbb}[1]{\\mathbb{#1}}\n",
    "\\newcommand{\\bs}[1]{\\boldsymbol{#1}}\n",
    "\\newcommand{\\bigo}[1]{\\mathcal{O}\\left(#1\\right)}\n",
    "%\n",
    "\\renewcommand{\\thefootnote}{\\fnsymbol{footnote}}\n",
    "%\n",
    "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
    "%\n",
    "% Other cnetralised settings for easy access\n",
    "%\n",
    "%\n",
    "%\\graphicspath{ {./images/} }\n",
    "%\\DeclareGraphicsExtensions{.pdf,.png,.jpg}\n",
    "\\DeclareMathOperator*{\\argmin}{argmin}\n",
    "\\DeclareMathOperator*{\\argmax}{argmax}\n",
    "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n",
    "%\n",
    "% New commands\n",
    "%\n",
    "\\newcommand{\\norm}[1]{\\left\\lVert#1\\right\\rVert}\n",
    "\\newcommand{\\phdot}{\\mathrel{\\,\\cdot\\,}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 2 - The Vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We saw in Chapter 1 that the field of complex numbers makes it simple to describe transformations on points in the plane, such as translations, rotations, and scalings.\n",
    "\n",
    "Josiah Willard Gibbs developed _vector analysis_ as an alternative to quaternions (by Sir William Rowan Hamilton)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1 What is a vector?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The word _vector_ comes from the Latin for \"carrier\". The term comes from a vector's propensity to move something from one location to another.\n",
    "\n",
    "In some traditional math courses on linear algebra, we are taught to think of a vector as a _list of numbers_:\n",
    "$$\n",
    "[3.14159, 2.718281828, -1.0, 2.0]\n",
    "$$\n",
    "\n",
    "We need to know this way of writing a vector because it is commonly used. Indeed, we will sometimes represent vectors using Python's _lists_.\n",
    "\n",
    "**Definition 2.1.1:** A vector with four entires, each of which is a real number, is called a _4-vector over_ $\\R$.\n",
    "\n",
    "The entries of a vector must all be drawn from a single field. Three examples of fields are $\\R$, $\\C$ and _GF_(2). We can therefore have vectors over each of these fields.\n",
    "\n",
    "**Definition 2.1.2:** For a field $\\F$ and a positive integer $n$, a vector with $n$ entries, each belonging to $\\F$, is called a _n-vector over_ $\\F$. The set of $n$-vectors over $\\F$ is denoted $\\F^n$.\n",
    "\n",
    "For example, the set of 4-vectors over $\\R$ is written $\\R^4$.\n",
    "\n",
    "The above definition reminds us of the notation $\\F^D$ for the set of _functions_ from $D$ to $\\F$. Indeed, the author suggests us interpret $\\F^d$ as shorthand for $\\F^{\\{0, 1, 2, 3, \\dots, d - 1\\}}$. According to this interpretation, $\\F^d$ is the set of functions from $\\{0, 1, 2, \\dots, d - 1\\}$ to $\\F$.\n",
    "\n",
    "For example, the 4-vector $[3.14159, 2.718281828, -1.0, 2.0]$ is in fact the function\n",
    "$$\n",
    "\\begin{align}\n",
    "0 & \\mapsto 3.14159\\\\\n",
    "1 & \\mapsto 2.718281828\\\\\n",
    "2 & \\mapsto -1.0\\\\\n",
    "3 & \\mapsto 2.0\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2 Vectors are functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we embrace this interpretation - once we accept that vectors are functions - a world of new applications opens to us.\n",
    "\n",
    "**Example 2.2.1: Documents as vectors:** _WORDS-vector over_ $\\R$.\n",
    "\n",
    "**Definition 2.2.2:** For a finite set $D$ and a field $\\F$, a _$D$-vector over_ $\\F$ is a __function__ from $D$ to $\\F$.\n",
    "\n",
    "This is a computer scientist's definition; it lends itself to representation in a data structure. It differs in two important ways from a mathematician's definition.\n",
    "\n",
    "* The domain $D$ is required to be finite. This has important mathematical consequences: the author states theorems that would not be true if $D$ were allowed to be infinite. There are mathematical questions that are best modelled using functions with _infinite_ domains.\n",
    "* The traditional, abstract approach to linear algebra does not directly define vectors at all. Just as field is defined as a set of values with some operations $(+, -, *, /)$ that satisfy certain algebraic laws, a vector space is defined as a set with some operations that satisfy certain algebraic laws; then vectors are the elements in the set. This approach is more general but more abstract, hence harder for someone to grasp.\n",
    "\n",
    "Returning to the more concrete approach, according to the notation from Section 0.3.3, we use $\\F^D$ to denote the _set of functions_ with domain $D$ and co-domain $\\F$, i.e. the set of all _$D$-vectors over_ $\\F$.\n",
    "\n",
    "**Example 2.2.3:**\n",
    "\n",
    "(b) $GF(2)^{\\{0, 1, \\dots, n - 1\\}}$: The set of all $n$-vectors over $GF(2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.2.1 Representation of vectors using Python dictionaries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will sometimes use Python's lists to represent vectors. However, the author has decreed that a vector is a _function with **finite** domain_, and Python's dictionaries are a convenient representation of functions with finite domain. Therefore, the author uses dictionaries in representing vectors.\n",
    "\n",
    "Representing vectors using Python dictionaries in some cases can be profligate. Instead, the author adopts the convention of allowing the omission of key-value pairs whose values are zero. This is called a _sparse representation_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2.2 Sparsity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A vector most of whose values are zero is called a _sparse vector_. If no more than $k$ of the entries are nonzero, we say the vector is _k-sparse_. A $k$-sparse vector can be represented using space proportional to $k$. Therefore, for example, when we represent a corpus of documents by WORD-vectors, the storage required is proportional to the total number of words comprising all the documents.\n",
    "\n",
    "Vectors that represent data acquired via physical sensors (e.g. images or sound) are not likely to be sparse. In a future chapter, the author introduces a computational problem in which the goal, given a vector and a parameter $k$, is to find the \"closest\" $k$-sparse vector. After we have learned what it means for vectors to be close, it will be straightforward to solve this computational problem.\n",
    "\n",
    "A solution to this computational problem would seem to be the key to _compressing_ images and audio segments, i.e. representing them compactly so more can be stored in the same amount of computer memory. This is correct, but there is a hitch: unfortunately, the vectors representing images or sound are not even close to sparse vectors. In Section 5.2, the author indicates the way around this obstacle. In Chapter 10, he explores some compression schemes based on the idea.\n",
    "\n",
    "n Chapter 4, the author introduces matrices and their representation. Because matrices are often sparse, in order to save on storage and computational time he will again use a dictionary representation in which zero values need _not_ be represented.\n",
    "\n",
    "However, many matrices arising in real-world problems are not sparse in the obvious sense. In Chapter 11, the author investigates another form of sparsity for matrices, _low rank_. Low-rank matrices arise in analysing data to discover factors that explain the data. He considers a computational problem in which the goal, given a matrix and a parameter $k$, is to find the closest matrix whose rank is at most $k$. We show that linear algebra provides a solution for this computational problem. It is at the heart of a widely used method called _principal component analysis_, and we will explore some of its applications."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 2.3 What can we represent with vectors?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Binary string**\n",
    "\n",
    "**Attributes**\n",
    "\n",
    "**State of a system**\n",
    "\n",
    "**Probability distribution** Since a finite probability distribution is a function from a _finite domain_ to the real numbers, e.g.\n",
    "\n",
    "`{1:1/6, 2:1/6, 3:1/6, 4:1/6, 5:1/6, 6:1/6}`,\n",
    "\n",
    "it can be considered a vector. We will see in Chapter 12 that linear algebra provides a way to analyse a random process that evolves over time according to simple probabilistic rules. One such random process underlies the original definition of PageRank, the method by which Google ranks pages.\n",
    "\n",
    "**Image** A black-and-white 1024 x 768 image can be viewed as a function from the set of pairs $\\left\\{(i, j): 0 \\le i < 1024, 0 \\le j < 768\\right\\}$ to the real numbers, and hence as a vector. The pixel-coordinate pair $(i, j)$ maps to a number, called the intensity of pixel $(i, j)$. We will study several applications of representing images by vectors, e.g. subsampling, blurring, searching for a specified subimage, and face detection.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.4 Vector addition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have seen examples of what vectors can represent. Now we study the operations performed with vectors. We have seen that vectors are useful for representing geometric points. The concept of a vector originated in _geometry_, and it is in the context of _geometry_ that the basic vector operations are most easily motivated. We start with _vector addition_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4.1 Translation and vector addition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "We saw in Chapter 1 that _translation_ was achieved in the complex plane by a function $f(z) = z_0 + z$ that adds a complex number $z_0$ to its input complex number; here we similarly achieve translation by a function $f(\\bs v) = \\bs v_0 + \\bs v$ that adds a vector to its input vector.\n",
    "\n",
    "**Definition 2.4.1:** Addition of $n$-vectors is defined in terms of addition of corresponding entries.\n",
    "\n",
    "**Question:** What is the best way to code this operation overloading in Python?\n",
    "\n",
    "Since a vector such as $[1, 2]$ corresponds to a translation, we can think of the vector as \"carrying\" something from one point to another. This is the sense in which a vector is a carrier."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 2.4.3:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def add2(v, w): return([v[0] + w[0], v[1] + w[1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "L = [[2, 2], [3, 2], [1.75, 1], [2, 1], [2.25, 1], [2.5, 1], [2.75, 1], [3, 1], [3.25, 1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from plotting import plot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plot(L, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plot([add2(v, [1,2]) for v in L], 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.4.4:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def addn(v, w): return([v[i] + w[i] for i in range(len(v))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def addn(v, w): return([x + y for (x, y) in zip(v, w)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def multiplyn(v, w): return([x * y for (x, y) in zip(v, w)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "L1 = [1, 2, 3]\n",
    "L2 = [-1, -2, -3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 0]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "addn(L1, L2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, -4, -9]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "multiplyn(L1, L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Every field $\\F$ has a zero element, so the set $\\F^D$ of $D$-vectors over $\\F$ necessarily has a _zero vector_, whose entries all have value zero. This _zero vector_ is denoted by $\\bs 0_D$ or merely by $\\bs 0$ if it is unnecessary to specify $D$.\n",
    "\n",
    "The function $f(\\bs v) = \\bs v + \\bs 0$ is a translation that leaves its input _unchanged_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4.2 Vector addition is associative and commutative"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since vector addition is defined in terms of associative and commutative operation, it too is associative and commutative."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4.3 Vectors as arrows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Like complex numbers in the plane, $n$-vector over $\\R$ can be visualised as arrows in $\\R^n$.\n",
    "\n",
    "Vector addition can be interpreted as composition of translations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.5 Scalar-vector multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We saw in Chapter 1 that _scaling_ could be represented in the complex plane by a function $f(z) = rz$ that multiplies its complex-number input by a positive real number $r$, and that multiplying by a negative number achieves a simultaneous scaling and rotation by 180 degrees. The analogous operation for vectors is called _scalar-vector multiplication_. In the context of vectors, a _field element_ (e.g. a number) is called a _scalar_ because it can be used to _scale_ a vector via multiplication. In this book, the author typically uses Greek letters (e.g. $\\alpha, \\beta, \\gamma$) to denote scalars."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.5.3:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def scalar_vector_mult(alpha, v): return [alpha * x for x in v]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def scalar_vector_mult(alpha, v): return [alpha * v[i] for i in range(len(v))]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 2.5.4:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from plotting import plot\n",
    "\n",
    "L = [[2, 2], [3, 2], [1.75, 1], [2, 1], [2.25, 1], [2.5, 1], [2.75, 1], [3, 1], [3.25, 1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plot([scalar_vector_mult(0.5, x) for x in L], 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "plot([scalar_vector_mult(-0.5, x) for x in L], 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.5.1 Scaling arrows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scaling a vector over $\\R$ by a positive real number changes the length of the corresponding arrow without changing its direction.\n",
    "\n",
    "The vector `[3, 1.5]` corresponds to the translation $f(\\bs v) = [3, 1.5] + \\bs v$, and two times this vector (`[6, 3]`) corresponds to a translation in the same direction but twice as far.\n",
    "\n",
    "3]) corresponds to a translation in the same direction but twice as far. Multiplying a vector by a negative number negates all the entries. As we have seen in connection with complex numbers, this reverses the direction of the corresponding arrow."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5.2 Associativity of scalar-vector multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The associativity stems from the field's associative law."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5.3 Line segments through the origin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from plotting import plot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v = [3, 2]\n",
    "plot([scalar_vector_mult(i/10, v) for i in range(11)], 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The plot seems to be tracing out the line segment from the origin to the point `(3, 2)`. The set of points\n",
    "\n",
    "$$\n",
    "\\{\\alpha \\bs v: \\alpha\\in\\R,\\, 0\\le \\alpha\\le 1\\}\n",
    "$$\n",
    "\n",
    "\n",
    "forms the line segment between the origin and $\\bs v$. We can visualise this by plotting not all such points (even Python lacks the power to process an uncountably infinite set of points) but a sufficiently dense sample, say a hundred points:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "plot([scalar_vector_mult(i/100, v) for i in range(101)], 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5.4 Lines through the origin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As long as we have permitted an infinite set of scales, let's go all out. What shape do we obtain when $\\alpha$ ranges over all real numbers? The scalars bigger than 1 give rise to somewhat larger copies of $\\bs v$. The negative scalars give rise to vectors pointing in the opposite direction. Putting these together, we see that the points of\n",
    "$$\n",
    "\\{\\alpha\\bs v:\\,\\alpha\\in\\R\\}\n",
    "$$\n",
    "forms the (infinite) _line through the **origin**_ and through $\\bs v$.\n",
    "\n",
    "**Review question:** Express the line segment between the origin and another point $\\bs v$ through the origin (two end points given) as a set of scalar multiples of a single vector. \n",
    "$$\n",
    "\\left\\{\\alpha\\bs v:\\,\\alpha\\in\\R, 0\\le\\alpha\\le 1\\right\\}\n",
    "$$\n",
    "\n",
    "**Review question:** Express a line through origin as the set of scalar multiples of a single vector $\\bs v$.\n",
    "$$\n",
    "\\left\\{\\alpha\\bs v:\\,\\alpha\\in\\R\\right\\}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 2.6 Combining vector addition and scalar multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.6.1 Line segments and lines that don't go through the origin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great - we can describe the set of points forming a line or line segment through the _origin_. We already know that the points forming the segment from $(0, 0)$ to $(3, 2)$ are $\\left\\{\\alpha(3, 2):\\,\\alpha\\in\\R, 0\\le\\alpha\\le 1\\right\\}$. Accordingly, we can plot the line segment using the following statements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from plotting import plot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "plot([addn(scalar_vector_mult(i/100, [3, 2]), [0.5, 1]) for i in range(101)], 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can similarly represent the _entire_ line through two given points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2.6.1:** Given points $\\bs u = (2, 3)$ and $\\bs v = (5, 7)$ in $\\R^2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\bs w = \\bs v - \\bs u = (5, 7) - (2, 3) = (3, 4)$ is the point such that the origin-to-$\\bs w$ line segment can be translated to yield the $\\bs u$-to-$\\bs v$ line segment. Further, the translation vector applied to both end points is $\\bs u = (2, 3)$ itself."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2.6.2:** Given a pair of points, $\\bs u = (1, 4)$ and $\\bs v = (6, 3)$ in $\\R^2$, write a mathematical\n",
    "expressing giving the set of points making up the line segment between the points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\left\\{\\bs u + \\alpha(\\bs v - \\bs u):\\,0\\le\\alpha\\le 1\\right\\} = \\left\\{(1, 4) + \\alpha(5, -1):\\,0\\le\\alpha\\le 1\\right\\}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.6.2 Distributive laws for scalar-vector multiplication vector addition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get a better understanding of this formulation of line segments and lines, we make use of two properties that arise in combining scalar-vector multiplication and vector addition. Both arise from the distributive law for fields, $x(y + z) = xy + xz$.\n",
    "\n",
    "**Proposition 2.6.3 (Scalar-vector multiplication distributes over vector addition):**\n",
    "$$\n",
    "\\alpha(\\bs u + \\bs v) = \\alpha\\bs u + \\alpha\\bs v\n",
    "$$\n",
    "\n",
    "**Proposition 2.6.5 (scalar-vector multiplication distributes over scalar addition):**\n",
    "$$\n",
    "(\\alpha + \\beta)\\bs u = \\alpha\\bs u + \\beta\\bs u\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.6.3 First look at convex combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It might seem odd that the form of the expression for the set of points making up a line segment $\\left\\{\\alpha(3, 2) + (0.5, 1):\\,\\alpha\\in\\R, 0\\le\\alpha\\le 1\\right\\}$, mentions one endpoint but not the other. This asymmetry is infelicitous. Using a bit of vector algebra, we can obtain a nicer expression:\n",
    "$$\n",
    "\\begin{align}\n",
    "\\alpha (3, 2) + (0.5, 1) & = \\alpha ((3.5, 3) - (0.5, 1)) + (0.5, 1)\\\\\n",
    " & = \\alpha (3.5, 3) + (1 - \\alpha)(0.5, 1)\\\\\n",
    " & = \\alpha (3.5, 3) + \\beta (0.5, 1)\n",
    "\\end{align}\n",
    "$$\n",
    "where $\\beta = 1 - \\alpha$. Now we can write an expression for the `(0.5,1)`-to-`(3.5,3)` segment\n",
    "$$\n",
    "\\left\\{\\alpha(3.5, 3) + \\beta(0.5, 1):\\,\\alpha, \\beta \\in \\R,\\, \\alpha, \\beta \\ge 0,\\,\\alpha + \\beta = 1\\right\\}\n",
    "$$\n",
    "that is _symmetric_ in two endpoints.\n",
    "\n",
    "An expression of the form $\\alpha\\bs u + \\beta\\bs v$ where $\\alpha + \\beta = 1$ is called a _convex combination_ of $\\bs u$ and $\\bs v$.\n",
    "\n",
    "**Proposition 2.6.7:** The $\\bs u$-to-$\\bs v$ line segment consists of the set of convex combinations of $\\bs u$ and $\\bs v$.\n",
    "\n",
    "**Task 2.6.9:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def addn(v, w): return [x + y for (x, y) in zip(v, w)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def minusn(v, w): return [x - y for (x, y) in zip(v, w)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def scalar_vector_mult(alpha, v): return [alpha * v[i] for i in v]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# NOT working: there must be a better way!\n",
    "def segment(pt1, pt2, steps = 100):\n",
    "    return [addn(pt1, step) for step in range(pt1, pt2 + (pt2 - pt1)/steps, (pt2 - pt1)/steps)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def segment(pt1, pt2):\n",
    "    steps = 100\n",
    "    pt1s, pt2s = [pt1[0] + i/steps * (pt2[0] - pt1[0]) for i in range(steps + 1)], [pt1[1] + i/steps * (pt2[1] - pt1[1]) for i in range(steps + 1)]\n",
    "    \n",
    "    return(list(zip(pt1s, pt2s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(3.5, 3.0),\n",
       " (3.47, 2.98),\n",
       " (3.44, 2.96),\n",
       " (3.41, 2.94),\n",
       " (3.38, 2.92),\n",
       " (3.35, 2.9),\n",
       " (3.32, 2.88),\n",
       " (3.29, 2.86),\n",
       " (3.26, 2.84),\n",
       " (3.23, 2.82),\n",
       " (3.2, 2.8),\n",
       " (3.17, 2.78),\n",
       " (3.14, 2.76),\n",
       " (3.11, 2.74),\n",
       " (3.08, 2.7199999999999998),\n",
       " (3.05, 2.7),\n",
       " (3.02, 2.68),\n",
       " (2.99, 2.66),\n",
       " (2.96, 2.64),\n",
       " (2.9299999999999997, 2.62),\n",
       " (2.9, 2.6),\n",
       " (2.87, 2.58),\n",
       " (2.84, 2.56),\n",
       " (2.81, 2.54),\n",
       " (2.7800000000000002, 2.52),\n",
       " (2.75, 2.5),\n",
       " (2.7199999999999998, 2.48),\n",
       " (2.69, 2.46),\n",
       " (2.66, 2.44),\n",
       " (2.63, 2.42),\n",
       " (2.6, 2.4),\n",
       " (2.5700000000000003, 2.38),\n",
       " (2.54, 2.36),\n",
       " (2.51, 2.34),\n",
       " (2.48, 2.32),\n",
       " (2.45, 2.3),\n",
       " (2.42, 2.2800000000000002),\n",
       " (2.39, 2.26),\n",
       " (2.36, 2.24),\n",
       " (2.33, 2.2199999999999998),\n",
       " (2.3, 2.2),\n",
       " (2.27, 2.18),\n",
       " (2.24, 2.16),\n",
       " (2.21, 2.14),\n",
       " (2.1799999999999997, 2.12),\n",
       " (2.15, 2.1),\n",
       " (2.12, 2.08),\n",
       " (2.09, 2.06),\n",
       " (2.06, 2.04),\n",
       " (2.0300000000000002, 2.02),\n",
       " (2.0, 2.0),\n",
       " (1.97, 1.98),\n",
       " (1.94, 1.96),\n",
       " (1.91, 1.94),\n",
       " (1.88, 1.92),\n",
       " (1.8499999999999999, 1.9),\n",
       " (1.8199999999999998, 1.88),\n",
       " (1.79, 1.86),\n",
       " (1.7600000000000002, 1.84),\n",
       " (1.73, 1.82),\n",
       " (1.7000000000000002, 1.8),\n",
       " (1.67, 1.78),\n",
       " (1.6400000000000001, 1.76),\n",
       " (1.6099999999999999, 1.74),\n",
       " (1.58, 1.72),\n",
       " (1.5499999999999998, 1.7),\n",
       " (1.52, 1.68),\n",
       " (1.4899999999999998, 1.66),\n",
       " (1.46, 1.64),\n",
       " (1.4300000000000002, 1.62),\n",
       " (1.4000000000000004, 1.6),\n",
       " (1.37, 1.58),\n",
       " (1.3399999999999999, 1.56),\n",
       " (1.31, 1.54),\n",
       " (1.2800000000000002, 1.52),\n",
       " (1.25, 1.5),\n",
       " (1.2199999999999998, 1.48),\n",
       " (1.19, 1.46),\n",
       " (1.1600000000000001, 1.44),\n",
       " (1.13, 1.42),\n",
       " (1.0999999999999996, 1.4),\n",
       " (1.0699999999999998, 1.38),\n",
       " (1.04, 1.36),\n",
       " (1.0100000000000002, 1.34),\n",
       " (0.98, 1.32),\n",
       " (0.9500000000000002, 1.3),\n",
       " (0.9199999999999999, 1.28),\n",
       " (0.8900000000000001, 1.26),\n",
       " (0.8599999999999999, 1.24),\n",
       " (0.8300000000000001, 1.22),\n",
       " (0.7999999999999998, 1.2),\n",
       " (0.77, 1.18),\n",
       " (0.7399999999999998, 1.16),\n",
       " (0.71, 1.14),\n",
       " (0.6800000000000002, 1.12),\n",
       " (0.6500000000000004, 1.1),\n",
       " (0.6200000000000001, 1.08),\n",
       " (0.5899999999999999, 1.06),\n",
       " (0.56, 1.04),\n",
       " (0.5300000000000002, 1.02),\n",
       " (0.5, 1.0)]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pt1 = [3.5, 3]\n",
    "pt2 = [0.5, 1]\n",
    "\n",
    "segment(pt1, pt2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from plotting import plot\n",
    "\n",
    "plot(segment(pt1, pt2), 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 2.6.10:** We consider convex combinations of a pair of vectors that represent images. By using images as frames in a video, we get the effect of a crossfade."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.6.4 First look at affine combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What about the _infinite line_ through two points, e.g. $(0.5, 1)$ and $(3.5, 3)$? We already saw that this line consists of the points $\\left\\{(0.5, 1) + \\alpha(3, 2):\\:\\alpha\\in\\R\\right\\}$. Using a similar argument, we can rewrite this set as\n",
    "$$\n",
    "\\left\\{\\alpha(3.5, 3) + \\beta(0.5, 1):\\:\\alpha\\in\\R,\\,\\beta\\in\\R,\\,\\alpha + \\beta = 1\\right\\}\n",
    "$$\n",
    "An expression of the form $\\alpha\\bs u + \\beta\\bs v$ where $\\alpha + \\beta = 1$ is called an _affine_ combination of $\\bs u$ and $\\bs v$.\n",
    "\n",
    "**Hypothesis 2.6.11:** The _line through_ $\\bs u$ and $\\bs v$ consists of the set of _affine combinations_ of $\\bs u$ and $\\bs v$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** The definitions of affine and convex combinations dictate that affine combinations are more general than their convex counterparts. Geometrically, line segments are part of the infinite line through the same set of points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.7 Dictionary-based representations of vectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The author has proposed in Section 2.2 that a vector is a _function_ from some domain $D$ to a field that can be represented using a Python dictionary. It is convenient to define a Python class `Vec` so that an instance has two fields (a.k.a. _instance variables_ or _attributes_):\n",
    "\n",
    "* `f`, the function, represented by a Python dictionary, and\n",
    "* `D`, the domain of the function, represented by a Python set.\n",
    "\n",
    "We also adopt the convention that entries with zero values may be _omitted_ from the dictionary `f`. This enables sparse vectors to be represented _compactly_.\n",
    "\n",
    "It might seem a bad idea to require that each instance of `Vec` keep track of the domain. Fortunately, Python allows many variables (or instance variables) to point to the same set in memory. Thus, if we are careful, we can ensure that all the vectors representing documents point to the same domain.\n",
    "\n",
    "The Python code required to define the class `Vec` is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Vec:\n",
    "    def __init__(self, labels, function):\n",
    "        self.D = labels\n",
    "        self.f = function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# create an instance of Vec:\n",
    "v = Vec({'A', 'B', 'C'}, {'A': 1})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "# subsequently access the two fields\n",
    "for d in v.D:\n",
    "    if d in v.f:\n",
    "        print(v.f[d])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.7.1:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exploiting the sparse-representation convention, we can write the procedure like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def zero_vec(D): return Vec(D, {}) # {} means empty dict, not empty set (use set() instead)s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Without the convention, one could write:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def zero_vec(D): return(Vec(D, {d:0 for d in D}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The procedure `zero_vec(D)` is defined in the provided file `vecutil.py`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.7.1 Setter and getter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following quizzes, we will write procedures that work with the _class-based_ representation of vectors. In a later problem, we will incorporate some of these procedures into a module that defines the class `Vec`. \n",
    "\n",
    "The following procedure can be used to assign a value to a specified entry of a `Vec v`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def setitem(v, d, val): v.f[d] = val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second argument `d` should be a member of the domain `v.D`. The procedure can be used, for example, as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "setitem(v, 'B', 2.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.0\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# print out v\n",
    "for d in v.D:\n",
    "    if d in v.f:\n",
    "        print(v.f[d])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Quiz 2.7.2:**\n",
    "\n",
    "Write the procedure in a way that takes into account the _sparse-representation_ convention."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# warning: the procedure below is incorrect because the domain D can be larger than v.f\n",
    "def getitem(v, d): return v.f[d] if d in v.D else 0 # conditional expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# the procedure can be written in one-line using a conditional expression\n",
    "def getitem(v, d): return v.f[d] if d in v.f else 0 # conditional expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getitem(v, 'A')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getitem(v, 'Z')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# using an if-statement - slightly longer\n",
    "def getitem(v, d):\n",
    "    if d in v.f: # similar to above: cannot simply put `if d in v.D`\n",
    "        return v.f[d]\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.7.2 Scalar-vector multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.7.3:**\n",
    "\n",
    "There is a nice way to ensure that the output vector is as _sparse_ as the input vector, but we do not have to ensure this. We can use `getitem(v, d)` but not required to. Be careful to ensure that our procedure does not modify the vector it is passed as argument; it should create a new instance of `Vec`. However, the new instance should point to the same set D as the old instance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# warning: below is incorrect as it modifies the old argument vector\n",
    "def scalar_mul(v, alpha):\n",
    "    v_new = Vec(v.D, v.f)\n",
    "    for k in v_new.f: # no need to put `for k in v_new.f.keys():`\n",
    "        setitem(v_new, k, alpha * v_new.f[k]) # incorrect: modifies the old argument vector\n",
    "    return v_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Vec at 0x7f85d03925c0>"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scalar_mul(v, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': 4, 'B': 8.0}"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scalar_mul(v, 2).f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# instead, the one line below\n",
    "def scalar_mul(v, alpha): return Vec(v.D, {d:alpha * v.f[d] for d in v.f}) # do not have to write `for k in v.f.keys()'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': 8, 'B': 16.0}"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scalar_mul(v, 2).f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# does not preserve sparsity:\n",
    "def scalar_mul(v, alpha): return Vec(v.D, {d:alpha * getitem(v, d) for d in v.D})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# on the other hand, to preserve sparsity\n",
    "def scalar_mul(v, alpha): return Vec(v.D, {d:alpha * val for d, val in v.f.items()})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': 8, 'B': 16.0}"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "scalar_mul(v, 2).f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.7.3 Addition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.7.4:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# this is an advanced version of the answer given by the author\n",
    "# note that set unior operator `|` can only be applied to sets, not dictionaries and that's why `.keys()` was used\n",
    "def add(u, v): return Vec(u.D, {d: getitem(u, d) + getitem(v, d) for d in (u.f.keys() | v.f.keys()) })"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "u = Vec(v.D, {'A':5, 'C':10})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': 9, 'B': 8.0, 'C': 10}"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add(u, v).f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.7.4 Vector negative, invertibility of vector addition, and vector subtraction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The _negative_ of a vector $\\bs v$ is the vector $-\\bs v$ obtained by negating _each element_ of $\\bs v$. If we\n",
    "interpret $\\bs v$ as an arrow, its negative $-\\bs v$ is the arrow of the same length pointed in the exactly opposite direction.\n",
    "\n",
    "If we interpret $\\bs v$ as the translation, its negative is the inverse translation. Applying one translation and its inverse leaves us back where we started.\n",
    "\n",
    "Vector subtraction is defined in terms of vector addition and negative: $\\bs u - \\bs v$ is defined as $\\bs u + (-\\bs v)$. This definition is obviously equivalent to the definition of vector subtraction: subtract corresponding elements.\n",
    "\n",
    "Vector subtraction is the inverse of vector addition. For some vector $\\bs w$, consider the functions\n",
    "$$\n",
    "f_{\\bs w}(\\bs v) = \\bs v + \\bs w\n",
    "$$\n",
    "and\n",
    "$$\n",
    "g_{\\bs w}(\\bs v) = \\bs v - \\bs w\n",
    "$$\n",
    "\n",
    "One function translates its input by $\\bs w$ and the other translates its input by $-\\bs w$. These two functions are inverses of each other. Indeed,\n",
    "$$\n",
    "\\begin{align}\n",
    "(g\\circ f)(\\bs v) & = g(f(\\bs v))\\\\\n",
    "& = g(\\bs v + \\bs w)\\\\\n",
    "& = \\bs v + \\bs w - \\bs w\\\\\n",
    "& = \\bs v\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Quiz 2.7.5:**\n",
    "\n",
    "Note the output of this function should be an instance of `Vec`, instead of a dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# create an instance of Vec:\n",
    "v = Vec({'A', 'B', 'C', 'D', 'E'}, {'A':1, 'B':0, 'C':3, 'D':4})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# preserves sparsity\n",
    "def neg(v): return Vec(v.D, {key:-val for key, val in v.f.items()}) # iterate over dictionary items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': -1, 'B': 0, 'C': -3, 'D': -4}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neg(v).f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# also preserves sparsity\n",
    "def neg(v): return Vec(v.D, {d:-getitem(v, d) for d in v.f})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': -1, 'B': 0, 'C': -3, 'D': -4}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neg(v).f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# even shorter version: why re-invent the wheel  \n",
    "def neg(v): return scalar_mul(v, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A': -1, 'B': 0, 'C': -3, 'D': -4}"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "neg(v).f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.8 Vector over _GF_(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Review**\n",
    "\n",
    "So far we have studied only vectors over $\\R$. In this section, we consider vectors over _GF_(2). Remember from Section 1.5 that _GF_(2) is a field in which the only values are 0 and 1. Adding 1 and 1 gives 0, and subtracting is the same as adding.\n",
    "\n",
    "For the sake of brevity, we will sometimes write specific $n$-vector over _GF_(2) as $n$-bit binary strings. For example, we write 1101 for the 4-vector whose only zero is in its third entry."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.8.1:** _GF_(2) _vector addition practice_: What is 1101 + 0111? (Note: it is the same as 1101 - 0111.)\n",
    "\n",
    "1101 + 0111 = 1010 = 1101 - 0111."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.8.1 Perfect secrecy re-revisited"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The encryption process described in Section 1.5.1 can be expressed more compactly using addition of vectors over _GF_(2).\n",
    "\n",
    "Suppose Alice needs to send a ten-bit plaintext $\\bs p$ to Bob."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Vernam's Cypher:** Alice and Bob randomly choose a 10-vector $\\bs k$. Alice computes the cyphtertext $\\bs c$ according to the formula\n",
    "$$\n",
    "\\bs c = \\bs p + \\bs k\n",
    "$$\n",
    "where the sum is a _vector_ sum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The firtt thing to check is that this cryptosystem is decryptable so that Bob, who knows $\\bs k$ and $\\bs c$, can recover $\\bs p$. He does so using the equation\n",
    "$$\n",
    "\\bs p = \\bs c - \\bs k\n",
    "$$\n",
    "\n",
    "Next we check that the system satisfies perfect secrecy. The argument is similar. For each plaintext $\\bs p$, the function $\\bs k \\mapsto \\bs k + \\bs p$ is _one-to-one_ and _onto_, hence **invertible**. The key $\\bs k$ is chosen _uniformly_ at random; therefore, the cyphertext $\\bs c$ is also distributed uniformly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.8.2 All-or-nothing secret-sharing using _GF_(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The company RSA introduced a producted named RSA Distributed Credential Protection (DCP) based on this idea."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem 2.8.3:** Explain how to share an $n$-bit secret among _three_ TAs so that a cabal consisting of any _two_ of them learns nothing about the secret."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.8.3 Lights Out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.9 Dot-product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "For example, for traditoinal vectors $\\bs u = (u_1, \\dots, u_n)$ and $\\bs v = (v_1, \\dots, v_n)$, their dot product is defined as\n",
    "\n",
    "$$\n",
    "\\bs u \\cdot \\bs v = u_1v_1 + u_2v_2 + \\cdots + u_nv_n\n",
    "$$\n",
    "\n",
    "Note that the output is a scalar, not a vector. For this reason, the dot-product is sometimes called the _scalar product_ of the vectors. This _collapsing_ nature of dot product gave rise to another more official/general name: **inner product**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 2.9.1:**\n",
    "\n",
    "In general, the dot-product of an all-ones vector with a second vector equals the sum of entries of the second vector."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example 2.9.2:**\n",
    "\n",
    "In general, if only one entry of $\\bs u$, say the $i$th entry, is 1, and all other entries of $\\bs u$ are entries, $\\bs u \\cdot \\bs v$ is the $i$th entry of $\\bs v$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.9.3:** Express the average of the entries of an $n$-vector $\\bs v$ as a dot-product."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\frac{\\bs 1 \\cdot \\bs v}{n}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.9.4:**\n",
    "\n",
    "Use the `sum()` procedure together with a list comprehension."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# preferred method\n",
    "def list_dot(u, v): return sum([x * y for x, y in zip(u, v)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# slightly longer\n",
    "def list_dot(u, v): return sum([u[i] * v[i] for i in range(len(u))])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note how the sum and average of all elements in a vector can be achieved using the fundamental operation: dot product. Dot product is the \"**executive summary**\" of a vector. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.9.1 Total cost or benefit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.9.2 Linear equations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Definition 2.9.6:** A _linear equation_ is an equation of the form $\\bs a\\cdot \\bs x = \\beta$, where $\\bs a$ is a vector, $\\beta$ is a scalar and $\\bs x$ is a vector variable.\n",
    "\n",
    "In addition, the \"**row** view\" of a matrix is represented as the dot product in above definition.\n",
    "\n",
    "Questions about systems/collections of linear equations:\n",
    "\n",
    "* Is there a solution to the system of linear equations?\n",
    "* Is there exactly one solution?\n",
    "\n",
    "**Why bother?** Even if there is an algorithm to compute _some_ vector that satisfies the linear equations, we cannot be sure that the solution we have computed is in fact the vector we are seeking unless there is only one solution to the system of linear equations.\n",
    "\n",
    "**Definition 2.9.10:** In general, a _system of linear equations_ (often abbreviated _linear system_) is a collection of equations:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\bs a_1 \\cdot \\bs x & = \\beta_1\\\\\n",
    "\\bs a_2 \\cdot \\bs x & = \\beta_2\\\\\n",
    "& \\vdots\\\\\n",
    "\\bs a_m \\cdot \\bs x & = \\beta_m\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "where $\\bs x$ is a vector variable. A _solution_ is a vector $\\hat{\\bs x}$ that satisfies *all* the equations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.9.3 Measuring similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dot-product can be used to measure the _similarity_ between vectors over $\\R$.\n",
    "\n",
    "**Comparing voting records**\n",
    "\n",
    "A positive sum indicates general agreement, and a negative sum indicates general disagreement.\n",
    "\n",
    "**Comparing audio segments**\n",
    "\n",
    "How would we go about searching for the needle (the short audio clip) in the long segment (the haystack)?\n",
    "\n",
    "In preparation, we consider a simpler problem: measuring the similarity between audio segments of the same length.\n",
    "\n",
    "Mathematically, an audio segment is a _waveform_, a _continuous function of time_ whose value is _amplitude_. The amplitude oscillates between a positive and negative number depending on the time. What's more, how positive and negative depends on the volume of the audio.\n",
    "\n",
    "On a digital computer, the audio segment is represented by a sequence of numbers, values of the continuous function _sampled_ at regular time intervals, e.g. 44,100 times a second.\n",
    "\n",
    "Note: This is the _finite_ representation (also an **approximation**) of a continuous function in real world, though we do not have much choice here.\n",
    "\n",
    "Let's first consider the task of comparing two audio segments of equal length. Suppose they consist of $n$ samples, represented as $n$-vectors $\\bs u$ and $\\bs v$.\n",
    "\n",
    "One simple way to compare them is using dot-product $\\sum_{i=1}^n \\bs u_i \\bs v_i$. Thus, once again, the greater the agreement, the greater the value of the dot-product.\n",
    "\n",
    "Nearly identical audio segments (even if they differ in loudness) will produce a higher value than different segments. However, the bad news is that if the two segments are even slightly off in tempo or pitch, the dot-product will be small, probably close to zero. (There are other techniques to address differences of this kind.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Finding an audio clip**\n",
    "\n",
    "Back to the problem of finding a needle (a short audio clip) in a haystack (a long audio segment).\n",
    "\n",
    "We can evaluate each of the possibilities by computing an appropriate dot-product, e.g. a sliding window scheme.\n",
    "\n",
    "In this example, the long segment consists of 23 numbers and the short clip 11 numbers, so we end up with $23 - 11 + 1 = 13$ dot-products. We put these 13 numbers in an output vector."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.9.13:** Haystack is `[1, -1, 1, 1, 1, -1, 1, 1, 1]` and the needle is `[1, -1, 1, 1, -1, 1]`.\n",
    "\n",
    "The dot-product vector is `[2, 2, 0, 0]`. Hence, the best matches start at position 0 and 1 of the haystack."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.9.14:** This method of searching is not universally applicable. Say we wanted to locate the short clip `[1, 2, 3]` in the longer segment `[1, 2, 3, 4, 5, 6]`. What would the dot-product method select as the best match?\n",
    "\n",
    "The dot-product vector is `[14, 20, 26, 32]`. By this measure, the best match is to start at 4, which is obviously incorrect."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Quiz 2.9.15:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def dot_product_list(needle, haystack): return [list_dot(needle, haystack[i:(i + len(needle))]) for i in range(len(haystack) - len(needle) + 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The following function is the answer given by the author in the book.\n",
    "# As suspected, the parameter in range() is short of 1 such that the resulting list misses one one element, i.e. the last.\n",
    "def dot_product_list(needle, haystack):\n",
    "    s = len(needle)\n",
    "    return [list_dot(needle, haystack[i:i+s]) for i in range(len(haystack) - s)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[14, 20, 26, 32]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## Capitalise on previous quizzes to verify above function.\n",
    "# Quiz 2.9.14\n",
    "haystack = [1, 2, 3, 4, 5, 6]\n",
    "needle = [1, 2, 3]\n",
    "dot_product_list(needle, haystack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 0]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Quiz 2.9.13\n",
    "haystack = [1, -1, 1, 1, 1, -1, 1, 1, 1]\n",
    "needle = [1, -1, 1, 1, -1, 1]\n",
    "dot_product_list(needle, haystack)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**First look at linear filters**\n",
    "\n",
    "As in Section 2.9.3, we compared a short needle to a slice of a long haystack by turning the slice into a vector and taking the dot-product of the slice with the needle. Here is another way to achieve the same goal: we turn the needle into a longer vector by padding it with zeros, and then calculate the dot-product of the padded vector with the haystack (they are of equal length).\n",
    "\n",
    "We can similarly compute the dot-products corresponding to other alignments of the needle vector with the haystack vector. This process is an example of applying a _linear filter_. The short clip plays the role of the _kernel_ of the filter. In more realistic examples, this calculation could be computationally expensive. Fortunately, computational shortcuts will be introduced in later chapters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.9.4 Dot-product of vectors over _GF_(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general, when you take the dot-product of an all-ones vector with a second vector, the resulting value is the _parity_ of the second vector: 0 if the number of ones is even and 1 if odd. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.9.5 Parity bit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When data are stored or transmitted, errors can occur. Often a system is designed to detect such errors if they occur infrequently. The most basic method of error detection is a _parity check bit_. To reliably transmit an $n$-bit sequence, one computes one additional bit, the parity bit, as the parity of the $n$-bit sequence, and sends that along with the $n$-bit sequence.\n",
    "\n",
    "For example, the PCI (Peripheral Component Interconnect) bus in a computer has PAR line that transmits the parity bit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.9.6 Simple authentication scheme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This scheme essentially capitalises on the row interpretation/picture of solving systems of linear equations via matrix vector multiplication, i.e. dot-products."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.9.7 Attacking the simple authentication scheme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Understanding which ones  of the variables are unknown from a problem solver's point of view is crucial for this kind of exercise. This simple authentication scheme is framed as a system of linear equations and thus can be interpreted as dot-products."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.9.8 Algebraic properties of the dot-product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section the author introduces some simple but powerful algebraic properties of the dot-product that hold regardless of the choice of field (e.g. $\\R$ or _GF_(2)).\n",
    "\n",
    "**Commutativity**\n",
    "\n",
    "**Homogeneity**\n",
    "\n",
    "**Distributivity**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.9.9 Attacking the simple authentication scheme, revisited"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.10 Our implementation of `Vec`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.10.1 Syntax for manipulating `Vec`s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will expand our class definition of `Vec` to provide some notational conveniences. In addition, if an expression has as a result of a `Vec` instance, the value of the expression will be presented not as an obscure Python incantation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Vec at 0x7f44e81a22b0>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.10.2 The implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.10.3 Using `Vec`s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will write the bodies of named procedures such as `setitem(v, d, val)` and `add(u, v)` and `scalar_mul(v, alpha)`. However, in actually using `Vec`s in other code, we must use operators instead of named procedures.\n",
    "\n",
    "In fact, in code outside the `vec` module that uses `Vec`, we will import just `Vec` from the `vec` module: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from vec import Vec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "so the named procedures will not be imported into the namespace. Those named procedures in the `vec` module are intended to be used _only_ inside the `vec` module itself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "v = Vec({'A', 'B', 'C', 'D', 'E'}, {'A':1, 'B':0, 'C':3, 'D':4})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.10.4 Printing `Vec`s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The class `Vec` defines a procedure that turns an instance into a string for the purpose of printing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " A B C D E\n",
      "----------\n",
      " 1 0 3 4 0\n"
     ]
    }
   ],
   "source": [
    "print(v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The procedure for pretty-printing a vector `v` must select some order on the domain `v.D`. Ours uses `sorted(v.D, key = hash)`, which does something reasonable on tuples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.10.5 Copying `Vec`s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `Vec` class defines a `.copy()` method that is called on an instance of `Vec` and returns a new instance equal to the old instance. It shares the domain `.D` with the old instance but has a new function `.f` that is initialised by the old instance.\n",
    "\n",
    "Ordinarily we do not have to copy `Vec`s. The scalar-vector multiplication and vector addition operations return new instances of `Vec` and do not mutate their inputs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.10.6 From list to `Vec`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `Vec` class is a useful way of representing vectors, but it is not the only such representation. As mentioned before, we sometimes represent vectors by lists. A list `L` can be viewed as a function, mapping `{0, 1, 2, len(L) - 1}` to corresponding vector element values, so it is possible to convert from a list-based representation to a dictionary-based representation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quiz 2.10.1:** Write a procedure `list2vec(L)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "## The first argument of Vec class has to be a set, thus the set() wrapper.\n",
    "def list2vec(L): return Vec(set(range(len(L))), {i:L[i] for i in range(len(L))})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# or\n",
    "def list2vec(L): return Vec(set(range(len(L))), {key:val for key, val in enumerate(L)})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "l = ['A', 'B', 'C', 'D']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " 0 1 2 3\n",
      "--------\n",
      " A B C D\n"
     ]
    }
   ],
   "source": [
    "print(list2vec(l))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 2.11 Solving a triangular system of linear equations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.11.1 Upper-triangular systems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.11.2 Backward substitution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This suggests a solution strategy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.11.3 First implementation of backward substitution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is a convenient way to express this algorithm in terms of _vectors_ and _dot-products_. The procedure initialises the solution vector $x$ to the all-zeros vector and populates $x$ entry by entry, starting at the last entry. Hence, by the time entry $x_i$ is to be populated, entries $x_{i+1},x_{i+2},\\cdots,x_n$ have already been populated and other entries are zero. This is why we can use a dot-product to calculate the part of the expression that involves variables whose values are already known."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Quiz 2.7.1\n",
    "def zero_vec(D): return Vec(D, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def triangular_solve_n(rowlist, b):\n",
    "    D = rowlist[0].D\n",
    "    n = len(D)\n",
    "    assert D == set(range(n))\n",
    "    x = zero_vec(D)\n",
    "    for i in reversed(range(n)):\n",
    "        x[i] = (b[i] - rowlist[i] * x)/rowlist[i][i]\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2.11.4:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "label_list = list(range(3))\n",
    "D = set(label_list)\n",
    "# rl = [[2, 3, -4],b[0, 1, 2], [0, 0, 5]]\n",
    "row_list = [Vec(D, {0:2, 1:3, 2:-4}), Vec(D, {1:1, 2:2}), Vec(D, {2:5})]\n",
    "b = [10, 3, 15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Vec({0, 1, 2},{0: 15.5, 1: -3.0, 2: 3.0})"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "triangular_solve_n(row_list, b)\n",
    "# agrees with answer given"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2.11.3:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Vec({0, 1, 2},{0: 17.8, 1: 4.4, 2: -1.2})"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "row_list = [Vec(D, {0:1, 1:-3, 2:-2}), Vec(D, {1:2, 2:4}), Vec(D, {2:-10})]\n",
    "b = [7, 4, 12]\n",
    "triangular_solve_n(row_list, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.11.4 When does the algorithm work?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.11.5 Backward substitution with arbitrary-domain vectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def triangular_solve(row_list, label_list, b):\n",
    "    D = row_list[0].D\n",
    "    x = zero_vec(D)\n",
    "    for j in reversed(range(len(D))):\n",
    "        c = label_list[j]\n",
    "        row = row_list[j]\n",
    "        x[c] = (b[j] - x * row)/row[c]\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Vec({'b', 'a', 'd', 'c'},{'b': 1.9000000000000004, 'd': -4.0, 'a': 3.2750000000000004, 'c': 1.4})"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "label_list = ['a', 'b', 'c', 'd']\n",
    "D = set(label_list)\n",
    "row_list = [Vec(D, {'a':4, 'b':-2, 'c':0.5, 'd':1}), Vec(D, {'b':2, 'c':3, 'd':3}),\n",
    "           Vec(D, {'c':5, 'd':1}), Vec(D, {'d':2})]\n",
    "b = [6, -4, 3, -8]\n",
    "triangular_solve(row_list, label_list, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The procedures triangular `solve(rowlist, label list, b)` and `triangular_solve_n(rowlist, b)` are provided in the module `triangular`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.12 Lab: Comparing voting records using dot-product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this lab, we are asked to represent a US senator's voting record as a vector over $\\R$ and use dot-products to compare voting records. For the purpose of this lab, we will just use a list to represent a vector."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.12.1 Motivation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now is the time for linear algebra.\n",
    "\n",
    "In this lab, we will use vectors to evaluate objectively the political mindset of the senators who represent us. Each senator's voting record can be represented as a vector, where each element of that vector represents how that senator voted on a given piece of legislation. By\n",
    "looking at the difference between the \"voting vectors\" of two senators, we can dispel the fog of politics and see just where our representatives stand, or rather, stood."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Data dictionary:\n",
    "\n",
    "* 1: 'yea'\n",
    "* -1: 'nay'\n",
    "* 0: abstention"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 2.12.1:** Write a procedure `create_voting_dict(strlist)` that, given a list of `strings` (voting records from the source file), returns a dictionary that maps the last name of a senator to a list of numbers representing that senator's voting record. You will need to\n",
    "use the built-in procedure `int()` to convert a string representation of an integer (e.g. `'1'`) to the actual integer (e.g. `1`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Akaka D HI -1 -1 1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 1 0 0 1 -1 -1 1 -1 1 -1 1 1 -1\\n',\n",
       " 'Alexander R TN 1 1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1\\n',\n",
       " 'Allard R CO 1 1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\\n',\n",
       " 'Allen R VA 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\\n',\n",
       " 'Baucus D MT -1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 -1 1 1 0 1 1 1 1 1 1 1 -1 1 0 1 1 -1 1 1 1\\n',\n",
       " 'Bayh D IN 1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 0 1 1 -1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 0 1 -1 1 -1 1 1 -1 1 1 -1\\n',\n",
       " 'Bennett R UT 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\\n',\n",
       " 'Biden D DE -1 -1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1 1 -1 -1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 -1 1 1 -1\\n',\n",
       " 'Bingaman D NM 1 0 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 1 1 1 -1 1 -1 -1 1 -1 1 -1 1 1 -1\\n',\n",
       " 'Bond R MO 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\\n']"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = open('voting_record_dump109.txt')\n",
    "my_list = list(f)\n",
    "my_list[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['-1',\n",
       " '-1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '-1',\n",
       " '-1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '-1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '-1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '-1',\n",
       " '1',\n",
       " '-1',\n",
       " '-1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '1',\n",
       " '0',\n",
       " '0',\n",
       " '1',\n",
       " '-1',\n",
       " '-1',\n",
       " '1',\n",
       " '-1',\n",
       " '1',\n",
       " '-1',\n",
       " '1',\n",
       " '1',\n",
       " '-1\\n']"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "my_list[0].split(' ')[3:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def create_voting_dict(strlist):\n",
    "    d = {}\n",
    "    for str in strlist:\n",
    "        lst = str.split(' ')\n",
    "        d[lst[0]] = [int(vote.strip('\\n')) for vote in lst[3:]]\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "voting_dict = create_voting_dict(my_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vitter => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Lautenberg => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Carper => [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Murray => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Hutchison => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Roberts => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "DeWine => [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1]\n",
      "DeMint => [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Dorgan => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1]\n",
      "Ensign => [1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1]\n",
      "Cornyn => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Boxer => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 0, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1]\n",
      "Domenici => [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Leahy => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 0, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 0, -1, -1, 1, -1, 1, -1, 1, 1, -1]\n",
      "Allard => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Clinton => [-1, 1, 1, 1, 0, 0, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Brownback => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Bennett => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Levin => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, -1, -1]\n",
      "Sessions => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Thomas => [1, 0, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]\n",
      "Murkowski => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Inouye => [-1, -1, 1, 0, 1, 1, -1, 1, 0, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 0, 1, 0, -1, 1, 1, -1]\n",
      "Alexander => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]\n",
      "Reid => [-1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Kennedy => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 0, 1, -1, 0, 1, -1, 1, -1, 1, 1, -1]\n",
      "Inhofe => [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1, 1, 1]\n",
      "Gregg => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Lieberman => [1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Burns => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Chambliss => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Nelson1 => [-1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Cantwell => [1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Bingaman => [1, 0, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, -1, 1, -1, 1, 1, -1]\n",
      "Feingold => [-1, -1, 1, -1, 1, -1, -1, -1, 1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, -1, 1, -1, 1, 1, -1]\n",
      "Sarbanes => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Chafee => [1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Harkin => [-1, -1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 0, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1]\n",
      "Santorum => [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Smith => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Byrd => [-1, -1, 1, -1, 1, 1, -1, 0, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1]\n",
      "Crapo => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Jeffords => [1, -1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 0, 1, -1, 1, 1, -1]\n",
      "Kyl => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Burr => [1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1]\n",
      "Schumer => [1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 0, 1, 1, -1, 1, 1, 1]\n",
      "Grassley => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "McCain => [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, -1, 0, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]\n",
      "Graham => [1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Dole => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Johnson => [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1]\n",
      "Bunning => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Wyden => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Collins => [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Bond => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Bayh => [1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 0, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 0, 1, -1, 1, -1, 1, 1, -1, 1, 1, -1]\n",
      "Dodd => [1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 0, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Rockefeller => [1, 1, 1, 1, 1, -1, -1, 0, 1, 0, 1, 0, 1, 1, -1, 1, 0, 1, -1, 0, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 0, -1, 1, 1, -1]\n",
      "Salazar => [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 0, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Voinovich => [1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1]\n",
      "Allen => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Thune => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Lugar => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Lincoln => [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Akaka => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 0, 0, 1, -1, -1, 1, -1, 1, -1, 1, 1, -1]\n",
      "Enzi => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, 0, 1, 1, 1, 1, 1, 1, -1, -1, 0, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Landrieu => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Stevens => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Hatch => [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Coleman => [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Cochran => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Specter => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Nelson2 => [1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Warner => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Feinstein => [1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Snowe => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 0, 1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Kohl => [1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Coburn => [1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 0, 1, -1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Conrad => [1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1]\n",
      "Biden => [-1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Durbin => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Isakson => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Talent => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Craig => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1]\n",
      "Obama => [1, -1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Martinez => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "McConnell => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Frist => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Mikulski => [-1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 0, 1, 0, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Reed => [1, -1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Shelby => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]\n",
      "Baucus => [-1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, -1, 1, 0, 1, 1, -1, 1, 1, 1]\n",
      "Lott => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]\n",
      "Dayton => [-1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, -1, 1, -1, 1, 1, 1]\n",
      "Hagel => [1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "Stabenow => [-1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 0, 1, 1, 1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1]\n",
      "Kerry => [-1, -1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1]\n",
      "Pryor => [-1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1]\n",
      "Sununu => [0, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, 1, 1, -1, 0, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "for key, val in voting_dict.items():\n",
    "    print(key + \" => \" + str(val))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.12.3 Why use dot-product to compare vectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.12.4 Policy comparison"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We would like to determine how like-minded two given senators are by computing the dot-product of vectors $\\bs u$ and $\\bs v$ to judge how often two senators are in agreements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 2.12.2:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def list_dot(u, v): return sum([x * y for x, y in zip(u, v)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def policy_compare(sen_a, sen_b, voting_dict): return list_dot(voting_dict[sen_a], voting_dict[sen_b])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "34"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "policy_compare('Obama', 'Clinton', voting_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "36"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "policy_compare('Obama', 'Biden', voting_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "policy_compare('Obama', 'McCain', voting_dict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 2.12.3:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def most_similar(sen, voting_dict):\n",
    "    # initialisation: setting up the stage\n",
    "    max_dp = -math.inf\n",
    "    sen_ms = \"\"\n",
    "    sen_votes = voting_dict[sen]\n",
    "    \n",
    "    for s, v in voting_dict.items():\n",
    "        dp = list_dot(sen_votes, v)\n",
    "        if (dp > max_dp and s != sen):\n",
    "            max_dp = dp\n",
    "            sen_ms = s\n",
    "    return (sen_ms, max_dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senator Kerry is most similar to Obama with dot-product 42.\n"
     ]
    }
   ],
   "source": [
    "senator = \"Obama\"\n",
    "sen_ms, max_dp = most_similar(senator, voting_dict)\n",
    "print(\"Senator \" + sen_ms + \" is most similar to \" + senator + \" with dot-product \" + str(max_dp) + \".\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senator Baucus is most similar to Clinton with dot-product 42.\n"
     ]
    }
   ],
   "source": [
    "senator = \"Clinton\"\n",
    "sen_ms, max_dp = most_similar(senator, voting_dict)\n",
    "print(\"Senator \" + sen_ms + \" is most similar to \" + senator + \" with dot-product \" + str(max_dp) + \".\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senator Gregg is most similar to McCain with dot-product 38.\n"
     ]
    }
   ],
   "source": [
    "senator = \"McCain\"\n",
    "sen_ms, max_dp = most_similar(senator, voting_dict)\n",
    "print(\"Senator \" + sen_ms + \" is most similar to \" + senator + \" with dot-product \" + str(max_dp) + \".\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 2.12.4:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def least_similar(sen, voting_dict):\n",
    "    # initialisation: setting up the stage\n",
    "    min_dp = math.inf\n",
    "    sen_ls = \"\"\n",
    "    sen_votes = voting_dict[sen]\n",
    "    \n",
    "    for s, v in voting_dict.items():\n",
    "        dp = list_dot(sen_votes, v)\n",
    "        if (dp < min_dp and s != sen):\n",
    "            min_dp = dp\n",
    "            sen_ls = s\n",
    "    return (sen_ls, min_dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senator Sununu is least similar to Obama with dot-product 7.\n"
     ]
    }
   ],
   "source": [
    "senator = \"Obama\"\n",
    "sen_ls, min_dp = least_similar(senator, voting_dict)\n",
    "print(\"Senator \" + sen_ls + \" is least similar to \" + senator + \" with dot-product \" + str(min_dp) + \".\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senator Coburn is least similar to Clinton with dot-product 7.\n"
     ]
    }
   ],
   "source": [
    "senator = \"Clinton\"\n",
    "sen_ls, min_dp = least_similar(senator, voting_dict)\n",
    "print(\"Senator \" + sen_ls + \" is least similar to \" + senator + \" with dot-product \" + str(min_dp) + \".\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senator Leahy is least similar to McCain with dot-product 4.\n"
     ]
    }
   ],
   "source": [
    "senator = \"McCain\"\n",
    "sen_ls, min_dp = least_similar(senator, voting_dict)\n",
    "print(\"Senator \" + sen_ls + \" is least similar to \" + senator + \" with dot-product \" + str(min_dp) + \".\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 2.12.5:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senator Jeffords is most similar to Chafee with dot-product 40.\n"
     ]
    }
   ],
   "source": [
    "senator = \"Chafee\"\n",
    "sen_ms, max_dp = most_similar(senator, voting_dict)\n",
    "print(\"Senator \" + sen_ms + \" is most like \" + senator + \" with dot-product \" + str(max_dp) + \".\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senator Feingold disgrees the most with Santorum with dot-product 3.\n"
     ]
    }
   ],
   "source": [
    "senator = \"Santorum\"\n",
    "sen_ls, min_dp = least_similar(senator, voting_dict)\n",
    "print(\"Senator \" + sen_ls + \" disgrees the most with \" + senator + \" with dot-product \" + str(min_dp) + \".\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.12.5 Not your average Democrat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def create_party_dict(strlist):\n",
    "    d = {}\n",
    "    for str in strlist:\n",
    "        lst = str.split(' ')\n",
    "        d[lst[0]] = lst[1].strip(\"\\n\")\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def find_average_similarity(sen, sen_set, voting_dict):\n",
    "    # initialisation\n",
    "    n = len(sen_set)\n",
    "    sum_dp = 0\n",
    "    sen_votes = voting_dict[sen]\n",
    "    \n",
    "    for s in sen_set:\n",
    "        sum_dp += list_dot(sen_votes, voting_dict[s])\n",
    "    \n",
    "    return sum_dp/n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Schumer', 'Lautenberg', 'Carper', 'Murray', 'Johnson', 'Wyden', 'Boxer', 'Dodd', 'Rockefeller', 'Salazar', 'Dorgan', 'Baucus', 'Lincoln', 'Leahy', 'Akaka', 'Landrieu', 'Clinton', 'Levin', 'Cantwell', 'Bingaman', 'Byrd', 'Nelson2', 'Feinstein', 'Inouye', 'Reid', 'Kennedy', 'Kohl', 'Bayh', 'Conrad', 'Mikulski', 'Biden', 'Lieberman', 'Durbin', 'Nelson1', 'Obama', 'Feingold', 'Sarbanes', 'Harkin', 'Reed', 'Dayton', 'Stabenow', 'Kerry', 'Pryor'}\n"
     ]
    }
   ],
   "source": [
    "party_dict = create_party_dict(my_list)\n",
    "democrats = {s for s, p in party_dict.items() if p == \"D\"}\n",
    "print(democrats)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def greatest_average_similarity(sen_set, voting_dict):\n",
    "    max_avg_dp = -math.inf\n",
    "    sen_w_gas = \"\"\n",
    "    \n",
    "    for s, v in voting_dict.items():\n",
    "        avg_sim = find_average_similarity(s, sen_set, voting_dict)\n",
    "        if avg_sim > max_avg_dp:\n",
    "            max_avg_dp = avg_sim\n",
    "            sen_w_gas = s\n",
    "    return sen_w_gas, max_avg_dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senator 'Biden' has the greatest average similarity with the set of Democrats: 34.86\n"
     ]
    }
   ],
   "source": [
    "sen, avg_dp = greatest_average_similarity(democrats, voting_dict)\n",
    "print(\"Senator '\" + sen + \"' has the greatest average similarity with the set of Democrats: \" + str(round(avg_dp, 2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Task 2.12.8:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def find_average_record(sen_set, voting_dict):\n",
    "    # initialisation\n",
    "    n = len(sen_set)\n",
    "    n_vote = len(voting_dict[list(sen_set)[0]])\n",
    "    voting_sums = [0] * n_vote # zero list/vector\n",
    "    \n",
    "    for sen in sen_set:\n",
    "        voting_sums = [s + v for s, v in zip(voting_sums, voting_dict[sen])]\n",
    "        \n",
    "    return [v/n for v in voting_sums]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The average voting record for Democrats is \n",
      "[-0.16279069767441862, -0.23255813953488372, 1.0, 0.8372093023255814, 0.9767441860465116, -0.13953488372093023, -0.9534883720930233, 0.813953488372093, 0.9767441860465116, 0.9767441860465116, 0.9069767441860465, 0.7674418604651163, 0.6744186046511628, 0.9767441860465116, -0.5116279069767442, 0.9302325581395349, 0.9534883720930233, 0.9767441860465116, -0.3953488372093023, 0.9767441860465116, 1.0, 1.0, 1.0, 0.9534883720930233, -0.4883720930232558, 1.0, -0.32558139534883723, -0.06976744186046512, 0.9767441860465116, 0.8604651162790697, 0.9767441860465116, 0.9767441860465116, 1.0, 1.0, 0.9767441860465116, -0.3488372093023256, 0.9767441860465116, -0.4883720930232558, 0.23255813953488372, 0.8837209302325582, 0.4418604651162791, 0.9069767441860465, -0.9069767441860465, 1.0, 0.9069767441860465, -0.3023255813953488]\n"
     ]
    }
   ],
   "source": [
    "average_democrat_record = find_average_record(democrats, voting_dict)\n",
    "print(\"The average voting record for Democrats is \")\n",
    "print(average_democrat_record)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# test whether we can achieve the same outcome as in task 2.12.7\n",
    "def find_most_similar_voting(voting, voting_dict):\n",
    "    max_dp = -math.inf\n",
    "    sen_ms = \"\"\n",
    "    \n",
    "    for s, v in voting_dict.items():\n",
    "        dp = list_dot(voting, v)\n",
    "        if (dp > max_dp):\n",
    "            max_dp = dp\n",
    "            sen_ms = s\n",
    "    return sen_ms, max_dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senator 'Biden' is the most similar to the average Democrat voting record: 34.86\n"
     ]
    }
   ],
   "source": [
    "sen, dp = find_most_similar_voting(average_democrat_record, voting_dict)\n",
    "print(\"Senator '\" + sen + \"' is the most similar to the average Democrat voting record: \" + str(round(dp, 2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 2.12.9:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# the obvious and slow way\n",
    "def bitter_rivals(voting_dict):\n",
    "    min_dp = math.inf\n",
    "    sen1 = \"\"\n",
    "    sen2 = \"\"\n",
    "    \n",
    "    for s1, v1 in voting_dict.items():\n",
    "        for s2, v2 in voting_dict.items():\n",
    "            if s1 != s2:\n",
    "                dp = list_dot(v1, v2)\n",
    "                if dp < min_dp:\n",
    "                    min_dp = dp\n",
    "                    sen1 = s1\n",
    "                    sen2 = s2\n",
    "    \n",
    "    return sen1, sen2, min_dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Senators 'Inhofe' and 'Feingold' are bitter rivals: -3\n"
     ]
    }
   ],
   "source": [
    "sen1, sen2, dp = bitter_rivals(voting_dict)\n",
    "print(\"Senators '\" + sen1 + \"' and '\" + sen2 + \"' are bitter rivals: \" + str(round(dp, 2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This task again requires comparing _each pair_ of voting records. Can this be done faster than the obvious way? There is a slightly more efficient algorithm, using _fast matrix multiplication_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.13 Review Questions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}