path: root/Elements_of_discrete_mathematics/Chapter3.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:d6505774a4cce1c5726d5bf482120157569ff894ee6f05281095d53b18882117"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "3 Relations and Functions"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 06:Page 118"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"Given a relation R on a set A={a,b,c,d} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\"\n",
      "#Each element in A acts as a node\n",
      "nodes=input(\"Enter the number of nodes\")#This is the total number of elements in the given set A\n",
      "w0=[[0 for i in range (nodes)]for j in range(nodes)]#Matrix elements are initialised to zero\n",
      "#Gets the initial value for the matrix elements\n",
      "print \"Enter the elements of W0. (Enter only 0 or 1)\"# The value is 1 if there is a path between i and j in the given graph, else it is 0\n",
      "for i in range(0,nodes):\n",
      "    for j in range(0,nodes):\n",
      "        print \"Enter value for w\",i,j\n",
      "        w0[i][j]=input()\n",
      "#To print the given matrix\n",
      "print \"The given matrix W0=MR(Matrix relation on R) is\"\n",
      "for i in range(0,nodes):\n",
      "    for j in range(0,nodes):\n",
      "        print w0[i][j],\n",
      "    print \"\\n\"\n",
      "for k in range(0,nodes):#To find the transitive relation matrix using Warshall's algorithm\n",
      "    for i in range(0,nodes):\n",
      "        for j in range(0,nodes):\n",
      "            w0[i][j]=w0[i][j] or (w0[i][k] and w0[k][j])\n",
      "#To print the transitive relation matrix\n",
      "print \"The required transitive relation matrix is\"\n",
      "for i in range(0,nodes):\n",
      "    for j in range(0,nodes):\n",
      "        print w0[i][j],\n",
      "    print \"\\n\"\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Given a relation R on a set A={a,b,c,d} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the number of nodes4\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the elements of W0. (Enter only 0 or 1)\n",
        "Enter value for w 0 0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 0 1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 0 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 0 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 1 0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 1 1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 1 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 1 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 2 0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 2 1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 2 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 2 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 3 0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 3 1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 3 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 3 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The given matrix W0=MR(Matrix relation on R) is\n",
        "0 1 0 0 \n",
        "\n",
        "1 0 1 0 \n",
        "\n",
        "0 0 0 1 \n",
        "\n",
        "1 0 0 0 \n",
        "\n",
        "The required transitive relation matrix is\n",
        "1 1 1 1 \n",
        "\n",
        "1 1 1 1 \n",
        "\n",
        "1 1 1 1 \n",
        "\n",
        "1 1 1 1 \n",
        "\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 07:Page 119"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"Given a relation R on a set A={a,b,c,d,e} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\"\n",
      "print \"Given:R={(b,c),(b,e),(c,e),(d,a),(c,b),(e,c)}\"\n",
      "#Each element in A acts as a node\n",
      "nodes=input(\"Enter the number of nodes\")#This is the total number of elements in the given set A\n",
      "w0=[[0 for i in range (nodes)]for j in range(nodes)]#Matrix elements are initialised to zero\n",
      "#Gets the initial value for the matrix elements\n",
      "print \"Enter the elements of W0. (Enter only 0 or 1)\"# The value is 1 if there is a path between i and j in the given graph, else it is 0\n",
      "for i in range(0,nodes):\n",
      "    for j in range(0,nodes):\n",
      "        print \"Enter value for w\",i,j\n",
      "        w0[i][j]=input()\n",
      "#To print the given matrix\n",
      "print \"The given matrix W0=MR(Matrix relation on R) is\"\n",
      "for i in range(0,nodes):\n",
      "    for j in range(0,nodes):\n",
      "        print w0[i][j],\n",
      "    print \"\\n\"\n",
      "for k in range(0,nodes):#To find the transitive relation matrix using Warshall's algorithm\n",
      "    for i in range(0,nodes):\n",
      "        for j in range(0,nodes):\n",
      "            w0[i][j]=w0[i][j] or (w0[i][k] and w0[k][j])\n",
      "#To print the transitive relation matrix\n",
      "print \"The required transitive relation matrix is\"\n",
      "for i in range(0,nodes):\n",
      "    for j in range(0,nodes):\n",
      "        print w0[i][j],\n",
      "    print \"\\n\"\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Given a relation R on a set A={a,b,c,d,e} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\n",
        "Given:R={(b,c),(b,e),(c,e),(d,a),(c,b),(e,c)}\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the number of nodes5\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the elements of W0. (Enter only 0 or 1)\n",
        "Enter value for w 0 0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 0 1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 0 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 0 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 0 4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 1 0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 1 1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 1 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 1 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 1 4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 2 0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 2 1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 2 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 2 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 2 4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 3 0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 3 1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 3 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 3 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 3 4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 4 0\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 4 1\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 4 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 4 3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter value for w 4 4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The given matrix W0=MR(Matrix relation on R) is\n",
        "0 0 0 0 0 \n",
        "\n",
        "0 0 1 0 1 \n",
        "\n",
        "0 0 0 0 1 \n",
        "\n",
        "1 0 0 0 0 \n",
        "\n",
        "0 1 1 0 0 \n",
        "\n",
        "The required transitive relation matrix is\n",
        "0 0 0 0 0 \n",
        "\n",
        "0 1 1 0 1 \n",
        "\n",
        "0 1 1 0 1 \n",
        "\n",
        "1 0 0 0 0 \n",
        "\n",
        "0 1 1 0 1 \n",
        "\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 41:Page 154"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#Given function definition is as follows\n",
      "print \"RECURSIVE FUNCTIONS\"\n",
      "def f(x):\n",
      "    if x==0:\n",
      "        return 1\n",
      "    else:\n",
      "        return 3*f(x-1)+1\n",
      "print \"f(1)=\",f(1)\n",
      "print \"f(2)=\",f(2)\n",
      "print \"f(3)=\",f(3)\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "RECURSIVE FUNCTIONS\n",
        "f(1)= 4\n",
        "f(2)= 13\n",
        "f(3)= 40\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 43:Page 156"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"A recursive function to calculate the GCD of two numbers\"\n",
      "def GCD(x,y):\n",
      "    if x>y:\n",
      "        x=x-y\n",
      "        return GCD(x,y)\n",
      "    elif x<y:\n",
      "        y=y-x\n",
      "        return GCD(x,y)\n",
      "    else:\n",
      "        print \"The GCD of the two numbers is\",x\n",
      "\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "A recursive function to calculate the GCD of two numbers\n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 44:Page 157"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"EXAMPLE OF TREE RECURSION\"\n",
      "print \"The first six fibonacci numbers are\"\n",
      "def fib(n):\n",
      "    if n==0:\n",
      "        return 0\n",
      "    elif n==1:\n",
      "        return 1\n",
      "    else:\n",
      "        print \"fib(\",n-1,\")+fib(\",n-2,\")=\",\n",
      "        return fib(n-1)+fib(n-2)\n",
      "print \"fib(0)=\",fib(0),\n",
      "print \"\\nfib(1)=\",fib(1),\n",
      "print \"\\nfib(2)=\",fib(2),\n",
      "print \"\\nfib(3)=\",fib(3),\n",
      "print \"\\nfib(4)=\",fib(4),\n",
      "print \"\\nfib(5)=\",fib(5),\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "EXAMPLE OF TREE RECURSION\n",
        "The first six fibonacci numbers are\n",
        "fib(0)= 0 \n",
        "fib(1)= 1 \n",
        "fib(2)= fib( 1 )+fib( 0 )= 1 \n",
        "fib(3)= fib( 2 )+fib( 1 )= fib( 1 )+fib( 0 )= 2 \n",
        "fib(4)= fib( 3 )+fib( 2 )= fib( 2 )+fib( 1 )= fib( 1 )+fib( 0 )= fib( 1 )+fib( 0 )= 3 \n",
        "fib(5)= fib( 4 )+fib( 3 )= fib( 3 )+fib( 2 )= fib( 2 )+fib( 1 )= fib( 1 )+fib( 0 )= fib( 1 )+fib( 0 )= fib( 2 )+fib( 1 )= fib( 1 )+fib( 0 )= 5\n"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 45:Page 159"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"HASH FUNCTIONS\"\n",
      "import math\n",
      "print \"Employee IDs are 6713,4409,5835\"\n",
      "print \"L consists of 100 two digit address:00,01,.....,99 \"\n",
      "m=97#Prime number close to 99\n",
      "def H(ID):\n",
      "    print ID,\"mod\",m,\"=\",\n",
      "    return ID%m\n",
      "print \"Division method\"\n",
      "print \"H(6713)=\",H(6713)\n",
      "print \"H(4409)=\",H(4409)\n",
      "print \"H(5835)=\",H(5835)\n",
      "print \"Midsquare method\"\n",
      "\n",
      "def H1(ID):\n",
      "    key=math.pow(ID,2)#Square the given key value\n",
      "    key1=int(key)#Convert it into integer to eliminate decimal point\n",
      "    number=str(key1)#Integer is converted to string for indexing purpose\n",
      "    length=len(number)#Finding the length of the string\n",
      "    number2=number[3:length-3]#Slicing the string to eliminate 3 digits from both ends\n",
      "    return number2\n",
      "    \n",
      "print \"k=6713\",\"square(k)=\",pow(6713,2),\"\\tH(6713)=\",H1(6713)\n",
      "print \"k=4409\",\"square(k)=\",pow(4409,2),\"\\tH(4409)=\",H1(4409)\n",
      "print \"k=5835\",\"square(k)=\",pow(5835,2),\"\\tH(5835)=\",H1(5835)\n",
      "print \"Folding method\"\n",
      "#Here the given key is divided in such a way that each part has two digits. Since it has even number of digits there is no exception to this rule\n",
      "def H2(ID):\n",
      "    ID1=str(ID)#Convert it into string in order to slice it\n",
      "    key1=ID1[0:2]#Split the string into two halves. First part in key1\n",
      "    key2=ID1[2:]#Second half is stored in key2\n",
      "    print key1,\"+\",key2,\"=\",\n",
      "    key=int(key1)+int(key2)#Convert these into int in order to perform addition\n",
      "    key3=str(key)#To eliminate the carry,convert it back to string\n",
      "    length=len(key3)#Since here each part contains only 2 digits, a carry means the presence of a third digit.\n",
      "    if length==3:\n",
      "        res=key3[1:]#If length is 3 , eliminate the leftmost digit\n",
      "        return res\n",
      "    else:\n",
      "        return key#If it is less than 3, print it as such\n",
      "print \"6713=\",H2(6713)\n",
      "print \"4409=\",H2(4409)\n",
      "print \"5835=\",H2(5835)\n",
      "\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "HASH FUNCTIONS\n",
        "Employee IDs are 6713,4409,5835\n",
        "L consists of 100 two digit address:00,01,.....,99 \n",
        "Division method\n",
        "H(6713)= 6713 mod 97 = 20\n",
        "H(4409)= 4409 mod 97 = 44\n",
        "H(5835)= 5835 mod 97 = 15\n",
        "Midsquare method\n",
        "k=6713 square(k)= 45064369 \tH(6713)= 64\n",
        "k=4409 square(k)= 19439281 \tH(4409)= 39\n",
        "k=5835 square(k)= 34047225 \tH(5835)= 47\n",
        "Folding method\n",
        "6713= 67 + 13 = 80\n",
        "4409= 44 + 09 = 53\n",
        "5835= 58 + 35 = 93\n"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 46:Page 161"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"Linear probing to overcome collision in the numbers 89,18,49,58,69\"\n",
      "memory=[\"\" for i in range (0,10)]#An array indicating the memory space. Initially all the locations are empty\n",
      "\n",
      "def h(n):\n",
      "    temp=n#Get a copy as we might change the value in the original variable\n",
      "    count=0#Initial collision count is zero\n",
      "    flag=0#Flag=1 indicates that the key has been placed in the memory. So initially it is zero\n",
      "    while flag==0:\n",
      "        num=n%10#10 is the number of buckets or partitions\n",
      "        if memory[num]==\"\":#Checks if the location is empty\n",
      "            memory[num]=temp#Inserts value if nothing is already present\n",
      "            flag=1#Indicates that the key is placed in memory\n",
      "        else:\n",
      "            count=count+1#If the location is not empty, the collision count is increased by one\n",
      "            def f(i):#Collosion resolution function\n",
      "                return i\n",
      "            n=num+f(count)#Facilitates linear probing by increasing the count by 1\n",
      "#Hash the values            \n",
      "h(89)\n",
      "h(18)\n",
      "h(49)\n",
      "h(58)\n",
      "h(69)\n",
      "print \"MEMORY  |\\t\\tVALUE\"\n",
      "print \"------------------------------------\"\n",
      "for i in range(0,10):#Print the hashed memory area\n",
      "    print i,\"\\t|\\t\",memory[i]\n",
      "    print \"---------------------------------\"\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Linear probing to overcome collision in the numbers 89,18,49,58,69\n",
        "MEMORY  |\t\tVALUE\n",
        "------------------------------------\n",
        "0 \t|\t49\n",
        "---------------------------------\n",
        "1 \t|\t58\n",
        "---------------------------------\n",
        "2 \t|\t69\n",
        "---------------------------------\n",
        "3 \t|\t\n",
        "---------------------------------\n",
        "4 \t|\t\n",
        "---------------------------------\n",
        "5 \t|\t\n",
        "---------------------------------\n",
        "6 \t|\t\n",
        "---------------------------------\n",
        "7 \t|\t\n",
        "---------------------------------\n",
        "8 \t|\t18\n",
        "---------------------------------\n",
        "9 \t|\t89\n",
        "---------------------------------\n"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 47:Page 163"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"Quadratic probing in the numbers 89,18,49,58,69\"\n",
      "memory=[\"\" for i in range (0,10)]#An array indicating the memory space. Initially all the locations are empty\n",
      "\n",
      "def h(n):\n",
      "    temp=n#Get a copy as we might change the value in the original variable\n",
      "    count=0#Initial collision count is zero\n",
      "    flag=0#Flag=1 indicates that the key has been placed in the memory. So initially it is zero\n",
      "    while flag==0:\n",
      "        num=n%10#10 is the number of buckets or partitions\n",
      "        if memory[num]==\"\":#Checks if the location is empty\n",
      "            memory[num]=temp#Inserts value if nothing is already present\n",
      "            flag=1#Indicates that the key is placed in memory\n",
      "        else:\n",
      "            count=count+1#If the location is not empty, the collision count is increased by one\n",
      "            def f(i):#Collosion resolution function\n",
      "                return i*i\n",
      "            n=num+f(count)#Facilitates quadratic probing by squaring the count \n",
      "#Hash the values            \n",
      "h(89)\n",
      "h(18)\n",
      "h(49)\n",
      "h(58)\n",
      "h(69)\n",
      "print \"MEMORY  |\\t VALUES\"\n",
      "print \"-------------------------------------\"\n",
      "for i in range(0,10):#Print the hashed memory area\n",
      "    print i,\"\\t|\\t\",memory[i]\n",
      "    print \"-------------------------------------\"\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Quadratic probing in the numbers 89,18,49,58,69\n",
        "MEMORY  |\t VALUES\n",
        "-------------------------------------\n",
        "0 \t|\t49\n",
        "-------------------------------------\n",
        "1 \t|\t\n",
        "-------------------------------------\n",
        "2 \t|\t\n",
        "-------------------------------------\n",
        "3 \t|\t58\n",
        "-------------------------------------\n",
        "4 \t|\t69\n",
        "-------------------------------------\n",
        "5 \t|\t\n",
        "-------------------------------------\n",
        "6 \t|\t\n",
        "-------------------------------------\n",
        "7 \t|\t\n",
        "-------------------------------------\n",
        "8 \t|\t18\n",
        "-------------------------------------\n",
        "9 \t|\t89\n",
        "-------------------------------------\n"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 48:Page 164"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"Double hashing in the numbers 89,18,49,58,69\"\n",
      "memory=[\"\" for i in range (0,10)]#An array indicating the memory space. Initially all the locations are empty\n",
      "r=7#Assume\n",
      "def h(n):\n",
      "    temp=n#Get a copy as we might change the value in the original variable\n",
      "    count=0#Initial collision count is zero\n",
      "    flag=0#Flag=1 indicates that the key has been placed in the memory. So initially it is zero\n",
      "    while flag==0:\n",
      "        num=n%10#10 is the number of buckets or partitions\n",
      "        if memory[num]==\"\":#Checks if the location is empty\n",
      "            memory[num]=temp#Inserts value if nothing is already present\n",
      "            flag=1#Indicates that the key is placed in memory\n",
      "        else:\n",
      "            count=count+1#If the location is not empty, the collision count is increased by one\n",
      "            def h1(t):\n",
      "                return r-(t%r)#Assume \n",
      "            \n",
      "            def f(i):#Collosion resolution function\n",
      "                return i*h1(temp)\n",
      "            n=num+f(count)#Facilitates probing \n",
      "#Hash the values            \n",
      "h(89)\n",
      "h(18)\n",
      "h(49)\n",
      "h(58)\n",
      "h(69)\n",
      "print \"MEMORY  |\\tVALUES\"\n",
      "print \"-------------------------------------\"\n",
      "for i in range(0,10):#Print the hashed memory area\n",
      "    print i,\"\\t|\\t\",memory[i]\n",
      "    print \"----------------------------------------\"\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Double hashing in the numbers 89,18,49,58,69\n",
        "MEMORY  |\tVALUES\n",
        "-------------------------------------\n",
        "0 \t|\t69\n",
        "----------------------------------------\n",
        "1 \t|\t\n",
        "----------------------------------------\n",
        "2 \t|\t\n",
        "----------------------------------------\n",
        "3 \t|\t58\n",
        "----------------------------------------\n",
        "4 \t|\t\n",
        "----------------------------------------\n",
        "5 \t|\t\n",
        "----------------------------------------\n",
        "6 \t|\t49\n",
        "----------------------------------------\n",
        "7 \t|\t\n",
        "----------------------------------------\n",
        "8 \t|\t18\n",
        "----------------------------------------\n",
        "9 \t|\t89\n",
        "----------------------------------------\n"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 49:Page 166"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "magazine=30#Magazines are considered as pigeonholes\n",
      "total_pages=61324#Pages are considered as pigeons. Assign each page to the magazine in which it appears\n",
      "print \"If 30 magazines contain a total of 61,324 pages, then one magazine must contain at least\",int((math.floor((total_pages-1)/magazine)+1)),\"pages\"#According to extended pigeonhole principle\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "If 30 magazines contain a total of 61,324 pages, then one magazine must contain at least 2045 pages\n"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 50:Page 166"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "a=0\n",
      "b=0\n",
      "s=[[0 for i in range(13)]for j in range(13)]#Initialise the matrix\n",
      "#If the summation turns out to be 13, then put them in a 2D array\n",
      "for i in range(1,13):\n",
      "    for j in range(i+1,13):\n",
      "        \n",
      "        if i+j==13:\n",
      "           \n",
      "            s[a][b]=i\n",
      "            s[a][b+1]=j\n",
      "            a=a+1\n",
      "#Print the 2D array containing the possible combinations        \n",
      "for i in range(0,a):\n",
      "    print \"s\",i+1,\"=(\",\n",
      "    for j in range(0,2):\n",
      "        print s[i][j],\",\",\n",
      "    print \"),\",\n",
      "    print \"\\n\"\n",
      "\n",
      "print \"These are the combination of numbers between 1 and 12 those on summation will yield 13 as a result.\"\n",
      "print \"Each of the chosen 7 numbers must contain any of these combinations, so that summation of 2 among that will yield 13. Therefore there are 6 ways to do so \"\n",
      "#According to pigeonhole principle\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "s 1 =( 1 , 12 , ), \n",
        "\n",
        "s 2 =( 2 , 11 , ), \n",
        "\n",
        "s 3 =( 3 , 10 , ), \n",
        "\n",
        "s 4 =( 4 , 9 , ), \n",
        "\n",
        "s 5 =( 5 , 8 , ), \n",
        "\n",
        "s 6 =( 6 , 7 , ), \n",
        "\n",
        "These are the combination of numbers between 1 and 12 those on summation will yield 13 as a result.\n",
        "Each of the chosen 7 numbers must contain any of these combinations, so that summation of 2 among that will yield 13. Therefore there are 6 ways to do so \n"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 52:Page 166"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "total_num=10#Total number of people volunteering\n",
      "committee_num=3#Number of people to be there in the committee\n",
      "print \"Ten people come forward to volunteer for a committee of three\"\n",
      "print \"Every possible committee of three that can be formed from these ten names is written on a slip of paper\"\n",
      "slips=(math.factorial(total_num)/(math.factorial(total_num-committee_num)*math.factorial(committee_num)))#Slips are compared to pigeons.By formula for combinations\n",
      "hats=10#Hats are compared to pigeonholes\n",
      "print \"Total number of combinations to choose 3 out of ten is\",slips\n",
      "print \"These possible \",slips, \"slips, one slip for each possible committee and the slips are put in \",hats,\"hats\"\n",
      "print \"Therefore, One hat must contain at least\",int((math.floor((slips-1)/hats)+1)),\"or more slips of paper\"\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Ten people come forward to volunteer for a committee of three\n",
        "Every possible committee of three that can be formed from these ten names is written on a slip of paper\n",
        "Total number of combinations to choose 3 out of ten is 120\n",
        "These possible  120 slips, one slip for each possible committee and the slips are put in  10 hats\n",
        "Therefore, One hat must contain at least 12 or more slips of paper\n"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 53:Page 166"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "types=12#Types of chocolates\n",
      "choice=5#Types to choose from\n",
      "print \"A store has an introductory sale on 12 types of chocolates. A customer can choose 1 chocolate of any 5 different types and will be charged no more than 1.75 \"\n",
      "c=math.factorial(types)/(math.factorial(choice)*math.factorial(types-choice))#By the formula for finding combinations\n",
      "print \"The customer can choose chocolates in \",c,\"ways\"\n",
      "amount=175#In paise\n",
      "print \"we have\",int((math.floor((c-1)/amount)+1)),\"choices having the same cost\"#By extended pigeonhole principle\n",
      "print \"Therefore, there must be at least two different ways to choose, so that the cost will be the same for both choices\"\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "A store has an introductory sale on 12 types of chocolates. A customer can choose 1 chocolate of any 5 different types and will be charged no more than 1.75 \n",
        "The customer can choose chocolates in  792 ways\n",
        "we have 5 choices having the same cost\n",
        "Therefore, there must be at least two different ways to choose, so that the cost will be the same for both choices\n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 54:Page 167"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "print \"A store has an introductory sale on 12 types of chocolates. A customer can choose 1 chocolate of any 5 different types and will be charged no more than 1.75. The store allows repetition in choices\"\n",
      "types=12#Total types of chocolates\n",
      "choice=5#Customer can choose 1 from 5 types\n",
      "c=math.factorial(types)/(math.factorial(choice)*math.factorial(types-choice))#By formula of finding combinations\n",
      "print \"The customer can choose chocolates in \",c,\"ways\"\n",
      "amount=175#In paise\n",
      "ans=int((math.floor((c-1)/amount)+1))#By extended pigeonhole principle\n",
      "print \"we have\",ans,\"choices having the same cost\"\n",
      "choice=(math.factorial(types+choice-1)/(math.factorial(ans)*math.factorial(types+choice-1-ans)))#Considered as pigeonhole\n",
      "print \"If repetitions are allowed, then we have 5 groups and there are C(12+5-1,5)=C(16,5)=\",choice,\"choices\"\n",
      "print \"At least\",int(math.floor(choice/amount)+1),\"choices will have the same cost. So, there are at least 10 ways to make different choices that have the same cost\"\n",
      "#By extended pigeonhole principle\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "A store has an introductory sale on 12 types of chocolates. A customer can choose 1 chocolate of any 5 different types and will be charged no more than 1.75. The store allows repetition in choices\n",
        "The customer can choose chocolates in  792 ways\n",
        "we have 5 choices having the same cost\n",
        "If repetitions are allowed, then we have 5 groups and there are C(12+5-1,5)=C(16,5)= 4368 choices\n",
        "At least 25 choices will have the same cost. So, there are at least 10 ways to make different choices that have the same cost\n"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 55:Page 167"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "total=15#Total number of choices\n",
      "choice=6#Number of choices to select\n",
      "c=math.factorial(total)/(math.factorial(choice)*math.factorial(total-choice))\n",
      "print \"6 numbers out of 1 to 15 can be chosen in\",c,\"ways\"#These are considered as pigeons\n",
      "sum1=0#Initial sum of first 6 numbers is set to zero\n",
      "sum2=0#Initial sum of last 6 numbers is set to zero\n",
      "for i in range(1,7):\n",
      "    sum1=sum1+i#Calulates the sum of first six numbers\n",
      "for i in range(10,16):\n",
      "    sum2=sum2+i#Calulates the sum of first six numbers\n",
      "num_of_sums=(sum2-sum1+1)\n",
      "print \"Number of sums that can be generated is\",num_of_sums#Considered as pigeon holes\n",
      "print \"There are\",int((math.floor((c-1)/num_of_sums)+1)),\"ways\"#By extended pigeon hole principle\n",
      "print \"Hence, there must be at least 90 ways to choose 6 numbers from 1 to 15 so that all the choices have the same sum\"\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "6 numbers out of 1 to 15 can be chosen in 5005 ways\n",
        "Number of sums that can be generated is 55\n",
        "There are 91 ways\n",
        "Hence, there must be at least 90 ways to choose 6 numbers from 1 to 15 so that all the choices have the same sum\n"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 56:Page 167"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "print \"ABCD is the required square. Join AD and BC.Now we get 4 triangles,namely ACD,BCD,ABC,ABD.\"\n",
      "print \"If five points are selected in a square, two of them must belong to the same triangle.\"#According to pigeonhole principle\n",
      "distance=math.sqrt(math.pow(1,2)+math.pow(1,2))\n",
      "print \"The largest distance in a triangle is\",distance,\"So the points must be no more than \",distance,\"inches apart\" \n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "ABCD is the required square. Join AD and BC.Now we get 4 triangles,namely ACD,BCD,ABC,ABD.\n",
        "If five points are selected in a square, two of them must belong to the same triangle.\n",
        "The largest distance in a triangle is 1.41421356237 So the points must be no more than  1.41421356237 inches apart\n"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 57:Page 167"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "print \"The sum of entries in A cannot be more than 64\"#Because A is a boolean matrix and so can hold 0 and 1 only. If all the entries in A are 1, the sum will be 64\n",
      "sum=51#Actual sum of entries in A\n",
      "rows=8#8*8 matrix\n",
      "columns=8#8*8 matrix\n",
      "row_ones=int(math.floor((sum-1)/rows)+1)#Minimum number of ones in a row by extended pigeonole principle\n",
      "print \"One row must have at least\",row_ones,\"ones\"\n",
      "column_ones=int(math.floor((sum-1)/columns)+1)#Minimum number of ones in a column by extended pigeonhole principle\n",
      "print \"One column must have at least\",column_ones,\"ones\"\n",
      "print \"The sum of elements of row and column is\",row_ones+column_ones\n",
      "print \"So, the sum of entries will add up to be more than 13\"\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The sum of entries in A cannot be more than 64\n",
        "One row must have at least 7 ones\n",
        "One column must have at least 7 ones\n",
        "The sum of elements of row and column is 14\n",
        "So, the sum of entries will add up to be more than 13\n"
       ]
      }
     ],
     "prompt_number": 19
    }
   ],
   "metadata": {}
  }
 ]
}