diff options
Diffstat (limited to 'Elements_of_discrete_mathematics')
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter1.ipynb | 498 | ||||
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter10.ipynb | 353 | ||||
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter2.ipynb | 1360 | ||||
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter3.ipynb | 1585 | ||||
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter4.ipynb | 117 | ||||
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter5.ipynb | 2242 | ||||
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter8.ipynb | 62 | ||||
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter9.ipynb | 285 | ||||
| -rwxr-xr-x | Elements_of_discrete_mathematics/screenshots/Chapter10.png | bin | 0 -> 113738 bytes | |||
| -rwxr-xr-x | Elements_of_discrete_mathematics/screenshots/Chapter2.png | bin | 0 -> 128979 bytes | |||
| -rwxr-xr-x | Elements_of_discrete_mathematics/screenshots/Chapter5.png | bin | 0 -> 135244 bytes |
11 files changed, 6502 insertions, 0 deletions
diff --git a/Elements_of_discrete_mathematics/Chapter1.ipynb b/Elements_of_discrete_mathematics/Chapter1.ipynb new file mode 100755 index 00000000..56b9d58d --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter1.ipynb @@ -0,0 +1,498 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:de0a0f66aff079301941637787a8030ad1f216bb6fd8c51b1e13503001244ca2"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "1 Sets and Propositions"
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 11:Page 21"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"To find the number of computers that support one or more of the three kinds of hardware considered, namely;Floating point arithmetic unit, magnetic disk storage and graphical display terminal.\"\n",
+ "A1=2#Set of computers with floating point arithmetic unit\n",
+ "A2=5#Set of computers with magetic disk storage\n",
+ "A3=3#Set of computers with graphical display terminal\n",
+ "A1_intersection_A2=2#Set of computers with floating point arithmetic unit and magentic disk storage\n",
+ "A1_intersection_A3=1#Set of computers with floating point arithmetic unit and graphical display terminal\n",
+ "A2_intersection_A3=3#Set of computers with magnetic disk storage and graphical display terminal \n",
+ "A1_intersection_A2_intersection_A3=1#Set of computers with floating point arithmetic, magnetic disk storage and graphical display terminal\n",
+ "#By the principle of inclusion and exclusion\n",
+ "A1_union_A2_union_A3=A1+A2+A3-A1_intersection_A2-A1_intersection_A3-A2_intersection_A3+A1_intersection_A2_intersection_A3\n",
+ "print A1_union_A2_union_A3,\"of the six computers have one or more of the three kinds of hardware considered\"\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To find the number of computers that support one or more of the three kinds of hardware considered, namely;Floating point arithmetic unit, magnetic disk storage and graphical display terminal.\n",
+ "5 of the six computers have one or more of the three kinds of hardware considered\n"
+ ]
+ }
+ ],
+ "prompt_number": 1
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 12:Page 21"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"We consider 200 students of courses Discrete Mathematics and Economics. A party is being organized which can be attended only by students who are not in either of the courses as these two courses have exams scheduled the next day.\"\n",
+ "students=200# Total number of students \n",
+ "DM=50 # Number of students who have taken Discrete Mathematics\n",
+ "ECO=140 # Number of students who have taken Economics\n",
+ "DM_and_ECO=24 # Number of students who have taken both Discrete Mathematics and Economics\n",
+ "one_or_both=(DM+ECO-DM_and_ECO) # Number of students who have taken either one or both the courses\n",
+ "print \"Number of students who take either one or both the courses is equal to\",one_or_both\n",
+ "print \"Consequently, the number of students who will be at the party is\", (students-one_or_both)\n",
+ "print \"Suppose that 60 of the 200 are underclass students \"\n",
+ "UC_students=60 # Number of underclass students\n",
+ "dm=20 # Number of underclass students who have taken Discrete Mathematics\n",
+ "eco=45 # Number of underclass students who have taken Economics\n",
+ "dm_and_eco=16 # Number of underclass students who have taken both Discrete Mathematics and Economics\n",
+ "# A1 is the set of students in the course Discrete Mathematics\n",
+ "# A2 is the set of students in the course Economics\n",
+ "# A3 is the set of underclass students\n",
+ "A1_union_A2_union_A3=DM+ECO+UC_students-DM_and_ECO-dm-eco+dm_and_eco\n",
+ "print \"Thus, the number of upperclass students who will go to the party is\",(students-A1_union_A2_union_A3)\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "We consider 200 students of courses Discrete Mathematics and Economics. A party is being organized which can be attended only by students who are not in either of the courses as these two courses have exams scheduled the next day.\n",
+ "Number of students who take either one or both the courses is equal to 166\n",
+ "Consequently, the number of students who will be at the party is 34\n",
+ "Suppose that 60 of the 200 are underclass students \n",
+ "Thus, the number of upperclass students who will go to the party is 23\n"
+ ]
+ }
+ ],
+ "prompt_number": 2
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 13:Page 22"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"To find the number of cars which have neither a radio nor an air conditioner nor white-wall tires out of the thirty cars assembled in a factory\"\n",
+ "cars=30 # Total number of cars assembled in a factory\n",
+ "A1=15 # Set of cars with radio\n",
+ "A2=8 # Set of cars with air-conditioner\n",
+ "A3=6 # Set of cars with white-wall tires\n",
+ "A1_intersection_A2_intersection_A3=3\n",
+ "A1_intersection_A2=3 # Since |A1_intersection_A2| >=|A1_intersection_A2_intersection_A3|\n",
+ "A1_intersection_A3=3 # Since |A1_intersection_A3| >=|A1_intersection_A2_intersection_A3|\n",
+ "A2_intersection_A3=3 # Since |A2_intersection_A3| >=|A1_intersection_A2_intersection_A3|\n",
+ "A1_union_A2_union_A3=A1+A2+A3-A1_intersection_A2-A1_intersection_A3-A2_intersection_A3+A1_intersection_A2_intersection_A3 # By the principle of inclusion and exclusion\n",
+ "print \"There are at most\",A1_union_A2_union_A3,\"cars that have one or more options.\"\n",
+ "print \"Consequently,there are at least\",(cars-A1_union_A2_union_A3),\"cars that do not have any options\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To find the number of cars which have neither a radio nor an air conditioner nor white-wall tires out of the thirty cars assembled in a factory\n",
+ "There are at most 23 cars that have one or more options.\n",
+ "Consequently,there are at least 7 cars that do not have any options\n"
+ ]
+ }
+ ],
+ "prompt_number": 3
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 14:Page 24"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"To determine the number of integers between 1 and 250 that are divisible by 2,3,5,7\"\n",
+ "A1=250/2 # Number of integers between 1 and 250 that are divisible by 2\n",
+ "A2=250/3 # Number of integers between 1 and 250 that are divisible by 3\n",
+ "A3=250/5 # Number of integers between 1 and 250 that are divisible by 5\n",
+ "A4=250/7 # Number of integers between 1 and 250 that are divisible by 7\n",
+ "A1_intersection_A2=250/(2*3) # Number of integers between 1 and 250 that are divisible by 2 and 3\n",
+ "A1_intersection_A3=250/(2*5) # Number of integers between 1 and 250 that are divisible by 2 and 5\n",
+ "A1_intersection_A4=250/(2*7) # Number of integers between 1 and 250 that are divisible by 2 and 7\n",
+ "A2_intersection_A3=250/(3*5)# Number of integers between 1 and 250 that are divisible by 3 and 5\n",
+ "A2_intersection_A4=250/(3*7)# Number of integers between 1 and 250 that are divisible by 3 and 7\n",
+ "A3_intersection_A4=250/(5*7)# Number of integers between 1 and 250 that are divisible by 5 and 7\n",
+ "A1_intersection_A2_intersection_A3=250/(2*3*5) # Number of integers between 1 and 250 that are divisible by 2,3 and 5\n",
+ "A1_intersection_A2_intersection_A4=250/(2*3*7) # Number of integers between 1 and 250 that are divisible by 2,3 and 7\n",
+ "A1_intersection_A3_intersection_A4=250/(2*5*7) # Number of integers between 1 and 250 that are divisible by 2,5 and 7\n",
+ "A2_intersection_A3_intersection_A4=250/(3*5*7) # Number of integers between 1 and 250 that are divisible by 3,5 and 7\n",
+ "A1_intersection_A2_intersection_A3_intersection_A4=250/(2*3*5*7) # Number of integers between 1 and 250 that are divisible by 2,3,5 and 7\n",
+ "A1_union_A2_union_A3_union_A4=A1+A2+A3+A4-A1_intersection_A2-A1_intersection_A3-A1_intersection_A4-A2_intersection_A3-A2_intersection_A4-A3_intersection_A4+A1_intersection_A2_intersection_A3+A1_intersection_A2_intersection_A4+A1_intersection_A3_intersection_A4+A2_intersection_A3_intersection_A4-A1_intersection_A2_intersection_A3_intersection_A4\n",
+ "print \"A1 is the set of integers between 1 and 250 that are divisible by 2\"\n",
+ "print \"A2 is the set of integers between 1 and 250 that are divisible by 3\"\n",
+ "print \"A3 is the set of integers between 1 and 250 that are divisible by 5\"\n",
+ "print \"A4 is the set of integers between 1 and 250 that are divisible by 7\"\n",
+ "print \"|A1_union_A2_union_A3_union_A4|=\",A1_union_A2_union_A3_union_A4\n",
+ "\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To determine the number of integers between 1 and 250 that are divisible by 2,3,5,7\n",
+ "A1 is the set of integers between 1 and 250 that are divisible by 2\n",
+ "A2 is the set of integers between 1 and 250 that are divisible by 3\n",
+ "A3 is the set of integers between 1 and 250 that are divisible by 5\n",
+ "A4 is the set of integers between 1 and 250 that are divisible by 7\n",
+ "|A1_union_A2_union_A3_union_A4|= 193\n"
+ ]
+ }
+ ],
+ "prompt_number": 4
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 15:Page 29"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Truth table for (p and q)and (not p)\"\n",
+ "def truth_table(p,q):\n",
+ " return (p and q) and (not p)#Logical representation of the given boolean exoression\n",
+ "print \"p\\tq\\t(p and q)\\t(not p)\\t(p and q) and (not p)\"\n",
+ "for a in (True,False):\n",
+ " for b in (True,False):#Loops that generate the possible input values\n",
+ " print a,\"\\t\",b,\"\\t\",a and b,\"\\t\\t\",not a,\"\\t\",truth_table(a,b)\n",
+ " \n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Truth table for (p and q)and (not p)\n",
+ "p\tq\t(p and q)\t(not p)\t(p and q) and (not p)\n",
+ "True \tTrue \tTrue \t\tFalse \tFalse\n",
+ "True \tFalse \tFalse \t\tFalse \tFalse\n",
+ "False \tTrue \tFalse \t\tTrue \tFalse\n",
+ "False \tFalse \tFalse \t\tTrue \tFalse\n"
+ ]
+ }
+ ],
+ "prompt_number": 5
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 21:Page 33"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Consider the truth tables of (P and negation_P)\"\n",
+ "print \"Here all the entries in the last column are false\"\n",
+ "def truth_table_and(p):\n",
+ " return p and (not p)#Representation of logical AND\n",
+ " \n",
+ "print \"p\\tnegation_p\\tp_and_negation_p\"\n",
+ "print \"---------------------------------------------\"\n",
+ "for q in (True,False):#generates the combination of inputs\n",
+ " res=truth_table_and(q)\n",
+ " print q,\"\\t\\t\",not q,\"\\t\\t\",res\n",
+ " \n",
+ " \n",
+ "print \"Consider the truth tables of (P or negation_P)\"\n",
+ "print \"Here all the entries in the last column are true \"\n",
+ "def truth_table_or(p):\n",
+ " return p or (not p)#Representation of logical OR\n",
+ " \n",
+ "print \"p\\tnegation_p\\tp_or_negation_p\"\n",
+ "print \"----------------------------------------------\"\n",
+ "for q in (True,False):#generates the combination of inputs\n",
+ " res=truth_table_or(q)\n",
+ " print q,\"\\t\\t\",not q,\"\\t\\t\",res\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Consider the truth tables of (P and negation_P)\n",
+ "Here all the entries in the last column are false\n",
+ "p\tnegation_p\tp_and_negation_p\n",
+ "---------------------------------------------\n",
+ "True \t\tFalse \t\tFalse\n",
+ "False \t\tTrue \t\tFalse\n",
+ "Consider the truth tables of (P or negation_P)\n",
+ "Here all the entries in the last column are true \n",
+ "p\tnegation_p\tp_or_negation_p\n",
+ "----------------------------------------------\n",
+ "True \t\tFalse \t\tTrue\n",
+ "False \t\tTrue \t\tTrue\n"
+ ]
+ }
+ ],
+ "prompt_number": 6
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 23:Page 35"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Restaurent 1 says 'Good food is not cheap'\"\n",
+ "print \"Restaurent 2 says 'Cheap food is not good'\"\n",
+ "#Generating prepositions from the given sentences\n",
+ "g='Food is good'\n",
+ "c='Food is cheap'\n",
+ "print \"g->negation c means 'Good food is not cheap'\"\n",
+ "print \"c->negation g means 'Cheap food is not good'\"\n",
+ "def g_implies_negation_c(g,c):\n",
+ " if g==True and not(c)==False:# Implementation of logical implication\n",
+ " return 'False'\n",
+ " else:\n",
+ " return 'True'\n",
+ "\n",
+ "def c_implies_negation_g(g,c):\n",
+ " if c==True and not g==False:# Implementation of logical implication\n",
+ " return 'False'\n",
+ " else:\n",
+ " return 'True'\n",
+ "print \"g\\t\\tc\\t|\\t\\tnegation_g\\t\\t\\tnegation_c\\t\\t\\tg_implies_negation_c\\t\\t\\tc_implies_negation_g\"\n",
+ "print \"---------------------------------------------------------------------------------------------------------------------------------------------------------------\"\n",
+ "for a in (False,True):#Generate the possible inputs\n",
+ " for b in (False,True):\n",
+ " print (\"%5s%10s\\t\\t|%20s%30s%35s%40s\"%(a,b,not a,not b,g_implies_negation_c(a,b),c_implies_negation_g(a,b)))\n",
+ " \n",
+ " \n",
+ "print \"Since both g_implies_negation_c and c_implies_negation_g values in the truth table are similar, it is proved that 'Good food is not cheap' and 'Cheap food is not good are the same'\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Restaurent 1 says 'Good food is not cheap'\n",
+ "Restaurent 2 says 'Cheap food is not good'\n",
+ "g->negation c means 'Good food is not cheap'\n",
+ "c->negation g means 'Cheap food is not good'\n",
+ "g\t\tc\t|\t\tnegation_g\t\t\tnegation_c\t\t\tg_implies_negation_c\t\t\tc_implies_negation_g\n",
+ "---------------------------------------------------------------------------------------------------------------------------------------------------------------\n",
+ "False False\t\t| True True True True\n",
+ "False True\t\t| True False True True\n",
+ " True False\t\t| False True True True\n",
+ " True True\t\t| False False False False\n",
+ "Since both g_implies_negation_c and c_implies_negation_g values in the truth table are similar, it is proved that 'Good food is not cheap' and 'Cheap food is not good are the same'\n"
+ ]
+ }
+ ],
+ "prompt_number": 7
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 24:Page 35"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "def implication(p,q,r,s):#Implementation of logical implicaion\n",
+ " part1=((p and q) or (p and r) )\n",
+ " if part1==True and s==False:\n",
+ " return 'False'\n",
+ " else:\n",
+ " return 'True'\n",
+ "def equivalent(p,q,r,s):#Implementation of logical expression\n",
+ " return (((not p) or((not q) and (not r)))or s)\n",
+ "print \"\\tp\\tq\\tr\\t\\ts\\t\\t|((p and q)or(p and q))->s\\t((negation_p or(negation_q and negation_r))or s)\"\n",
+ "print \"--------------------------------------------------------------------------------------------------------------------------------------\"\n",
+ "for a in (False,True):\n",
+ " for b in (False,True):\n",
+ " for c in (False,True):\n",
+ " for d in (False,True):#Genetates all possible combinations of inputs\n",
+ " print (\"%8s%8s%10s%15s|%35s%35s\" %(a,b,c,d,implication(a,b,c,d),equivalent(a,b,c,d)))\n",
+ " \n",
+ "print \"Therefore, they are proved to be equivalent\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\tp\tq\tr\t\ts\t\t|((p and q)or(p and q))->s\t((negation_p or(negation_q and negation_r))or s)\n",
+ "--------------------------------------------------------------------------------------------------------------------------------------\n",
+ " False False False False| True True\n",
+ " False False False True| True True\n",
+ " False False True False| True True\n",
+ " False False True True| True True\n",
+ " False True False False| True True\n",
+ " False True False True| True True\n",
+ " False True True False| True True\n",
+ " False True True True| True True\n",
+ " True False False False| True True\n",
+ " True False False True| True True\n",
+ " True False True False| False False\n",
+ " True False True True| True True\n",
+ " True True False False| False False\n",
+ " True True False True| True True\n",
+ " True True True False| False False\n",
+ " True True True True| True True\n",
+ "Therefore, they are proved to be equivalent\n"
+ ]
+ }
+ ],
+ "prompt_number": 10
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 55:Page 55"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"EUCLIDEAN ALGORITHM\"\n",
+ "def GCD(n,m):#Euclidean algorithm to compute GCD\n",
+ " if n>=m and (n%m==0):\n",
+ " return m\n",
+ " else:\n",
+ " return GCD(m,n%m)\n",
+ "print \"GCD(25,6) by Euclidean algorithm =\",GCD(25,6),\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "EUCLIDEAN ALGORITHM\n",
+ "GCD(25,6) by Euclidean algorithm = 1\n"
+ ]
+ }
+ ],
+ "prompt_number": 11
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 56:Page 55"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"EUCLIDEAN ALGORITHM\"\n",
+ "def GCD(n,m):#Euclidean algorithm to compute GCD\n",
+ " if n>=m and (n%m==0):\n",
+ " return m\n",
+ " else:\n",
+ " return GCD(m,n%m)\n",
+ "print \"GCD(18,4) by Euclidean algorithm =\",GCD(18,4),#Final comma in all print statements is to eliminate new line character in the end of it\n",
+ "print \"\\nGCD(26,2) by Euclidean algorithm =\",GCD(26,2),\n",
+ "print \"\\nGCD(28,8) by Euclidean algorithm =\",GCD(28,8),\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "EUCLIDEAN ALGORITHM\n",
+ "GCD(18,4) by Euclidean algorithm = 2 \n",
+ "GCD(26,2) by Euclidean algorithm = 2 \n",
+ "GCD(28,8) by Euclidean algorithm = 4\n"
+ ]
+ }
+ ],
+ "prompt_number": 12
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file diff --git a/Elements_of_discrete_mathematics/Chapter10.ipynb b/Elements_of_discrete_mathematics/Chapter10.ipynb new file mode 100755 index 00000000..8b7fc5fa --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter10.ipynb @@ -0,0 +1,353 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:6e9582656e16b2ddb2a1a599466d473ed1824284ac996f30e627d64aae2d0daa"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "10 Groups and rings"
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 09:Page 457"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"(3,4) parity check code.\"\n",
+ "def parity_checker(word):\n",
+ " count=0#Initially the number of 1s is zero\n",
+ " for i in range(0,4):#Ranges till 4 as the size of the received word is 4\n",
+ " if word[i]!='0':\n",
+ " count=count+1#Counts the number of 1s in the given code\n",
+ " \n",
+ " if count%2==0:#Even weight can only be detected by this checker\n",
+ " return \"No, error cannot be detected\"\n",
+ " else:\n",
+ " return \"Yes, error can be detected\"\n",
+ "print \"0010-\",parity_checker(str('0010'))\n",
+ "print \"1001-\",parity_checker(str('1001'))\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "(3,4) parity check code.\n",
+ "0010- Yes, error can be detected\n",
+ "1001- No, error cannot be detected\n"
+ ]
+ }
+ ],
+ "prompt_number": 1
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 10:Page 457"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"(6,7) parity check code.\"\n",
+ "def parity_checker(word):\n",
+ " count=0#Initially the number of 1s is zero\n",
+ " for i in range(0,7):#Ranges till 7 as the received word consists of 7 digits\n",
+ " if word[i]!='0':\n",
+ " count=count+1#Counts the number of 1s in the given code\n",
+ " \n",
+ " if count%2==0:#Even weight can only be detected by this checker\n",
+ " return \"No, error cannot be detected\"\n",
+ " else:\n",
+ " return \"Yes, error can be detected\"\n",
+ " \n",
+ "\n",
+ "print \"1101010-\",parity_checker(str('1101010'))\n",
+ "print \"1010011-\",parity_checker(str('1010011'))\n",
+ "print \"0011111-\",parity_checker(str('0011111'))\n",
+ "print \"1001101-\",parity_checker(str('1001101'))\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "(6,7) parity check code.\n",
+ "1101010- No, error cannot be detected\n",
+ "1010011- No, error cannot be detected\n",
+ "0011111- Yes, error can be detected\n",
+ "1001101- No, error cannot be detected\n"
+ ]
+ }
+ ],
+ "prompt_number": 2
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 11:Page 457"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Consider (2,6) encoding function\"\n",
+ "encode=[\"00\",\"01\",\"10\",\"11\"]#Set of data to be encoded\n",
+ "k=0#Value for filling the distance is initially set to zero\n",
+ "distance=[\"\" for i in range(7)]#Array that can hold all possible combinations of distance value ie. 6 combinations\n",
+ "def e(word):#Function that returns the encoded value\n",
+ " \n",
+ " if word==\"00\":\n",
+ " return str(\"000000\")\n",
+ " elif word==\"10\":\n",
+ " return str(\"101010\")\n",
+ " elif word==\"01\":\n",
+ " return str(\"011110\")\n",
+ " elif word==\"11\":\n",
+ " return str(\"111000\")\n",
+ "def d(word1,word2):\n",
+ " \n",
+ " count=0#Variable that counts the number of 1s\n",
+ " data1=str(e(word1))\n",
+ " \n",
+ " data2=str(e(word2))#Convert into string for indexing which facilitates bitwise operation\n",
+ " \n",
+ " for i in range(0,6):\n",
+ " if data1[i]!=data2[i]:\n",
+ " count=count+1#XOR implementation\n",
+ " return count\n",
+ "for i in range(0,4):\n",
+ " for j in range(i+1,4):\n",
+ " \n",
+ " distance[k]=d(encode[i],encode[j])\n",
+ " print \"d(e(\",encode[i],\"),e(\",encode[j],\"))=\",distance[k]\n",
+ " k=k+1\n",
+ "print \"Minimum distance is\",min(distance)#Finds the minimum distance\n",
+ "print \"Since the minimum distance is\",min(distance),\"the code will detect\",(min(distance)-1),\"or fewer errors\"\n",
+ " \n",
+ " \n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Consider (2,6) encoding function\n",
+ "d(e( 00 ),e( 01 ))= 4\n",
+ "d(e( 00 ),e( 10 ))= 3\n",
+ "d(e( 00 ),e( 11 ))= 3\n",
+ "d(e( 01 ),e( 10 ))= 3\n",
+ "d(e( 01 ),e( 11 ))= 3\n",
+ "d(e( 10 ),e( 11 ))= 2\n",
+ "Minimum distance is 2\n",
+ "Since the minimum distance is 2 the code will detect 1 or fewer errors\n"
+ ]
+ }
+ ],
+ "prompt_number": 3
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 12:Page 458"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Consider (3,9) encoding function\"\n",
+ "encode=[\"000\",\"001\",\"010\",\"011\",\"100\",\"101\",\"110\",\"111\"]#Set of data to be encoded\n",
+ "k=0#Value for filling the distance is initially set to zero\n",
+ "distance=[\"\" for i in range(28)]#Array that can hold all possible combinations of distance value ie. 6 combinations\n",
+ "def e(word):#Function that returns the encoded value\n",
+ " \n",
+ " if word==\"000\":\n",
+ " return str(\"000000000\")\n",
+ " elif word==\"001\":\n",
+ " return str(\"011100101\")\n",
+ " elif word==\"010\":\n",
+ " return str(\"010101000\")\n",
+ " elif word==\"011\":\n",
+ " return str(\"110010001\")\n",
+ " elif word==\"100\":\n",
+ " return str(\"010011010\")\n",
+ " elif word==\"101\":\n",
+ " return str(\"111101011\")\n",
+ " elif word==\"110\":\n",
+ " return str(\"001011000\")\n",
+ " elif word==\"111\":\n",
+ " return str(\"110000111\")\n",
+ "def d(word1,word2):\n",
+ " \n",
+ " count=0#Variable that counts the number of 1s\n",
+ " data1=str(e(word1))\n",
+ " \n",
+ " data2=str(e(word2))#Convert into string for indexing which facilitates bitwise operation\n",
+ " \n",
+ " for i in range(0,9):#Since it is a (3,9) encoder\n",
+ " if data1[i]!=data2[i]:\n",
+ " count=count+1#XOR implementation\n",
+ " return count\n",
+ "for i in range(0,8):#Since there are eight possibilities with three digits\n",
+ " for j in range(i+1,8):\n",
+ " \n",
+ " distance[k]=d(encode[i],encode[j])\n",
+ " print \"d(e(\",encode[i],\"),e(\",encode[j],\"))=\",distance[k]\n",
+ " k=k+1\n",
+ "print \"Minimum distance is\",min(distance)#Finds the minimum distance\n",
+ "print \"Since the minimum distance is\",min(distance),\"the code will detect\",(min(distance)-1),\"or fewer errors\"\n",
+ " \n",
+ " \n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Consider (3,9) encoding function\n",
+ "d(e( 000 ),e( 001 ))= 5\n",
+ "d(e( 000 ),e( 010 ))= 3\n",
+ "d(e( 000 ),e( 011 ))= 4\n",
+ "d(e( 000 ),e( 100 ))= 4\n",
+ "d(e( 000 ),e( 101 ))= 7\n",
+ "d(e( 000 ),e( 110 ))= 3\n",
+ "d(e( 000 ),e( 111 ))= 5\n",
+ "d(e( 001 ),e( 010 ))= 4\n",
+ "d(e( 001 ),e( 011 ))= 5\n",
+ "d(e( 001 ),e( 100 ))= 7\n",
+ "d(e( 001 ),e( 101 ))= 4\n",
+ "d(e( 001 ),e( 110 ))= 6\n",
+ "d(e( 001 ),e( 111 ))= 4\n",
+ "d(e( 010 ),e( 011 ))= 5\n",
+ "d(e( 010 ),e( 100 ))= 3\n",
+ "d(e( 010 ),e( 101 ))= 4\n",
+ "d(e( 010 ),e( 110 ))= 4\n",
+ "d(e( 010 ),e( 111 ))= 6\n",
+ "d(e( 011 ),e( 100 ))= 4\n",
+ "d(e( 011 ),e( 101 ))= 5\n",
+ "d(e( 011 ),e( 110 ))= 5\n",
+ "d(e( 011 ),e( 111 ))= 3\n",
+ "d(e( 100 ),e( 101 ))= 5\n",
+ "d(e( 100 ),e( 110 ))= 3\n",
+ "d(e( 100 ),e( 111 ))= 5\n",
+ "d(e( 101 ),e( 110 ))= 6\n",
+ "d(e( 101 ),e( 111 ))= 4\n",
+ "d(e( 110 ),e( 111 ))= 8\n",
+ "Minimum distance is 3\n",
+ "Since the minimum distance is 3 the code will detect 2 or fewer errors\n"
+ ]
+ }
+ ],
+ "prompt_number": 4
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 13:Page 458"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"To prove the given set to be a group code\"\n",
+ "print \"Since 00000 belongs to the set, identity is satisfied\"\n",
+ "result=[\"\" for i in range(5)]#List that holds the result of xor\n",
+ "word=['00000','10101','01110','11011']#Initial set of encoded words\n",
+ "count=0#Variable that counts the number of pairs that satisfies the closure property\n",
+ "for i in range(0,4):\n",
+ " for j in range(i+1,4):#Possible combinations of words\n",
+ " data1=word[i]\n",
+ " data2=word[j]\n",
+ " print \"\\n\"\n",
+ " print data1,\"exor\",data2,\"=\",\n",
+ " for k in range(0,5):#XOR gate operations\n",
+ " if data1[k]!=data2[k]:\n",
+ " result[k]=1\n",
+ " print result[k],\n",
+ " else:\n",
+ " \n",
+ " result[k]=0\n",
+ " print result[k],\n",
+ " result1=''.join(str(e) for e in result)#Converts list to string for comparing purpose\n",
+ " for r in range(0,4):#Checks if it belongs to the given set of words\n",
+ " \n",
+ " if result1==word[r]:\n",
+ " count=count+1\n",
+ "if count==6:#Since there are 6 possible pairs of words\n",
+ " print \"\\nClosure property is satisfied as we found that if x and y belongs to the set, then x xor y also belongs to the set.\"\n",
+ "else:\n",
+ " print \"Closure property is not satisfied\"\n",
+ " \n",
+ "print \"Associativity can be satisfies and also each element has an inverse.\"\n",
+ "print \"Hence, it is a group code\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To prove the given set to be a group code\n",
+ "Since 00000 belongs to the set, identity is satisfied\n",
+ "\n",
+ "\n",
+ "00000 exor 10101 = 1 0 1 0 1 \n",
+ "\n",
+ "00000 exor 01110 = 0 1 1 1 0 \n",
+ "\n",
+ "00000 exor 11011 = 1 1 0 1 1 \n",
+ "\n",
+ "10101 exor 01110 = 1 1 0 1 1 \n",
+ "\n",
+ "10101 exor 11011 = 0 1 1 1 0 \n",
+ "\n",
+ "01110 exor 11011 = 1 0 1 0 1 \n",
+ "Closure property is satisfied as we found that if x and y belongs to the set, then x xor y also belongs to the set.\n",
+ "Associativity can be satisfies and also each element has an inverse.\n",
+ "Hence, it is a group code\n"
+ ]
+ }
+ ],
+ "prompt_number": 5
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file diff --git a/Elements_of_discrete_mathematics/Chapter2.ipynb b/Elements_of_discrete_mathematics/Chapter2.ipynb new file mode 100755 index 00000000..e3633af0 --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter2.ipynb @@ -0,0 +1,1360 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:2cbc1da90c4c7b54c1033f2cfac603ed9480419c909b33f66bc0d4ea974287c3"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "2 Permutations, combinations, and discrete probability "
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 01:page 69"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"This is to find the number of ways to schedule three exams in five days such that no two exams fall on the same day\"\n",
+ "first_exam=5#number of available days for the first exam\n",
+ "second_exam=4#number of available days for the second exam\n",
+ "third_exam=3#number of available days for the third exam\n",
+ "total=first_exam*second_exam*third_exam#number of combinations\n",
+ "print \"Total number of ways is :\",total\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "This is to find the number of ways to schedule three exams in five days such that no two exams fall on the same day\n",
+ "Total number of ways is : 60\n"
+ ]
+ }
+ ],
+ "prompt_number": 1
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 02:Page 69"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"To find the number of ways in which seven rooms can be allocated to four programmers\"\n",
+ "a=7 # The number of possible rooms for first programmer\n",
+ "b=6 # The number of possible rooms for second programmer\n",
+ "c=5 # The number of possible rooms for third programmer\n",
+ "d=4 # The number of possible rooms for fourth programmer\n",
+ "res=a*b*c*d\n",
+ "print \"The assignment can be made in \",res,\"different ways\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To find the number of ways in which seven rooms can be allocated to four programmers\n",
+ "The assignment can be made in 840 different ways\n"
+ ]
+ }
+ ],
+ "prompt_number": 2
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 03:Page 69"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Number of four digit decimal numbers which have no repeated digits\"\n",
+ "thousands_place=9 # Only nine digits can be placed there. zero cannot be placed there as it will become a three digit number\n",
+ "hundreds_place=9 #As one slot is already filled with a number, the remaining nine digits can only be placed here\n",
+ "tens_place=8 # As two digits have already been used, there are only eight more digits for this place\n",
+ "ones_place=7 # Three digits have occupied three places and only seven digits remain more\n",
+ "total=thousands_place*hundreds_place*tens_place*ones_place\n",
+ "print total,\" possible four digit decimal numbers can be formed without any repetition of digits\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Number of four digit decimal numbers which have no repeated digits\n",
+ "4536 possible four digit decimal numbers can be formed without any repetition of digits\n"
+ ]
+ }
+ ],
+ "prompt_number": 3
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 04:Page 70"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "print \"To find the number of ways in which we can make up strings of four distinct letters followed by three distinct digits\"\n",
+ "def permutations(n,r):\n",
+ " res=math.factorial(n)/math.factorial(n-r)#Mathematical formula for permutations\n",
+ " return res\n",
+ "print \"Total number of possible ways are\",permutations(26,4)*permutations(10,3)\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To find the number of ways in which we can make up strings of four distinct letters followed by three distinct digits\n",
+ "Total number of possible ways are 258336000\n"
+ ]
+ }
+ ],
+ "prompt_number": 4
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 05:Page 70"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"To schedule three examinations within a five day period with no restrictions on the number of examinations scheduled each day\"\n",
+ "print \"The total number of ways are\", pow(5,3)\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To schedule three examinations within a five day period with no restrictions on the number of examinations scheduled each day\n",
+ "The total number of ways are 125\n"
+ ]
+ }
+ ],
+ "prompt_number": 5
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 08:Page 71"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"We print all five-digit numbers on slips of paper with one number on each slip.\"\n",
+ "print \"We have\",pow(10,5),\"distinct five-digit numbers\" \n",
+ "print \"Among these numbers\",pow(5,5),\"of them can be read either right side up or upside down\"#Since the digits 0,1,6,8,9 become 0,1,9,8,6 when they are read upside down, there are pairs of numbers that can share the same slip if the slips are read right side up or upside down\n",
+ "print \"There are\",pow(5,5)-(3*pow(5,2)),\"numbers that can be read either right side up or upside down but will read differently.So,hey can be divided into pairs so that every pair of numbers can share one slip.\"\n",
+ "print \"The total number of distinct slips we need is\",pow(10,5)-((pow(5,5)-3*pow(5,2))/2)\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "We print all five-digit numbers on slips of paper with one number on each slip.\n",
+ "We have 100000 distinct five-digit numbers\n",
+ "Among these numbers 3125 of them can be read either right side up or upside down\n",
+ "There are 3050 numbers that can be read either right side up or upside down but will read differently.So,hey can be divided into pairs so that every pair of numbers can share one slip.\n",
+ "The total number of distinct slips we need is 98475\n"
+ ]
+ }
+ ],
+ "prompt_number": 6
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 09:Page 72"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"There are\",pow(4,7),\"different schedules for a seven day period with four subjects\"\n",
+ "print \"To find the number of schedules which devote at least one day to each subject namely mathematics, physics, chemistry,and economics.\"\n",
+ "print \"A1 denote the set of schedules in which mathematics is never included\"\n",
+ "print \"A2 denote the set of schedules in which physics is never included\"\n",
+ "print \"A3 denote the set of schedules in which chemistry is never included\"\n",
+ "print \"A4 denote the set of schedules in which economics is never included\"\n",
+ "print \"A1_union_A2_union_A3_union_A4 is the set of schedules in which one or more of the subjects is not included. We obtain |A1 U A2 U A3 U A4|=\",\n",
+ "A1=A2=A3=A4=pow(3,7)\n",
+ "A1_intersection_A2=A1_intersection_A3=A1_intersection_A4=A2_intersection_A3=A2_intersection_A4=A3_intersection_A4=pow(2,7)\n",
+ "A1_intersection_A2_intersection_A3=A1_intersection_A2_intersection_A4=A1_intersection_A3_intersection_A4=A2_intersection_A3_intersection_A4=1\n",
+ "A1_intersection_A2_intersection_A3_intersection_A4=0\n",
+ "A1_union_A2_union_A3_union_A4=A1+A2+A3+A4-A1_intersection_A2-A1_intersection_A3-A1_intersection_A4-A2_intersection_A3-A2_intersection_A4-A3_intersection_A4+A1_intersection_A2_intersection_A3+A1_intersection_A2_intersection_A4+A1_intersection_A3_intersection_A4+A2_intersection_A3_intersection_A4\n",
+ "print A1_union_A2_union_A3_union_A4\n",
+ "print \"The number of schedules in which all subjects will be included\",pow(4,7)-A1_union_A2_union_A3_union_A4\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "There are 16384 different schedules for a seven day period with four subjects\n",
+ "To find the number of schedules which devote at least one day to each subject namely mathematics, physics, chemistry,and economics.\n",
+ "A1 denote the set of schedules in which mathematics is never included\n",
+ "A2 denote the set of schedules in which physics is never included\n",
+ "A3 denote the set of schedules in which chemistry is never included\n",
+ "A4 denote the set of schedules in which economics is never included\n",
+ "A1_union_A2_union_A3_union_A4 is the set of schedules in which one or more of the subjects is not included. We obtain |A1 U A2 U A3 U A4|= 7984\n",
+ "The number of schedules in which all subjects will be included 8400\n"
+ ]
+ }
+ ],
+ "prompt_number": 7
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 10:Page 73"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "num_office=12 # Total number of offices to be painted\n",
+ "num_of_green=3 # Number of offices to be painted green\n",
+ "num_of_pink=2 # Number of offices to be painted pink\n",
+ "num_of_yellow=2 # Number of offices to be painted yellow\n",
+ "num_of_white=5 # Number of offices to be painted white\n",
+ "res=math.factorial(num_office)/(math.factorial(num_of_green)*math.factorial(num_of_pink)*math.factorial(num_of_yellow)*math.factorial(num_of_white))#Mathematical implementation of permutation with similarities\n",
+ "print \"Total number of ways to paint 12 offices so that 3 of them are green,2 of them are pink,2 of them are yellow and the remaining with white are \", res\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Total number of ways to paint 12 offices so that 3 of them are green,2 of them are pink,2 of them are yellow and the remaining with white are 166320\n"
+ ]
+ }
+ ],
+ "prompt_number": 8
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 11:Page 73"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "length=5#Total length of the message\n",
+ "num_of_dashes=3#Number of dashes in message \n",
+ "num_of_dots=2#Number of dots in the message\n",
+ "res=math.factorial(length)/(math.factorial(num_of_dashes)*math.factorial(num_of_dots))\n",
+ "print \"The number of different messages that can be represented by a sequence of three dashes and two dots :\",res\n",
+ " \n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "The number of different messages that can be represented by a sequence of three dashes and two dots : 10\n"
+ ]
+ }
+ ],
+ "prompt_number": 9
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 12:Page 74"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "days=7 # Number of days in a week\n",
+ "spaghetti=3 # Number of days a housekeeper wants to serve speghetti in a week\n",
+ "res=math.factorial(days)/(math.factorial(spaghetti)*math.factorial(days-spaghetti))#Mathematical implementation of permutation swith similarities\n",
+ "print \"Number of possible ways in which a house keeper can serve spagetti dinner three times each week is\",res\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Number of possible ways in which a house keeper can serve spagetti dinner three times each week is 35\n"
+ ]
+ }
+ ],
+ "prompt_number": 10
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 13:Page 74"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "length=32 # Total length of binary sequence\n",
+ "num_of_one=7 # Total number of places to be filled with one\n",
+ "def c(n,r):\n",
+ " res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))\n",
+ " return res\n",
+ "print \"Total number of combinations of binary sequences of length 32 in each of which there are exactly seven 1s is \",c(length,num_of_one)\n",
+ "# Because we can view the problem as placing 7 ones in 32 numbered boxes(and then fill the empty boxes with 0s)\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Total number of combinations of binary sequences of length 32 in each of which there are exactly seven 1s is 3365856\n"
+ ]
+ }
+ ],
+ "prompt_number": 12
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 14:Page 74"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "\n",
+ "import math\n",
+ "\n",
+ "total_senators=11 # Total number of senators\n",
+ "committee_mem=5 # Number of members in the committee\n",
+ "\n",
+ "def c(n,r):\n",
+ " res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))\n",
+ " return res\n",
+ "\n",
+ "#Finding number of combinations for selecting a committee of 5 members from 11 senators\n",
+ "print \"The number of ways to select a committee of 5 members among 11 senators are\",c(total_senators,committee_mem);\n",
+ "\n",
+ "# Finding number of combinations to select a committee of five members so that a particular senator , senator A is always included\n",
+ "print \"The number of ways to select a committee of five members so that a particular senator , senator A is always included are\", c(total_senators-1,committee_mem-1);\n",
+ "# Since senator A is always included in the committee, we need to find combinations for the remaining 4 using remaining 10 senators\n",
+ "\n",
+ "# Finding number of combinations to select a committee of five members so that a particular senator , senator A is always excluded\n",
+ "print \"The number of ways to select a committee of five members so that a particular senator , senator A is always excluded are\", c(total_senators-1,committee_mem);\n",
+ "# Since senator A is alway excluded from the committee, the committee members are selected from the remaining 10 senators\n",
+ "\n",
+ "\n",
+ "print \"To find number of combinations to select a committee of five members so that at least one of senator A and senator B will be included\"\n",
+ "\n",
+ "both_A_and_B=c(total_senators-2,committee_mem-2)\n",
+ "print \"Number of selections including both senator A and senator B \",both_A_and_B\n",
+ "# Since both senator A and senator B are already included, we need to find combinations for the remaining 3 committee members using remaining 9 senators\n",
+ "\n",
+ "#Number of ways to select a committee of five members including senator A and excluding senator B\n",
+ "A_but_not_B=c(total_senators-2,committee_mem-1)\n",
+ "print \"Number of selections including senator A and excluding senator B \",A_but_not_B\n",
+ "# Since senator A is included and senator B is always excluded, find combinations for remaining 4 committee members using remaining 9 senators\n",
+ "\n",
+ "#Finding number of combinations to select a committee of five members including senator B and excluding senator A\n",
+ "B_but_not_A=c(total_senators-2,committee_mem-1)\n",
+ "print \"Number of selections including senator B and excluding senator A \",B_but_not_A\n",
+ "# Since senator B is included and senator A is always excluded, find combinations for remaining 4 committee members using remaining 9 senators\n",
+ "\n",
+ "res=both_A_and_B+A_but_not_B+B_but_not_A\n",
+ "print \"Number of ways to select a committee of five members so that at least one of senator A and senator B will be included\",res\n",
+ "\n",
+ "print \"Alternative method\"\n",
+ "\n",
+ "print \"Number of ways to select a committee of five members so that at least one of senator A and senator B will be included\",c(total_senators,committee_mem)-c(total_senators-2,committee_mem)\n",
+ "\n",
+ "\n",
+ "print \"By applying principle of inclusion and exclusion\"\n",
+ "#A1 denotes the set of ways of selection that include senator A\n",
+ "#A2 denotes the set of ways of selection that include senator B\n",
+ "A1=c(total_senators-1,committee_mem-1)\n",
+ "A2=c(total_senators-1,committee_mem-1)\n",
+ "A1_intersection_A2=c(total_senators-2,committee_mem-2)\n",
+ "print \"|A1 U A2|\",A1+A2-A1_intersection_A2\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "The number of ways to select a committee of 5 members among 11 senators are 462\n",
+ "The number of ways to select a committee of five members so that a particular senator , senator A is always included are 210\n",
+ "The number of ways to select a committee of five members so that a particular senator , senator A is always excluded are 252\n",
+ "To find number of combinations to select a committee of five members so that at least one of senator A and senator B will be included\n",
+ "Number of selections including both senator A and senator B 84\n",
+ "Number of selections including senator A and excluding senator B 126\n",
+ "Number of selections including senator B and excluding senator A 126\n",
+ "Number of ways to select a committee of five members so that at least one of senator A and senator B will be included 336\n",
+ "Alternative method\n",
+ "Number of ways to select a committee of five members so that at least one of senator A and senator B will be included 336\n",
+ "By applying principle of inclusion and exclusion\n",
+ "|A1 U A2| 336\n"
+ ]
+ }
+ ],
+ "prompt_number": 13
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 15:Page 75"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "print \"To find the total number of line segments the diagonals are divided into by their intersections\"\n",
+ "def c(n,r):\n",
+ " res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))\n",
+ " return res\n",
+ "nodes=10#Decagon has 10 vertex points\n",
+ "pair=2#Denotes pair of edges to form a disgonal\n",
+ "num_of_diagonals=(c(nodes,pair)-nodes)\n",
+ "print \"Number of diagonals :\",num_of_diagonals\n",
+ "#There are c(10,2) straight lines joining c(10,2) pairs of vertices. But since 10 of them are sides of the decagon, we subtract 10\n",
+ "num_of_intersections=c(nodes,4)\n",
+ "print \"Total number of intersections\",num_of_intersections\n",
+ "# Since for every 4 vertices we can count exactly one intersection between the diagonals\n",
+ "print \"Total number of line segments\",(num_of_diagonals+(2*num_of_intersections))\n",
+ "#Since a diagonal is divided into k+1 line segments when there are k intersecting points lying on it, and since each intersecting point lies on two diagonals\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To find the total number of line segments the diagonals are divided into by their intersections\n",
+ "Number of diagonals : 35\n",
+ "Total number of intersections 210\n",
+ "Total number of line segments 455\n"
+ ]
+ }
+ ],
+ "prompt_number": 14
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 16:Page 76"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "def c(n,r):\n",
+ " res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))#Mathematical implementation of combinations\n",
+ " return res\n",
+ "days=7#Total days in a week\n",
+ "choice=3#Number of days to be selected\n",
+ "print \"The number of ways to choose three out of seven days(with repititions allowed) is c(7+3-1,3)=c(9,3)=\", c(days+choice-1,choice)\n",
+ "print \"The number of ways to choose seven out of three days(with repititions necessarily allowed) is c(3+7-1,7)=c(9,7)=\", c(choice+days-1,days)\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "The number of ways to choose three out of seven days(with repititions allowed) is c(7+3-1,3)=c(9,3)= 84\n",
+ "The number of ways to choose seven out of three days(with repititions necessarily allowed) is c(3+7-1,7)=c(9,7)= 36\n"
+ ]
+ }
+ ],
+ "prompt_number": 15
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 17:Page 76"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "total=7#Total number of diferent markings in a domino\n",
+ "squares=2#Number of squares in a domino\n",
+ "def c(n,r):\n",
+ " res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))\n",
+ " return res\n",
+ "print \"The number of distinct dominoes in a set is C(7+2-1,2)=C(8,2)=\",c(total+squares-1,squares)\n",
+ "#Equivalent to selecting two subjects from seven objects \"one\",\"two\",\"three\",\"four\",\"five\",\"six\",\"blank\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "The number of distinct dominoes in a set is C(7+2-1,2)=C(8,2)= 28\n"
+ ]
+ }
+ ],
+ "prompt_number": 16
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 18:page 76"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "dice=3#Number of dice being rolled\n",
+ "num=6#Total number of outcomes in one dice\n",
+ "def C(n,r):\n",
+ " return math.factorial(n)/(math.factorial(r)*math.factorial(n-r))#Formula to calculate combinations\n",
+ "print \"When three dice are rolled, the number of different outcomes are C(6+3-1,3)=C(8,3)=\",C(num+dice-1,dice),\"because rolling three dice is equivalent to selecting three numbers from six numbers 1,2,3,4,5,6, with repetitions allowed\"\n",
+ "#Since it is equivalent to selecting 3 numbers from 6 numbers namely 1,2,3,4,5,6 with repetitions allowed\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "When three dice are rolled, the number of different outcomes are C(6+3-1,3)=C(8,3)= 56 because rolling three dice is equivalent to selecting three numbers from six numbers 1,2,3,4,5,6, with repetitions allowed\n"
+ ]
+ }
+ ],
+ "prompt_number": 17
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 19:Page 77"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "def C(n,r):\n",
+ " res= math.factorial(n)/(math.factorial(r)*math.factorial(n-r))#Formula to calculate combinations\n",
+ " return res\n",
+ "moves=14#total possible moves in both directions\n",
+ "eastward=7#Possible number of eastward moves in total\n",
+ "northward=7#Possible number of northward moves in total\n",
+ "print \"The number of different paths for a rook to move from the southwest corner of a chessboard to the northwest corner by moving eastward and northward only.\"\n",
+ "print \"0 denote an eastward step and 1 denote a northward step, the number of paths is equal to the number of ways of arranging seven 0s and seven 1s, which is\",math.factorial(14)/(math.factorial(7)*math.factorial(7))\n",
+ "#Formula of permutations involving indistinguishable objects ie.,7 similar eastward moves and 7 similar northward moves\n",
+ "#This is the same as that of placing seven indistinguishable balls in four distinct boxes with no box left empty.\n",
+ "east_move=4#Number of northward moves\n",
+ "north_move=3#Number of eastward moves\n",
+ "num=C(east_move+north_move-1,north_move)#Number of ways of making up a path with four eastward moves\n",
+ "num1=C(north_move+east_move-1,east_move)#Number of ways of making up a path with three northward moves\n",
+ "print \"Number of ways of making up a path with four eastward moves is \",num#Same as that of placing seven indistinguishable balls in four boxes with no box left empty\n",
+ "print \"Number of ways of making up a path with three northward moves is \",num1\n",
+ "print \"Therefore, the answer to our question is \",num,\"*\",num1,\"=\",num*num1\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "The number of different paths for a rook to move from the southwest corner of a chessboard to the northwest corner by moving eastward and northward only.\n",
+ "0 denote an eastward step and 1 denote a northward step, the number of paths is equal to the number of ways of arranging seven 0s and seven 1s, which is 3432\n",
+ "Number of ways of making up a path with four eastward moves is 20\n",
+ "Number of ways of making up a path with three northward moves is 15\n",
+ "Therefore, the answer to our question is 20 * 15 = 300\n"
+ ]
+ }
+ ],
+ "prompt_number": 18
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 20:Page 77"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "chairs=12#Total number of chairs\n",
+ "boys=5#Number of boys to be seated\n",
+ "objects=6#Number of differenr objects\n",
+ "def C(n,r):\n",
+ " return math.factorial(n)/(math.factorial(r)*math.factorial(n-r))#Mathematical implementation of combinations\n",
+ "print \"To determine the number of ways to seat five boys in a row of 12 chairs.The number of arrangements would be\",math.factorial(chairs)/math.factorial(chairs-boys)#Because it is similar to arranging 12 objects which are of 6 different types ie.five boys are of different kind each and the remaining unoccupied chairs are of a kind\n",
+ "print \"Alternative way:\"\n",
+ "print \"Suppose, we arrange the first five boys in a row and then distribute the seven unoccupied chairs arbitrarily either between any two boys or at the two ends. The distribution problem then becomes that of placing seven balls of the same color in six boxes. Thus, the number of ways to do is 5!*C(6+7-1,7)=5!*(12!/7!*5!)=12!/7!=\",math.factorial(boys)*C(objects+(chairs-boys)-1,(chairs-boys))\n",
+ "print \"Suppose, we want to seat the boys so that no two boys are next to each other.\"\n",
+ "print \"5!*C(6+3-1,3)=5!*(8!/3!*5!)=\",math.factorial(5)*C(6+3-1,3)\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To determine the number of ways to seat five boys in a row of 12 chairs.The number of arrangements would be 95040\n",
+ "Alternative way:\n",
+ "Suppose, we arrange the first five boys in a row and then distribute the seven unoccupied chairs arbitrarily either between any two boys or at the two ends. The distribution problem then becomes that of placing seven balls of the same color in six boxes. Thus, the number of ways to do is 5!*C(6+7-1,7)=5!*(12!/7!*5!)=12!/7!= 95040\n",
+ "Suppose, we want to seat the boys so that no two boys are next to each other.\n",
+ "5!*C(6+3-1,3)=5!*(8!/3!*5!)= 6720\n"
+ ]
+ }
+ ],
+ "prompt_number": 33
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 22:page 83"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "from fractions import Fraction\n",
+ "print \"For the experiment of rolling a dice, the sample space consists of six samples. We suppose the probability of occurence of each of these samples is 1/6.\"\n",
+ "print \"probability of getting an odd number is\", (Fraction(1,6)+Fraction(1,6)+Fraction(1,6)) # Since out of the six samples, three of them are odd numbers and the probability of getting each of them is 1/6\n",
+ "print \"On the other hand, suppose that we have a 'crooked' die such that the probability of getting a 1 is 1/3 and the probability of getting each of the remaining numbers is 2/15.\"\n",
+ "print \"The probability of getting an odd number is\",(Fraction(1,3)+Fraction(2,15)+Fraction(2,15)) # Since out of the six samples, three of them are odd numbers and the probability of getting a 1 is 1/3 and each of the remaining is 2/15\n",
+ "print \"The probability of getting an even number is\",(Fraction(2,15)+Fraction(2,15)+Fraction(2,15)) # Since out of the six samples, three of them are even numbers and the probability of getting each of them is 2/15\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "For the experiment of rolling a dice, the sample space consists of six samples. We suppose the probability of occurence of each of these samples is 1/6.\n",
+ "probability of getting an odd number is 1/2\n",
+ "On the other hand, suppose that we have a 'crooked' die such that the probability of getting a 1 is 1/3 and the probability of getting each of the remaining numbers is 2/15.\n",
+ "The probability of getting an odd number is 3/5\n",
+ "The probability of getting an even number is 2/5\n"
+ ]
+ }
+ ],
+ "prompt_number": 20
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 23:Page 84"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "from fractions import Fraction\n",
+ "print \"For the experiment of rolling two dice, the sample space consists of 36 samples. Suppose we want to find the probability of getting a sum of 9 in this experiment. We can get the sum 9 in four different ways such as {(3,6),(4,5),(5,4),(6,3)}\"\n",
+ "print \"probability of getting a sum 9 is\",(Fraction(1,36)+Fraction(1,36)+Fraction(1,36)+Fraction(1,36)) # Since the probability of occurence of each sample is 1/36 and we have four samples which give a sum of 9\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "For the experiment of rolling two dice, the sample space consists of 36 samples. Suppose we want to find the probability of getting a sum of 9 in this experiment. We can get the sum 9 in four different ways such as {(3,6),(4,5),(5,4),(6,3)}\n",
+ "probability of getting a sum 9 is 1/9\n"
+ ]
+ }
+ ],
+ "prompt_number": 21
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 24:Page 84"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "from decimal import *\n",
+ "import math\n",
+ "def c(n,r):\n",
+ " res=math.factorial(n)/(math.factorial(r)*math.factorial(n-r))#Mathematical implementation of combinations\n",
+ " return res\n",
+ "\n",
+ "cards=52#Total number of cards in a deck\n",
+ "poker_cards=5#5 cards make up a poker hand\n",
+ "aces=48.0#Number of outcomes with 4 aces\n",
+ "print \"Consider the problem of dealing a poker hand out of a deck of 52 cards.\"\n",
+ "print \"The sample space consists of\",c(cards,poker_cards),\"sample points corresponding to the c(52,5) different hands that can be dealt\"\n",
+ "print \"Assume that the outcomes have equal probabilities;that is,the probability that a particular hand was dealt is equal to 1/c(52,5)=\",1.0/(c(cards,poker_cards))\n",
+ "getcontext().prec=3#Decides the number of decimal digits\n",
+ "print \"To determine the probability of geting four aces, we note that 48 of the c(52,5) possible outcomes contain four aces;thus,the probability is 48/c(52,5)=\",Decimal(aces)/Decimal(c(cards,poker_cards))\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Consider the problem of dealing a poker hand out of a deck of 52 cards.\n",
+ "The sample space consists of 2598960 sample points corresponding to the c(52,5) different hands that can be dealt\n",
+ "Assume that the outcomes have equal probabilities;that is,the probability that a particular hand was dealt is equal to 1/c(52,5)= 3.84769292332e-07\n",
+ "To determine the probability of geting four aces, we note that 48 of the c(52,5) possible outcomes contain four aces;thus,the probability is 48/c(52,5)= 0.0000185\n"
+ ]
+ }
+ ],
+ "prompt_number": 22
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 25:Page 84"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "from decimal import *\n",
+ "def P(n,r):\n",
+ " res=math.factorial(n)/math.factorial(n-r)#Mathematical implementation of permutations\n",
+ " return res\n",
+ "print \"Consider 23 people out of which the chance is less than 50-50 that no two of them will have the same birthday. Sample space consists of 366^23 samples corresponding to all possible distributions of birthdays of 23 people.\"\n",
+ "print \"Assume: The distributions are equiprobable.\"\n",
+ "getcontext().prec=3#Decides the number of decimal digits\n",
+ "print \"Since out of the 366^23 samples, P(366,23) of them correspond to distributions of birthdays such that no two of the 23 people have the same birthday, the probability that no two people have the same birthday is P(366,23)/366^23=\",(Decimal(P(366,23))/Decimal(pow(366,23)))\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Consider 23 people out of which the chance is less than 50-50 that no two of them will have the same birthday. Sample space consists of 366^23 samples corresponding to all possible distributions of birthdays of 23 people.\n",
+ "Assume: The distributions are equiprobable.\n",
+ "Since out of the 366^23 samples, P(366,23) of them correspond to distributions of birthdays such that no two of the 23 people have the same birthday, the probability that no two people have the same birthday is P(366,23)/366^23= 0.494\n"
+ ]
+ }
+ ],
+ "prompt_number": 23
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 26:Page 84"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "from decimal import *\n",
+ "import math\n",
+ "students=8#Total number of students\n",
+ "freshmen=2#Total number of freshmen\n",
+ "sophomores=2#Total number of sophomores\n",
+ "juniors=2#Total number of juniors\n",
+ "seniors=2#Total number of seniors\n",
+ "sample_space=pow(4,8)#Total number of samples\n",
+ "print \"Eight students are standing in line for an interview. We want to determine the probability that there are exactly two fishermen, two sophomores, two juniors, and two seniors in the line. The sample space consists of 4^8 samples corresponding to all possibilities of classes the students are from. \"\n",
+ "print \"Assume: All the samples are equiprobable\"\n",
+ "getcontext().prec=3#Decides the number of decimal digits\n",
+ "print \"There are 8!/2!2!2!2! samples corresponding to the case in which there are two students from each class. Thus the probability is \",(Decimal(math.factorial(students))/(Decimal(math.factorial(freshmen)*math.factorial(sophomores)*math.factorial(juniors)*math.factorial(seniors)*sample_space)))\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Eight students are standing in line for an interview. We want to determine the probability that there are exactly two fishermen, two sophomores, two juniors, and two seniors in the line. The sample space consists of 4^8 samples corresponding to all possibilities of classes the students are from. \n",
+ "Assume: All the samples are equiprobable\n",
+ "There are 8!/2!2!2!2! samples corresponding to the case in which there are two students from each class. Thus the probability is 0.0385\n"
+ ]
+ }
+ ],
+ "prompt_number": 24
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 28:Page 85 "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"To find the probability of various number of buffers being filled by digital data from a remote site\"\n",
+ "A=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]# A denotes that initial 16 buffers are full\n",
+ "B=[1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31]#B denotes that odd buffers are full\n",
+ "A_inter_B=[1,3,5,7,9,11,13,15]#set representing A intersection B\n",
+ "P_A=0.0#initial probability corresponding to set A is zero\n",
+ "P_A_and_B=0.0#initial probability of set A intersection B is zero\n",
+ "P_B=0.0#initial probability of set B is zero\n",
+ "for q in A:\n",
+ " P_A+=(1.0/561.0)*(33.0-q)\n",
+ "print \"Probability of buffers in set A being filled is\",round(P_A,3)\n",
+ "for q in B:\n",
+ " P_B+=(1.0/561.0)*(33.0-q)\n",
+ "print \"Probability of buffers in set B being filled is\",round(P_B,3)\n",
+ "for q in A_inter_B:\n",
+ " P_A_and_B+=(1.0/561.0)*(33.0-q)\n",
+ "print \"Probability of buffers in set A intersection B being filled is\",round(P_A_and_B,3)\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "To find the probability of various number of buffers being filled by digital data from a remote site\n",
+ "Probability of buffers in set A being filled is 0.758\n",
+ "Probability of buffers in set B being filled is 0.485\n",
+ "Probability of buffers in set A intersection B being filled is 0.357\n"
+ ]
+ }
+ ],
+ "prompt_number": 25
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 29:Page 86"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Out of 100,000 people, 51,500 are female and 48,500 are male. Among the females 9,000 are bald, and among the males 30,200 are bald. Suppose we are to choose a person at random. We shall have S={fb,fh,mb,mh} as the sample space with fb denoting bald female, fh a femele with hair, mb a bald male, and mh a male with hair.\"\n",
+ "P_fb=0.090 # Probability of selecting a bald female \n",
+ "P_fh=0.425 # Probabbility of selecting a female with hair\n",
+ "P_mb=0.302 # Probability of selecting a bald male\n",
+ "p_mh=0.183 # Probability of selecting a male with hair\n",
+ "print \"Given:\"\n",
+ "print \"P(fb)=0.090\"\n",
+ "print \"P(fh)=0.425\"\n",
+ "print \"P(mb)=0.302\"\n",
+ "print \"P(mh)=0.183\"\n",
+ "\n",
+ "print \"Let A denote the event that a bald person was chosen\"\n",
+ "print \"Let B denote the event that a female was chosen\"\n",
+ "print \"Then A intersection B is the event that a bald female was chosen, A union B the event that a bald person or a female was chosen,A EXOR B the event that a female with hair or a bald male was chosen and B-A the event that a female with hair was chosen.\"\n",
+ "P_A=P_fb+P_mb # Includes both male bald and female bald\n",
+ "P_B=P_fb+P_fh # Includes all females\n",
+ "P_A_intersection_B=P_fb # iIncludes all females who are bald\n",
+ "P_A_union_B=P_fb+P_fh+P_mb # Includes all females and bald male\n",
+ "P_A_EXOR_B=P_fh+P_mb # Includes female with hair and bald male\n",
+ "P_B_minus_A=P_fh # Includes only female with hair\n",
+ "print \"P(A)=\",P_A\n",
+ "print \"P(B)\",P_B\n",
+ "print \"P(A intersection B)=\",P_A_intersection_B\n",
+ "print \"P(A union B)=\",P_A_union_B\n",
+ "print \"P(A EXOR B)=\",P_A_EXOR_B\n",
+ "print \"P(B-A)=\",P_B_minus_A\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Out of 100,000 people, 51,500 are female and 48,500 are male. Among the females 9,000 are bald, and among the males 30,200 are bald. Suppose we are to choose a person at random. We shall have S={fb,fh,mb,mh} as the sample space with fb denoting bald female, fh a femele with hair, mb a bald male, and mh a male with hair.\n",
+ "Given:\n",
+ "P(fb)=0.090\n",
+ "P(fh)=0.425\n",
+ "P(mb)=0.302\n",
+ "P(mh)=0.183\n",
+ "Let A denote the event that a bald person was chosen\n",
+ "Let B denote the event that a female was chosen\n",
+ "Then A intersection B is the event that a bald female was chosen, A union B the event that a bald person or a female was chosen,A EXOR B the event that a female with hair or a bald male was chosen and B-A the event that a female with hair was chosen.\n",
+ "P(A)= 0.392\n",
+ "P(B) 0.515\n",
+ "P(A intersection B)= 0.09\n",
+ "P(A union B)= 0.817\n",
+ "P(A EXOR B)= 0.727\n",
+ "P(B-A)= 0.425\n"
+ ]
+ }
+ ],
+ "prompt_number": 26
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 31:Page 88"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Out of 100,000 people, 51,500 are female and 48,500 are male. Among the females 9,000 are bald, and among the males 30,200 are bald. Suppose we are to choose a person at random.We shall have S={fb,fh,mb,mh} as the sample space with fb denoting bald female, fh a femele with hair, mb a bald male, and mh a male with hair.\"\n",
+ "print \"Let A denote the event that a bald person was chosen, B the event that a female was chosen, and C the event that a male was chosen.\"\n",
+ "P_fb=0.090 # Probability of selecting a bald female \n",
+ "P_fh=0.425 # Probabbility of selecting a female with hair\n",
+ "P_mb=0.302 # Probability of selecting a bald male\n",
+ "P_mh=0.183 # Probability of selecting a male with hair\n",
+ "print \"Given:\"\n",
+ "print \"P(fb)=0.090\"\n",
+ "print \"P(fh)=0.425\"\n",
+ "print \"P(mb)=0.302\"\n",
+ "print \"P(mh)=0.183\"\n",
+ "P_A=P_fb+P_mb # Includes both male bald and female bald\n",
+ "P_B=P_fb+P_fh # Includes all female\n",
+ "P_C=P_mb+P_mh # Includes all male\n",
+ "P_A_intersection_C=P_mb # Includes all males who are bald\n",
+ "P_C_intersection_A=P_mb # Since A intersection C and C intersection A are the same, this also includes all males who are bald\n",
+ "P_A_intersection_B=P_fb # Includes all females who are bald\n",
+ "P_B_intersection_A=P_fb # Since A intersection B and B intersection A are the same,this also includes all females who are bald\n",
+ "\n",
+ "P_A_given_B=P_A_intersection_B/P_B # By conditional probability\n",
+ "print \"P(A|B)=\",round(P_A_given_B,3);\n",
+ "print \"This is less than P(A) which is 0.392\"\n",
+ "P_A_given_C=P_A_intersection_C/P_C # By conditional probability\n",
+ "\n",
+ "print \"P(A|C)=\",round(P_A_given_C,3)\n",
+ "print \"This is quite a bit greater than P(A)\"\n",
+ "P_B_given_A=P_B_intersection_A/P_A# By conditional probability\n",
+ "print \"P(B|A)=\",round(P_B_given_A,2)\n",
+ "P_C_given_A=P_C_intersection_A/P_A# By conditional probability\n",
+ "print \"P(C|A)=\",round(P_C_given_A,2)\n",
+ "print \"Indeed, although P(B) is slightly larger than P(C),P(B|A) is much smaller than P(C|A)\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Out of 100,000 people, 51,500 are female and 48,500 are male. Among the females 9,000 are bald, and among the males 30,200 are bald. Suppose we are to choose a person at random.We shall have S={fb,fh,mb,mh} as the sample space with fb denoting bald female, fh a femele with hair, mb a bald male, and mh a male with hair.\n",
+ "Let A denote the event that a bald person was chosen, B the event that a female was chosen, and C the event that a male was chosen.\n",
+ "Given:\n",
+ "P(fb)=0.090\n",
+ "P(fh)=0.425\n",
+ "P(mb)=0.302\n",
+ "P(mh)=0.183\n",
+ "P(A|B)= 0.175\n",
+ "This is less than P(A) which is 0.392\n",
+ "P(A|C)= 0.623\n",
+ "This is quite a bit greater than P(A)\n",
+ "P(B|A)= 0.23\n",
+ "P(C|A)= 0.77\n",
+ "Indeed, although P(B) is slightly larger than P(C),P(B|A) is much smaller than P(C|A)\n"
+ ]
+ }
+ ],
+ "prompt_number": 27
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 32:Page 89"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "from fractions import Fraction\n",
+ "from decimal import *\n",
+ "print \"A coin was chosen at random and tossed.\"\n",
+ "p_fc_hd=Fraction('1/3') # Probability that a fair coin was chosen and head shows\n",
+ "p_fc_tl=Fraction('1/3') # Probability that a fair coin was chosen and tail shows\n",
+ "p_ufc_hd=Fraction('1/12') # Probability that a unfair coin was chosen and head shows\n",
+ "p_ufc_tl=Fraction('1/4') # Probability that a unfair coin was chosen and head shows\n",
+ "\n",
+ "print \"The probability that head shows is\",(Fraction(p_fc_hd)+Fraction(p_ufc_hd)) # Probability of head in both fair and unfair coins\n",
+ "print \"The probability that an unfair coin was chosen is\",(Fraction(p_ufc_hd)+Fraction(p_ufc_tl)) # Probability of head and tail in unfair coin\n",
+ "p_head=(Fraction(p_fc_hd)+Fraction(p_ufc_hd))\n",
+ "print \"The conditional probability that an unfair coin was chosen given that head shows is\",(Fraction(p_ufc_hd)/Fraction(p_head))# By conditional probability, probability of head in unfair coin to the probabilty of head in both fair and unfair coins\n",
+ "print \"The conditional probability that head shows given that an unfair coin was chosen is\",(Fraction(p_ufc_hd)/(Fraction(p_ufc_hd)+Fraction(p_ufc_tl))) # By conditional probability,probability of head in unfair coin to the probability of head and tail in unfair coin\n",
+ "\n",
+ "\n",
+ "\n",
+ "\n",
+ "\n",
+ "\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "A coin was chosen at random and tossed.\n",
+ "The probability that head shows is 5/12\n",
+ "The probability that an unfair coin was chosen is 1/3\n",
+ "The conditional probability that an unfair coin was chosen given that head shows is 1/5\n",
+ "The conditional probability that head shows given that an unfair coin was chosen is 1/4\n"
+ ]
+ }
+ ],
+ "prompt_number": 28
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 33:Page 89"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "from fractions import Fraction\n",
+ "def P(n,r):\n",
+ " res=math.factorial(n)/math.factorial(n-r)\n",
+ " return res\n",
+ "faces=6#Number of faces in a dice\n",
+ "dice=3#Number of dice that were rolled\n",
+ "print \"Three dice were rolled.\"\n",
+ "print \"Given: No two faces were the same.\"\n",
+ "print \"Let A denote the event that there was an ace.\"\n",
+ "print \"Let B denote the event that no two faces were the same.\"\n",
+ "P_B=Fraction(P(faces,dice))/Fraction(pow(faces,dice)) # Sample space is pow(6,3) sice three dice are rolled.\n",
+ "P_A_intersection_B=Fraction(dice*P(faces-1,dice-1))/Fraction(pow(faces,dice))#Since A has occured, it cannot repeat again. So faces and dice are reduced by 1\n",
+ "P_A_given_B=Fraction(P_A_intersection_B)/Fraction(P_B) #By conditional probability\n",
+ "print \"P(A|B)=\",P_A_given_B\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Three dice were rolled.\n",
+ "Given: No two faces were the same.\n",
+ "Let A denote the event that there was an ace.\n",
+ "Let B denote the event that no two faces were the same.\n",
+ "P(A|B)= 1/2\n"
+ ]
+ }
+ ],
+ "prompt_number": 29
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 34:Page 90"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "from fractions import Fraction\n",
+ "print \"We define events and probabilities as follows.\"\n",
+ "print \"E:Introduction of computer education\"\n",
+ "print \"A1:Mr.X is selected as chairman\"\n",
+ "print \"A2:Mr.Y is selected as chairman\"\n",
+ "print \"A3:Mr.Z is selected as chairman\"\n",
+ "P_A1=Fraction('4/9') # Probability of Mr.X being selected\n",
+ "P_A2=Fraction('2/9') # Probability of Mr.Y being selected\n",
+ "P_A3=Fraction('3/9') # Probability of Mr.Z being selected\n",
+ "P_E_given_A1=Fraction('3/10') # probability that there was computer education in the college when Mr.X is selected as a chairman\n",
+ "P_E_given_A2=Fraction('5/10') # probability that there was computer education in the college when Mr.Y is selected as a chairman\n",
+ "P_E_given_A3=Fraction('8/10') # probability that there was computer education in the college when Mr.Z is selected as a chairman\n",
+ "print \"P(E)=P[(E INTERSECTION A1) UNION (E INTERSECTION A2) UNION (E INTERSECTION A3)]\"\n",
+ "print \"=P(E INTERSECTION A1) + P(E INTERSECTION A2) + P(E INTERSECTION A3)\"\n",
+ "print \"=P(A1)P(E|A1)+P(A2)P(E|A2)+P(A3)P(E|A3)\" # Since by conditional probability, P(E|A1)=P(E intersection A1)/P(A1)\n",
+ "print \"=\",P_A1,\"*\",P_E_given_A1,\"+\",P_A2,\"*\",P_E_given_A2,\"+\",P_A3,\"*\",P_E_given_A3,\"=\",\n",
+ "P_E=(P_A1*P_E_given_A1)+(P_A2*P_E_given_A2)+(P_A3*P_E_given_A3) # P_E denotes the probability of computer education in the college\n",
+ "print P_E\n",
+ "print \"So, the probability that there was computer education in the college is\",P_E\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "We define events and probabilities as follows.\n",
+ "E:Introduction of computer education\n",
+ "A1:Mr.X is selected as chairman\n",
+ "A2:Mr.Y is selected as chairman\n",
+ "A3:Mr.Z is selected as chairman\n",
+ "P(E)=P[(E INTERSECTION A1) UNION (E INTERSECTION A2) UNION (E INTERSECTION A3)]\n",
+ "=P(E INTERSECTION A1) + P(E INTERSECTION A2) + P(E INTERSECTION A3)\n",
+ "=P(A1)P(E|A1)+P(A2)P(E|A2)+P(A3)P(E|A3)\n",
+ "= 4/9 * 3/10 + 2/9 * 1/2 + 1/3 * 4/5 = 23/45\n",
+ "So, the probability that there was computer education in the college is 23/45\n"
+ ]
+ }
+ ],
+ "prompt_number": 30
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 35:Page 91"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"A1: Event that the selected item was produced by machine M1\"\n",
+ "print \"A2: Event that the selected item was produced by machine M2\"\n",
+ "print \"A3: Event that the selected item was produced by machine M3\"\n",
+ "print \"E: Event that the selected item is defective\"\n",
+ "P_A1=0.2 # The probability that an item selected at random from the entire batch was produced by machine M1\n",
+ "P_A2=0.3 # The probability that an item selected at random from the entire batch was produced by machine M2\n",
+ "P_A3=0.5 # The probability that an item selected at random from the entire batch was produced by machine M3\n",
+ "P_E_given_A1=0.01 # Probability that an item produced by machine M1 will be defective\n",
+ "P_E_given_A2=0.02 # Probability that an item produced by machine M2 will be defective\n",
+ "P_E_given_A3=0.03 # Probability that an item produced by machine M3 will be defective\n",
+ "print \"We require to calculate the conditional probability P(A3|E)\"\n",
+ "print \"Using bayes' theorem\"\n",
+ "P_A3_given_E=(P_A3*P_E_given_A3)/((P_A1*P_E_given_A1)+(P_A2*P_E_given_A2)+(P_A3*P_E_given_A3))\n",
+ "print \"The probability that this item was produced by machine M3 is\",round(P_A3_given_E,3)\n",
+ " \n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "A1: Event that the selected item was produced by machine M1\n",
+ "A2: Event that the selected item was produced by machine M2\n",
+ "A3: Event that the selected item was produced by machine M3\n",
+ "E: Event that the selected item is defective\n",
+ "We require to calculate the conditional probability P(A3|E)\n",
+ "Using bayes' theorem\n",
+ "The probability that this item was produced by machine M3 is 0.652\n"
+ ]
+ }
+ ],
+ "prompt_number": 31
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 36:Page 95"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "from fractions import Fraction\n",
+ "import math\n",
+ "from decimal import *\n",
+ "print \"Estimating the likelihood that there will be a 1 hour examination when the professor is scheduled to get out of town\"\n",
+ "print \"Sample space={x1,x2,x3,x4}\"\n",
+ "P_X1=Fraction('1/2')#X1 denotes professor out of town and exam given\n",
+ "P_X2=Fraction('1/16')#X2 denotes professor out of town and exam not given\n",
+ "P_X3=Fraction('3/16')#X3 denotes professor in town and exam given\n",
+ "P_X4=Fraction('1/4')#X4 denotes professor in town and exam not given\n",
+ "print \"A denotes the event that exam is given and B denote the event that professor is out of town\"\n",
+ "P_A=P_X1+P_X3#Probability of A\n",
+ "P_A_numerator=P_A.numerator#Separating numerator and denominators in all P(A)\n",
+ "P_A_denominator=P_A.denominator\n",
+ "P_A_given_B=P_X1/(P_X1+P_X2)#Probability of P(A|B)\n",
+ "P_A_given_B_numerator=P_A_given_B.numerator#Separating numerators and denominators in P(A|B)\n",
+ "P_A_given_B_denominator=P_A_given_B.denominator\n",
+ "print \"Probability that the exam is given is \",P_A\n",
+ "print \"Probability of exam given that the profession is out of town is \",P_A_given_B\n",
+ "log_P_A_numerator=round(math.log(P_A_numerator,2),2)#Logrithm of 11\n",
+ "log_P_A_denominator=math.log(P_A_denominator,2)#Logrithm of 16\n",
+ "neg_log_P_A=-log_P_A_numerator+log_P_A_denominator#Negative logrithm of P(A).SInce log(a/b)=lob(a)-log(b)\n",
+ "getcontext().prec=2#Decides the number of digits after decimal point\n",
+ "print \"The needed information to determine that an examination will be given is \",neg_log_P_A,\"bits\"\n",
+ "log_P_A_given_B_numerator=math.log(P_A_given_B_numerator,2)#Logrithm of \n",
+ "log_P_A_given_B_denominator=round(math.log(P_A_given_B_denominator,2),2)#Logrithm of 9\n",
+ "print \"Information provided by the fact that the professor is out of town on the fact that examination is given is I(A,B)=\",(-log_P_A_numerator+log_P_A_denominator+log_P_A_given_B_numerator-log_P_A_given_B_denominator),\"bits\"\n",
+ "print \"C denotes the event that the professor is in town\"\n",
+ "P_A_given_C=P_X3/(P_X3+P_X4)\n",
+ "print \"Probability that the examination is given when the professor is in town is \",P_A_given_C\n",
+ "P_A_given_C_numerator=P_A_given_C.numerator#Separating numerators and denominators in P(A|C)\n",
+ "P_A_given_C_denominator=P_A_given_C.denominator\n",
+ "log_P_A_given_C_numerator=round(math.log(P_A_given_C_numerator,2),2)\n",
+ "log_P_A_given_C_denominator=math.log(P_A_given_C_denominator,2)\n",
+ "print \"I(A,C)=\",round((-log_P_A_numerator+log_P_A_denominator+log_P_A_given_C_numerator-log_P_A_given_C_denominator),2)\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Estimating the likelihood that there will be a 1 hour examination when the professor is scheduled to get out of town\n",
+ "Sample space={x1,x2,x3,x4}\n",
+ "A denotes the event that exam is given and B denote the event that professor is out of town\n",
+ "Probability that the exam is given is 11/16\n",
+ "Probability of exam given that the profession is out of town is 8/9\n",
+ "The needed information to determine that an examination will be given is 0.54 bits\n",
+ "Information provided by the fact that the professor is out of town on the fact that examination is given is I(A,B)= 0.37 bits\n",
+ "C denotes the event that the professor is in town\n",
+ "Probability that the examination is given when the professor is in town is 3/7\n",
+ "I(A,C)= -0.69\n"
+ ]
+ }
+ ],
+ "prompt_number": 32
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file diff --git a/Elements_of_discrete_mathematics/Chapter3.ipynb b/Elements_of_discrete_mathematics/Chapter3.ipynb new file mode 100755 index 00000000..fe88d5b7 --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter3.ipynb @@ -0,0 +1,1585 @@ +{
+ "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": {}
+ }
+ ]
+}
\ No newline at end of file diff --git a/Elements_of_discrete_mathematics/Chapter4.ipynb b/Elements_of_discrete_mathematics/Chapter4.ipynb new file mode 100755 index 00000000..2adb4c8f --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter4.ipynb @@ -0,0 +1,117 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:a85fddad5ca1dfcfd83be3de3e24c0c6e6b3cfc061b0141fb4ecc95c31a3f057"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "4 Graphs and planar graphs"
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 03:Page 199 "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"GRAPH TRAVERSLS-DEPTH FIRST SEARCH\"\n",
+ "graph={'A': ['G','B'],\n",
+ " 'B': ['C'],\n",
+ " 'C': ['E','D'],\n",
+ " 'D': [],\n",
+ " 'E': ['D','F'],\n",
+ " 'F': ['A'],\n",
+ " 'G': ['F']}#Input the graph details using a sequence data structure \n",
+ "\n",
+ "def dfs(graph,start):\n",
+ " path=[]#Initially the path is empty, as no nodes are visited\n",
+ " stack=[start]#The starting node is pushed into the stack\n",
+ " while stack!=[]:\n",
+ " visited=stack.pop()#The node is marked as visited\n",
+ " if visited not in path:\n",
+ " path.append(visited)#The node is added to the path\n",
+ " for w in reversed(graph[visited]):#The node is checked to see if it has any adjacent nodes. \n",
+ " if w not in path:\n",
+ " stack.append(w)#Adjacent nodes if any without being visited are added to the stack\n",
+ " return path\n",
+ "print \"path=\",dfs(graph,'A')#The sequence and the starting nodes are given as input \n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "GRAPH TRAVERSLS-DEPTH FIRST SEARCH\n",
+ "path= ['A', 'G', 'F', 'B', 'C', 'E', 'D']\n"
+ ]
+ }
+ ],
+ "prompt_number": 1
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 04:Page 201"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"GRAPH TRAVERSALS-BREADTH FIRST SEARCH\"\n",
+ "graph={'A': set(['G','B']),\n",
+ " 'B': set(['C']),\n",
+ " 'C': set(['D','E']),\n",
+ " 'D': set([]),\n",
+ " 'E': set(['D','F']),\n",
+ " 'F': set(['A']),\n",
+ " 'G': set(['F'])}#Input the graph information\n",
+ "\n",
+ "def bfs(graph,start):\n",
+ " path=[]#Initially path is empty as no nodes are visited\n",
+ " queue=[start]#The start node is added to the queue\n",
+ " while queue:\n",
+ " v=queue.pop(0)#Always the first node is only popped\n",
+ " if v not in path:\n",
+ " path+=[v]#The popped node is added to the path\n",
+ " queue+=graph[v]#The adjacent nodes of the visited nodes are inserted in the queue\n",
+ " return path\n",
+ "print \"path=\",bfs(graph,'A')\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "GRAPH TRAVERSALS-BREADTH FIRST SEARCH\n",
+ "path= ['A', 'B', 'G', 'C', 'F', 'E', 'D']\n"
+ ]
+ }
+ ],
+ "prompt_number": 2
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file diff --git a/Elements_of_discrete_mathematics/Chapter5.ipynb b/Elements_of_discrete_mathematics/Chapter5.ipynb new file mode 100755 index 00000000..79b98a7c --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter5.ipynb @@ -0,0 +1,2242 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:ecb9bbda12d6fdb3e39aeaf2fe5ef561c8a8f84a2def1400dc3ed8df4da10809"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "5 Trees and cut sets"
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 01:Page 263"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Problem of connecting 19 lamps to a single electric outlet by using extension cords each of which has four outlets\"\n",
+ "total_lamps=19#Total lamps to be connected to a single electric outlet\n",
+ "outlets=4#Number of outlets in each extension cord.\n",
+ "def calc(lamp,outlet):\n",
+ " return (lamp-1)/(outlets-1)#Since any such connection is a quaternary tree with the single outlet connected to the root of the tree\n",
+ "print \"Although there are many ways to connect the lights,\",calc(total_lamps,outlets),\"extension cords are always required.\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Problem of connecting 19 lamps to a single electric outlet by using extension cords each of which has four outlets\n",
+ "Although there are many ways to connect the lights, 6 extension cords are always required.\n"
+ ]
+ }
+ ],
+ "prompt_number": 1
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 02:Page 263"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"A hypothetical computer has an instruction which computes the sum of three numbers.\"\n",
+ "nodes=9#Number of leaf nodes in each regular ternary tree to compute the sum of nine numbers\n",
+ "num=3#An instruction adds only three numbers\n",
+ "def calc(node,num):\n",
+ " return (nodes-1)/(num-1)\n",
+ "print \"The addition instruction will be executed \",calc(nodes,num),\"times to find the sum of nine numbers\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "A hypothetical computer has an instruction which computes the sum of three numbers.\n",
+ "The addition instruction will be executed 4 times to find the sum of nine numbers\n"
+ ]
+ }
+ ],
+ "prompt_number": 2
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 03:Page 278"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Implementation of Kruskal's algorithm\"\n",
+ "n=input(\"Enter the number of nodes\")\n",
+ "print \"Enter the adjacency matrix\"\n",
+ "cost=[[\"\" for i in range(n+1)]for j in range(n+1)]#Matrix is declared\n",
+ "parent=[\"\" for i in range(n+1)]#List is declared\n",
+ "mincost=0#Initially mincost is zero\n",
+ "for i in range(1,n+1):\n",
+ " for j in range(1,n+1):#To include n, have used n+1\n",
+ " print \"Enter the input for\",i,j\n",
+ " cost[i][j]=input()#Gets input matrix\n",
+ " if cost[i][j]==0:\n",
+ " cost[i][j]=999#Max cost is assigned if there is no edge between the specified nodes\n",
+ "ne=1#Count of visited nodes\n",
+ "def find(i):\n",
+ " while parent[i]:\n",
+ " i=parent[i]\n",
+ " return i\n",
+ "def uni(i,j):\n",
+ " if i!=j:\n",
+ " parent[j]=i\n",
+ " return 1\n",
+ " return 0\n",
+ "\n",
+ "print \"\\nThe edges of the minimum cost spanning tree is\"\n",
+ "while ne<n:\n",
+ " min=999\n",
+ " for i in range(1,n+1):\n",
+ " for j in range(1,n+1):\n",
+ " if cost[i][j]<min:\n",
+ " min=cost[i][j]#If the new node has minimum value,takes the new value\n",
+ " global a\n",
+ " global v\n",
+ " global b\n",
+ " a=i\n",
+ " global u\n",
+ " u=i\n",
+ " b=j\n",
+ " v=j\n",
+ " u=find(u)\n",
+ " v=find(v)\n",
+ " if uni(u,v):\n",
+ " print \"\\nEdge\",ne,\"(\",a,\" ,\",b,\")=\",min\n",
+ " ne=ne+1\n",
+ " mincost=mincost+min\n",
+ " cost[a][b]=cost[b][a]=999\n",
+ "print \"\\nMinimum cost=\",mincost\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Implementation of Kruskal's algorithm\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the number of nodes9\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the adjacency matrix\n",
+ "Enter the input for 1 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "9\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "9\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 8 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "8\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 8\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "8\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 9 9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "The edges of the minimum cost spanning tree is\n",
+ "\n",
+ "Edge 1 ( 2 , 9 )= 1\n",
+ "\n",
+ "Edge 2 ( 6 , 8 )= 1\n",
+ "\n",
+ "Edge 3 ( 1 , 9 )= 2\n",
+ "\n",
+ "Edge 4 ( 2 , 4 )= 2\n",
+ "\n",
+ "Edge 5 ( 2 , 3 )= 4\n",
+ "\n",
+ "Edge 6 ( 6 , 9 )= 4\n",
+ "\n",
+ "Edge 7 ( 6 , 7 )= 5\n",
+ "\n",
+ "Edge 8 ( 5 , 6 )= 6\n",
+ "\n",
+ "Minimum cost= 25\n"
+ ]
+ }
+ ],
+ "prompt_number": 3
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 04:Page 280"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"PRIM'S ALGORITHM\"\n",
+ "n=input(\"Enter the number of nodes\")\n",
+ "print \"Enter the adjacency matrix\"\n",
+ "cost=[[\"\" for i in range(n+1)]for j in range(n+1)]#Matrix declaration\n",
+ "visited=[0 for i in range(n+1)]#List declaration\n",
+ "n1=n+1#For use in range()\n",
+ "for i in range(1,n+1):\n",
+ " for j in range(1,n+1):\n",
+ " print \"Enter the input for\",i,j\n",
+ " cost[i][j]=input()#Get the adjacency matrix\n",
+ " if(cost[i][j]==0):\n",
+ " cost[i][j]=999#If there is no edge between two nodes, assign high cost\n",
+ "visited[1]=1#First node is initially visited\n",
+ "ne=1#Variable for node counting\n",
+ "mincost=0#Initially mincost is zero\n",
+ "\n",
+ "print \"\\n\"\n",
+ "while ne<n:\n",
+ " min=999\n",
+ " for i in range(1,n):\n",
+ " for j in range(1,n+1):#Generates all nodes\n",
+ " if(cost[i][j]<min):\n",
+ " if(visited[i]!=0):\n",
+ " min=cost[i][j]#Changes value if the new node has less cost\n",
+ " global a\n",
+ " a=i\n",
+ " u=i\n",
+ " global b\n",
+ " b=j\n",
+ " global v\n",
+ " v=j\n",
+ " if(visited[v]==0 or visited[u]==0):\n",
+ " \n",
+ " print \"\\nedge\",ne,\":(\",a,\" \",b,\")\",\"cost\",min\n",
+ " ne=ne+1\n",
+ " mincost=mincost+min\n",
+ " visited[b]=1\n",
+ " cost[a][b]=cost[b][a]=999\n",
+ "print \"minimum cost=\",mincost\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "PRIM'S ALGORITHM\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the number of nodes7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the adjacency matrix\n",
+ "Enter the input for 1 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 1 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 2 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 3 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 4 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 5 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "2\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 6 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "3\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 5\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 6\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the input for 7 7\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "\n",
+ "\n",
+ "edge 1 :( 1 6 ) cost 1\n",
+ "\n",
+ "edge 2 :( 1 2 ) cost 2\n",
+ "\n",
+ "edge 3 :( 2 7 ) cost 1\n",
+ "\n",
+ "edge 4 :( 6 5 ) cost 2\n",
+ "\n",
+ "edge 5 :( 5 4 ) cost 3\n",
+ "\n",
+ "edge 6 :( 2 3 ) cost 5\n",
+ "minimum cost= 14\n"
+ ]
+ }
+ ],
+ "prompt_number": 4
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file diff --git a/Elements_of_discrete_mathematics/Chapter8.ipynb b/Elements_of_discrete_mathematics/Chapter8.ipynb new file mode 100755 index 00000000..a92071c6 --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter8.ipynb @@ -0,0 +1,62 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:315aef45dcd0f156b4319ee68cddb70a9a8edfeb1c485c709f025d64bf2af90b"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "8 Discrete numeric functions and generating functions"
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 01:Page 368"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Suppose we deposit $100 in a savings account at an interest rate of 7 percent per year, compounded annually\"\n",
+ "principal=100\n",
+ "rate_of_interest=7\n",
+ "def amount(r): # r represents the number of years\n",
+ " a=principal*pow(1.07,r) # Since the formula for compound interest is 100*(1+(rate_of_interest/100)) and rate_of_interest here is 7\n",
+ " return a\n",
+ "print \"At the end of the first year, the total amount in the account is $\",amount(1) #Since we calculate the amount after 1 year, here r is 1\n",
+ "print \"At the end of the second year, the total amount in the account is $\",amount(2) #Since we calculate the amount after 2 years, here r is 2\n",
+ "print \"At the end of the third year, the total amount in the account is $\",round(amount(3),2) #Since we calculate the amount after 3 years, here r is 3\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Suppose we deposit $100 in a savings account at an interest rate of 7 percent per year, compounded annually\n",
+ "At the end of the first year, the total amount in the account is $ 107.0\n",
+ "At the end of the second year, the total amount in the account is $ 114.49\n",
+ "At the end of the third year, the total amount in the account is $ 122.5\n"
+ ]
+ }
+ ],
+ "prompt_number": 1
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file diff --git a/Elements_of_discrete_mathematics/Chapter9.ipynb b/Elements_of_discrete_mathematics/Chapter9.ipynb new file mode 100755 index 00000000..2c4b742e --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter9.ipynb @@ -0,0 +1,285 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:fe52e80aefa7cef4c97d80a1d8ac06d5a056bd7deebddce40f058e873b9c3a02"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "9 Recurrence relations and recursive algorithms"
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 15:Page 421"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"MERGE SORT\"\n",
+ "alist=[65,43,22,54,87,11,76,48,30,60,19,75,94,27,58,80]#List to be sorted\n",
+ "def mergesort(alist):\n",
+ " print \"Splitting\",alist\n",
+ " if len(alist)>1:\n",
+ " \n",
+ " mid=len(alist)/2\n",
+ " left_half=alist[:mid]\n",
+ " right_half=alist[mid:]#Spltting into halves\n",
+ " mergesort(left_half)\n",
+ " mergesort(right_half)#Recirsive split to obtain values\n",
+ " i=0\n",
+ " j=0\n",
+ " k=0#Varaibles for indexing\n",
+ " while i<len(left_half) and j<len(right_half):\n",
+ " if left_half[i]<right_half[j]:\n",
+ " alist[k]=left_half[i]#Puts the minimum value in the beginning\n",
+ " i=i+1\n",
+ " else:\n",
+ " alist[k]=right_half[j]\n",
+ " j=j+1\n",
+ " k=k+1\n",
+ " while i<len(left_half):\n",
+ " alist[k]=left_half[i]#Combine left sorted elements to the whole list\n",
+ " i=i+1\n",
+ " k=k+1\n",
+ " while j<len(right_half):\n",
+ " alist[k]=right_half[j]#Combine right sorted elements to the wholw list\n",
+ " j=j+1\n",
+ " k=k+1\n",
+ " print \"Merging\",alist\n",
+ " \n",
+ "mergesort(alist)\n",
+ "print(alist)\n",
+ "\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "MERGE SORT\n",
+ "Splitting [65, 43, 22, 54, 87, 11, 76, 48, 30, 60, 19, 75, 94, 27, 58, 80]\n",
+ "Splitting [65, 43, 22, 54, 87, 11, 76, 48]\n",
+ "Splitting [65, 43, 22, 54]\n",
+ "Splitting [65, 43]\n",
+ "Splitting [65]\n",
+ "Merging [65]\n",
+ "Splitting [43]\n",
+ "Merging [43]\n",
+ "Merging [43, 65]\n",
+ "Splitting [22, 54]\n",
+ "Splitting [22]\n",
+ "Merging [22]\n",
+ "Splitting [54]\n",
+ "Merging [54]\n",
+ "Merging [22, 54]\n",
+ "Merging [22, 43, 54, 65]\n",
+ "Splitting [87, 11, 76, 48]\n",
+ "Splitting [87, 11]\n",
+ "Splitting [87]\n",
+ "Merging [87]\n",
+ "Splitting [11]\n",
+ "Merging [11]\n",
+ "Merging [11, 87]\n",
+ "Splitting [76, 48]\n",
+ "Splitting [76]\n",
+ "Merging [76]\n",
+ "Splitting [48]\n",
+ "Merging [48]\n",
+ "Merging [48, 76]\n",
+ "Merging [11, 48, 76, 87]\n",
+ "Merging [11, 22, 43, 48, 54, 65, 76, 87]\n",
+ "Splitting [30, 60, 19, 75, 94, 27, 58, 80]\n",
+ "Splitting [30, 60, 19, 75]\n",
+ "Splitting [30, 60]\n",
+ "Splitting [30]\n",
+ "Merging [30]\n",
+ "Splitting [60]\n",
+ "Merging [60]\n",
+ "Merging [30, 60]\n",
+ "Splitting [19, 75]\n",
+ "Splitting [19]\n",
+ "Merging [19]\n",
+ "Splitting [75]\n",
+ "Merging [75]\n",
+ "Merging [19, 75]\n",
+ "Merging [19, 30, 60, 75]\n",
+ "Splitting [94, 27, 58, 80]\n",
+ "Splitting [94, 27]\n",
+ "Splitting [94]\n",
+ "Merging [94]\n",
+ "Splitting [27]\n",
+ "Merging [27]\n",
+ "Merging [27, 94]\n",
+ "Splitting [58, 80]\n",
+ "Splitting [58]\n",
+ "Merging [58]\n",
+ "Splitting [80]\n",
+ "Merging [80]\n",
+ "Merging [58, 80]\n",
+ "Merging [27, 58, 80, 94]\n",
+ "Merging [19, 27, 30, 58, 60, 75, 80, 94]\n",
+ "Merging [11, 19, 22, 27, 30, 43, 48, 54, 58, 60, 65, 75, 76, 80, 87, 94]\n",
+ "[11, 19, 22, 27, 30, 43, 48, 54, 58, 60, 65, 75, 76, 80, 87, 94]\n"
+ ]
+ }
+ ],
+ "prompt_number": 2
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 17:Page 424"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"BINARY SEARCH\"\n",
+ "array=[\"\" for i in range(100)]\n",
+ "temp=0#Variable checks if the element has been found. Initialised to zero, if it retains the same value till the end, then the element is not in the given list\n",
+ "n=input(\"Enter the number of elements\")\n",
+ "print \"Enter the elememts in sorted order\"\n",
+ "for i in range(0,n):\n",
+ " array[i]=input()#Input the numbers in ascending order\n",
+ "item=input(\"Enter the item to be searched\")\n",
+ "first=0#\n",
+ "last=n-1\n",
+ "while first<=last:\n",
+ " mid=(first+last)/2#Finds the middle element\n",
+ " if item==array[mid]:\n",
+ " print \"Search is successfully completed\"\n",
+ " temp=mid\n",
+ " print \"The item is in position\",temp+1\n",
+ " \n",
+ " if item<array[mid]:#Divides the array into half depending on the value to be searched\n",
+ " last=mid-1\n",
+ " else:\n",
+ " first=mid+1\n",
+ "if temp==0:\n",
+ " print \"Search is not successfully completed\"\n",
+ " \n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "BINARY SEARCH\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the number of elements7\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the elememts in sorted order\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "9\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "16\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "25\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "49\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "50\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "67\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "84\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the item to be searched67\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Search is successfully completed\n",
+ "The item is in position 6\n"
+ ]
+ }
+ ],
+ "prompt_number": 3
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file diff --git a/Elements_of_discrete_mathematics/screenshots/Chapter10.png b/Elements_of_discrete_mathematics/screenshots/Chapter10.png Binary files differnew file mode 100755 index 00000000..6ae7774c --- /dev/null +++ b/Elements_of_discrete_mathematics/screenshots/Chapter10.png diff --git a/Elements_of_discrete_mathematics/screenshots/Chapter2.png b/Elements_of_discrete_mathematics/screenshots/Chapter2.png Binary files differnew file mode 100755 index 00000000..0367a0b1 --- /dev/null +++ b/Elements_of_discrete_mathematics/screenshots/Chapter2.png diff --git a/Elements_of_discrete_mathematics/screenshots/Chapter5.png b/Elements_of_discrete_mathematics/screenshots/Chapter5.png Binary files differnew file mode 100755 index 00000000..e4543517 --- /dev/null +++ b/Elements_of_discrete_mathematics/screenshots/Chapter5.png |
