{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Type your name here*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "This assignment is a warmup to practice your Python skills.\n",
    "Your task is to write a Python program that optimizes a cost function that we're going to describe next.\n",
    "\n",
    "Consider a system that contains $n$ units labeled $\\{0,\\ldots,n-1\\}$ that are all connected.  Each unit has a state associated with it, where unit $i$ has a state $x_i$, and the overall state is referred to as $\\mathbf{x}$, i.e. $\\mathbf{x} = \\{x_0, x_1, \\ldots, x_{n-1}\\}$.  Assume that $x_i$ takes on the values -1 or +1.  All the units are interconnected and the weight of the connection between units $i$ and $j$ is given by $w_{ij}$.  We assume that the connectivity matrix is symmetric, i.e. $w_{ij} = w_{ji}$.  The state of the system is associated with a cost function, also referred to as energy, given by:\n",
    "\n",
    "$$\n",
    "E(\\mathbf{x}) = - \\frac{1}{2} \\sum_{i,j=0}^{n-1} w_{ij} x_i x_j\n",
    "$$\n",
    "\n",
    "This energy function is the basis of the [Hopfield neural network](https://en.wikipedia.org/wiki/Hopfield_network), which is a model of associative memory, and the [Ising spin-glass model](https://en.wikipedia.org/wiki/Ising_model#Spin_glasses) which has been extensively studied in statistical physics.\n",
    "\n",
    "We are interested in finding the global minimum of $E(\\mathbf{x})$, i.e. to find $\\mathbf{x}^*$ such that $E(\\mathbf{x}^*) \\leq E(\\mathbf{x})$ for all choices of $\\mathbf{x}$, and return the value of $E(\\mathbf{x}^*)$.\n",
    "The problem of finding this global minimum is NP-complete, i.e. there is no known efficient algorithm for computing it.  Therefore, you will need to consider all possible assignments to the variables $x_i$ when searching for the global minimum of $E(\\mathbf{x})$.\n",
    "\n",
    "For example, with the matrix \n",
    "$$ W = \n",
    "\\begin{pmatrix} \n",
    "0 & 1 \\\\\n",
    "1 & 0 \n",
    "\\end{pmatrix}\n",
    "$$\n",
    "The optimal solution is $\\mathbf{x}^* = (1, 1)$, with $E (1,1) = -\\frac{1}{2} (1 + 1) = -1$; note that $(-1,-1)$ gives the same result.\n",
    "Your task is to complete the following function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ising_optimize(matrix) :\n",
    "    \"\"\"\n",
    "    Return the minimum value of E(x) with the matrix given as the input\n",
    "    parameter.\n",
    "    The matrix is provided either as a Python list-of-lists or as a \n",
    "    string which is the path to a CSV file.\n",
    "    \"\"\"\n",
    "    return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the matrix shown above can be provided as input in one of two ways:\n",
    "w = [[0,1], [1, 0]]\n",
    "# as a list of lists:\n",
    "ising_optimize(w)\n",
    "# or can be read from a comma-delimited file:\n",
    "f = open(\"matrix.csv\", 'w')\n",
    "_ = f.write(\"0,1\\n1,0\\n\")\n",
    "f.close()\n",
    "!cat matrix.csv\n",
    "#%more matrix.csv\n",
    "ising_optimize(\"matrix.csv\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# recall that a list of lists can be accessed as W[i][j] for element i,j:\n",
    "w[1][0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that to determine the type of input provided to the function you can use the Python `type` built-in function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type([]) == list\n",
    "type('cs440') == str"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our test cases will look something like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "test failed\n"
     ]
    }
   ],
   "source": [
    "if ising_optimize(w) == -1 :\n",
    "    print(\"test was successful\")\n",
    "else :\n",
    "    print(\"test failed\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In your code do not use the Python `csv` module or code from the Numpy/pandas libraries.\n",
    "\n",
    "Submit your code as a jupyter notebook named `p1.ipynb` via Canvas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grading\n",
    "\n",
    "Your notebook will be run and graded automatically.  So make sure your code satisfies the specified API, i.e. correct naming and behavior of your methods and classes.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}