cs110_pcw_12_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = \"Verina Armanyous\"\n",
    "COLLABORATORS = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "0f21ce4c9e01aa6a231ae85c9319acf3",
     "grade": false,
     "grade_id": "cell-f49515decdd20fa1",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 12.1\n",
    "\n",
    "## Question 1.\n",
    "Define the `enqueue(self, x)` and `dequeue(self)` methods of the class `Queue` below, by modifying the cell. You do not need to include the error checking for underflow and overflow. You can follow the pseudo-codes on p.235, Cormen et al. to complete this task."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "7e29f9d49b8f1ac6d8a416278c338aaa",
     "grade": false,
     "grade_id": "cell-ebbe229b0421e86e",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "class Queue(object):\n",
    "    def __init__(self, length):\n",
    "        self.length = length\n",
    "        self.head = 1\n",
    "        self.tail = 1\n",
    "        self.q = {}\n",
    "        for i in range(1, self.length+1):\n",
    "            self.q[i] = None\n",
    "    def enqueue (self,x): #to add elements to the queue\n",
    "        self.q[self.tail]= x #add new value at the tail \n",
    "        if self.tail==self.length: #if tail and length are equal\n",
    "            self.tail =1 #assign 1 to be the value of tail\n",
    "        else:\n",
    "            self.tail=self.tail+1 #otherwise, increase tail value by 1\n",
    "    \n",
    "    def dequeue(self): #to remove elements from the queue\n",
    "        x= self.q[self.head] #x is the head of the queue\n",
    "        if self.head==self.length: #if head and length are equal\n",
    "            self.head=1 #assign one to the head\n",
    "        else:\n",
    "            self.head=self.head+1 #otherwise, increase head by 1\n",
    "        return x #return the value of the element\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "70c402b90b1c8213eaf69a116c0a3c45",
     "grade": false,
     "grade_id": "cell-9e685a1fdf0e1bf6",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2. \n",
    "\n",
    "Below, the first cell is a working code for two classes, `Node` and `Graph` that can be used to represent undirected or directed graphs. Use these two classes to complete the function `bfs` that implements the breath-first search algorithm in the second cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "67f0f9b0f8b0039c23ed185490e394fb",
     "grade": false,
     "grade_id": "cell-2dfede3b8a3adb96",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "r: [s v] color: W dist: inf pi: Nil,\n",
      "s: [r w] color: W dist: inf pi: Nil,\n",
      "t: [w x u] color: W dist: inf pi: Nil,\n",
      "u: [t x y] color: W dist: inf pi: Nil,\n",
      "v: [r] color: W dist: inf pi: Nil,\n",
      "w: [s t x] color: W dist: inf pi: Nil,\n",
      "x: [w t u y] color: W dist: inf pi: Nil,\n",
      "y: [u x] color: W dist: inf pi: Nil,\n",
      "\n"
     ]
    }
   ],
   "source": [
    "class Node: \n",
    "    \n",
    "    BLACK = 'B'\n",
    "    GRAY = 'G'\n",
    "    WHITE = 'W'\n",
    "    \n",
    "    def __init__(self, name, adj_list=None, weighted_adj_list=None): \n",
    "        self.name = name\n",
    "        self.color = Node.WHITE\n",
    "        self.pi = None\n",
    "        self.dist = float('inf')\n",
    "        self.adj_list = adj_list\n",
    "        if not adj_list: \n",
    "            self.adj_list = []\n",
    "        \n",
    "    def add_edge(self, node): \n",
    "        if node.name not in self.adj_list: \n",
    "            self.adj_list.append(node.name)\n",
    "        \n",
    "    def remove_edge(self, node): \n",
    "        self.adj_list.remove(node.name)\n",
    "        \n",
    "    def to_string(self): \n",
    "        res = self.name + ': [' + ' '.join(self.adj_list) + '] color: ' + self.color + ' dist: ' + str(self.dist)\n",
    "        if not self.pi:\n",
    "            res += ' pi: Nil'\n",
    "        else: \n",
    "            res += ' pi: ' + self.pi\n",
    "        return res\n",
    "\n",
    "class Graph: \n",
    "    \n",
    "    def __init__(self, nodes={}): \n",
    "        self.nodes = nodes\n",
    "        \n",
    "    def add_node(self,node): \n",
    "        self.nodes[node.name] = node\n",
    "        \n",
    "    def add_edge(self,n1,n2): \n",
    "        self.nodes[n1].add_edge(self.nodes[n2])\n",
    "        \n",
    "    def remove_edge(self, n1, n2): \n",
    "        self.nodes[n1].remove_edge(self.nodes[n2])\n",
    "        \n",
    "    def to_string(self): \n",
    "        res = \"\"\n",
    "        for n in self.nodes.keys(): \n",
    "            res += self.nodes[n].to_string() + \",\\n\"\n",
    "        return res\n",
    "      \n",
    "g = Graph({})\n",
    "g.add_node(Node('r', ['s','v']))\n",
    "g.add_node(Node('s', ['r','w']))\n",
    "g.add_node(Node('t', ['w','x','u']))\n",
    "g.add_node(Node('u', ['t','x','y']))\n",
    "g.add_node(Node('v', ['r']))\n",
    "g.add_node(Node('w', ['s','t','x']))\n",
    "g.add_node(Node('x', ['w','t','u','y']))\n",
    "g.add_node(Node('y', ['u','x']))\n",
    "\n",
    "print(g.to_string())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "760f180f167347b70d63a81bd97bdc00",
     "grade": false,
     "grade_id": "cell-79459bfd60700881",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def bfs(G,s):\n",
    "    \"\"\"\n",
    "    Breath-first search\n",
    "    \n",
    "    Inputs:\n",
    "    - G: a graph (instance of Graph)\n",
    "    - s: string, name of the source vertex which is an instance of Node\n",
    "    \n",
    "    Output:\n",
    "    - info: string, what is returned by G.to_string()\n",
    "    \"\"\"\n",
    "    for v in G.nodes: #for all nodes in the graph\n",
    "        v.color = WHITE #nodes are white\n",
    "        v.dist = float('inf') #distance set to positive infinity\n",
    "        v.pi=None \n",
    "    s.color=GRAY #change the color of source vertex to  gray\n",
    "    s.dist=0\n",
    "    s.pi= None\n",
    "    Q=Queue() #create a queue\n",
    "    Q.enqueue(s)\n",
    "    while Q:\n",
    "        v=dequeue(Q)\n",
    "        for j in G.adj_list[v]:\n",
    "            if j.color==WHITE: #if the color of adjacent node is white\n",
    "                j.color=GRAY #change to gray \n",
    "                j.dist=v.dist+1 # update the distance \n",
    "                j.pi = v\n",
    "                enqueue(Q,j)\n",
    "                \n",
    "        v.color= BLACK #change the color to black when the adjacent nodes are visited\n",
    "        \n",
    "    return G.to_string()\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "39083ef10d9964de5fedd745ae0216a1",
     "grade": false,
     "grade_id": "cell-df5e25eea74070b9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3.\n",
    "\n",
    "Solve exercise 22.2-1 in Cormen et al. by following these steps:\n",
    "1. Build a graph G that represents the graph in Figure 22.2-(a). The names of the vertices are noted in each vertex (1, 2, 3, 4, 5, and 6)\n",
    "2. Print the info returned by `bfs`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "b0d6e287db54e8c0cc714362ffdb21ef",
     "grade": true,
     "grade_id": "cell-692a09a756ecaa40",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'WHITE' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-6-3147bf23a216>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0mG\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mNode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'5'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m'4'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mG\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mNode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'6'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m'6'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 8\u001b[0;31m \u001b[0mbfs\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mG\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-4-b954370784ec>\u001b[0m in \u001b[0;36mbfs\u001b[0;34m(G, s)\u001b[0m\n\u001b[1;32m     11\u001b[0m     \"\"\"\n\u001b[1;32m     12\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mv\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mG\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnodes\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m#for all nodes in the graph\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 13\u001b[0;31m         \u001b[0mv\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcolor\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mWHITE\u001b[0m \u001b[0;31m#nodes are white\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     14\u001b[0m         \u001b[0mv\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdist\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfloat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'inf'\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m#distance set to positive infinity\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     15\u001b[0m         \u001b[0mv\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpi\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mNameError\u001b[0m: name 'WHITE' is not defined"
     ]
    }
   ],
   "source": [
    "G= Graph({}) #create an instance of the class\n",
    "G.add_node(Node('1', ['2','5']))\n",
    "G.add_node(Node('2', ['5']))\n",
    "G.add_node(Node('3', ['6','5']))\n",
    "G.add_node(Node('4', ['2']))\n",
    "G.add_node(Node('5', ['4']))\n",
    "G.add_node(Node('6', ['6']))\n",
    "bfs(G,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "e383fc84bbdac7b0911f3d6f17c80a34",
     "grade": false,
     "grade_id": "cell-71c8b5ed8faa8e34",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 4.\n",
    "Solve exercise 22.2-2 in Cormen et al. by following these steps:\n",
    "1. Build a graph G that represents the graph in Figure 22.3-(a). Note that the names of the vertices are given as `r`, `x`, `t`, `u`, etc.\n",
    "2. Print the info returned by `bfs`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "c977a39ba030c39d3fba8cc1ca0d5dfe",
     "grade": true,
     "grade_id": "cell-eccd2dcb9f2eec18",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 's' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-8-7b7b9e36ea2e>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      8\u001b[0m \u001b[0mG\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mNode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'y'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m'u'\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m'x'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      9\u001b[0m \u001b[0mG\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd_node\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mNode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'u'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m'y'\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m't'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 10\u001b[0;31m \u001b[0mbfs\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mG\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 's' is not defined"
     ]
    }
   ],
   "source": [
    "G= Graph({}) #create an instance of the class\n",
    "G.add_node(Node('r', ['s','v']))\n",
    "G.add_node(Node('x', ['w','t','y']))\n",
    "G.add_node(Node('s', ['r','w']))\n",
    "G.add_node(Node('v', ['r']))\n",
    "G.add_node(Node('w', ['s','t','x']))\n",
    "G.add_node(Node('t', ['x','u','w']))\n",
    "G.add_node(Node('y', ['u','x']))\n",
    "G.add_node(Node('u', ['y','t']))\n",
    "bfs(G,s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "5a09e4cae5de3aec672714362e8b27d2",
     "grade": false,
     "grade_id": "cell-aae6917929e609dd",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 5.\n",
    "Is the shortest path problem in an undirected graph suitable for a dynamic programming solution? Why or why not?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "4ce458227450628bf1c354006e74dc8d",
     "grade": true,
     "grade_id": "cell-e0446af225564643",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "We can bottom up approach to store the distance between each two nodes. Then, when we want to find the shortest path between two nodes, we take the minimum number that would provide a combination of nodes that would lead us to the final node. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "f9a675e4875e995f261285d322e59ac2",
     "grade": false,
     "grade_id": "cell-bc2f4b735ce6608d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 6. \n",
    "Answer in prose what changes need to be made to the graph representation to incorporate the concept of edge weights."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "29d70dd6835f376857472704851c81f0",
     "grade": true,
     "grade_id": "cell-a9d4e31b797ed485",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "In the matrix, instead of using 1 and 0 to donate whether two nodes are connected, we can put the weight of the edge between the two nodes.  On the graph representation, we can assign an extra attribute to the edge that would reflect its weight. "
   ]
  }
 ],
 "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.7.1"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}