# 3 Relations and Functions¶

## Example 06:Page 118¶

In [2]:
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"
#Each element in A acts as a node
nodes=input("Enter the number of nodes")#This is the total number of elements in the given set A
w0=[[0 for i in range (nodes)]for j in range(nodes)]#Matrix elements are initialised to zero
#Gets the initial value for the matrix elements
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
for i in range(0,nodes):
for j in range(0,nodes):
print "Enter value for w",i,j
w0[i][j]=input()
#To print the given matrix
print "The given matrix W0=MR(Matrix relation on R) is"
for i in range(0,nodes):
for j in range(0,nodes):
print w0[i][j],
print "\n"
for k in range(0,nodes):#To find the transitive relation matrix using Warshall's algorithm
for i in range(0,nodes):
for j in range(0,nodes):
w0[i][j]=w0[i][j] or (w0[i][k] and w0[k][j])
#To print the transitive relation matrix
print "The required transitive relation matrix is"
for i in range(0,nodes):
for j in range(0,nodes):
print w0[i][j],
print "\n"

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
Enter the number of nodes4
Enter the elements of W0. (Enter only 0 or 1)
Enter value for w 0 0
0
Enter value for w 0 1
1
Enter value for w 0 2
0
Enter value for w 0 3
0
Enter value for w 1 0
1
Enter value for w 1 1
0
Enter value for w 1 2
1
Enter value for w 1 3
0
Enter value for w 2 0
0
Enter value for w 2 1
0
Enter value for w 2 2
0
Enter value for w 2 3
1
Enter value for w 3 0
1
Enter value for w 3 1
0
Enter value for w 3 2
0
Enter value for w 3 3
0
The given matrix W0=MR(Matrix relation on R) is
0 1 0 0

1 0 1 0

0 0 0 1

1 0 0 0

The required transitive relation matrix is
1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1



## Example 07:Page 119¶

In [3]:
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"
print "Given:R={(b,c),(b,e),(c,e),(d,a),(c,b),(e,c)}"
#Each element in A acts as a node
nodes=input("Enter the number of nodes")#This is the total number of elements in the given set A
w0=[[0 for i in range (nodes)]for j in range(nodes)]#Matrix elements are initialised to zero
#Gets the initial value for the matrix elements
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
for i in range(0,nodes):
for j in range(0,nodes):
print "Enter value for w",i,j
w0[i][j]=input()
#To print the given matrix
print "The given matrix W0=MR(Matrix relation on R) is"
for i in range(0,nodes):
for j in range(0,nodes):
print w0[i][j],
print "\n"
for k in range(0,nodes):#To find the transitive relation matrix using Warshall's algorithm
for i in range(0,nodes):
for j in range(0,nodes):
w0[i][j]=w0[i][j] or (w0[i][k] and w0[k][j])
#To print the transitive relation matrix
print "The required transitive relation matrix is"
for i in range(0,nodes):
for j in range(0,nodes):
print w0[i][j],
print "\n"

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
Given:R={(b,c),(b,e),(c,e),(d,a),(c,b),(e,c)}
Enter the number of nodes5
Enter the elements of W0. (Enter only 0 or 1)
Enter value for w 0 0
0
Enter value for w 0 1
0
Enter value for w 0 2
0
Enter value for w 0 3
0
Enter value for w 0 4
0
Enter value for w 1 0
0
Enter value for w 1 1
0
Enter value for w 1 2
1
Enter value for w 1 3
0
Enter value for w 1 4
1
Enter value for w 2 0
0
Enter value for w 2 1
0
Enter value for w 2 2
0
Enter value for w 2 3
0
Enter value for w 2 4
1
Enter value for w 3 0
1
Enter value for w 3 1
0
Enter value for w 3 2
0
Enter value for w 3 3
0
Enter value for w 3 4
0
Enter value for w 4 0
0
Enter value for w 4 1
1
Enter value for w 4 2
1
Enter value for w 4 3
0
Enter value for w 4 4
0
The given matrix W0=MR(Matrix relation on R) is
0 0 0 0 0

0 0 1 0 1

0 0 0 0 1

1 0 0 0 0

0 1 1 0 0

The required transitive relation matrix is
0 0 0 0 0

0 1 1 0 1

0 1 1 0 1

1 0 0 0 0

0 1 1 0 1



## Example 41:Page 154¶

In [5]:
#Given function definition is as follows
print "RECURSIVE FUNCTIONS"
def f(x):
if x==0:
return 1
else:
return 3*f(x-1)+1
print "f(1)=",f(1)
print "f(2)=",f(2)
print "f(3)=",f(3)

RECURSIVE FUNCTIONS
f(1)= 4
f(2)= 13
f(3)= 40


## Example 43:Page 156¶

In [6]:
print "A recursive function to calculate the GCD of two numbers"
def GCD(x,y):
if x>y:
x=x-y
return GCD(x,y)
elif x<y:
y=y-x
return GCD(x,y)
else:
print "The GCD of the two numbers is",x

A recursive function to calculate the GCD of two numbers


## Example 44:Page 157¶

In [7]:
print "EXAMPLE OF TREE RECURSION"
print "The first six fibonacci numbers are"
def fib(n):
if n==0:
return 0
elif n==1:
return 1
else:
print "fib(",n-1,")+fib(",n-2,")=",
return fib(n-1)+fib(n-2)
print "fib(0)=",fib(0),
print "\nfib(1)=",fib(1),
print "\nfib(2)=",fib(2),
print "\nfib(3)=",fib(3),
print "\nfib(4)=",fib(4),
print "\nfib(5)=",fib(5),

EXAMPLE OF TREE RECURSION
The first six fibonacci numbers are
fib(0)= 0
fib(1)= 1
fib(2)= fib( 1 )+fib( 0 )= 1
fib(3)= fib( 2 )+fib( 1 )= fib( 1 )+fib( 0 )= 2
fib(4)= fib( 3 )+fib( 2 )= fib( 2 )+fib( 1 )= fib( 1 )+fib( 0 )= fib( 1 )+fib( 0 )= 3
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


## Example 45:Page 159¶

In [8]:
print "HASH FUNCTIONS"
import math
print "Employee IDs are 6713,4409,5835"
print "L consists of 100 two digit address:00,01,.....,99 "
m=97#Prime number close to 99
def H(ID):
print ID,"mod",m,"=",
return ID%m
print "Division method"
print "H(6713)=",H(6713)
print "H(4409)=",H(4409)
print "H(5835)=",H(5835)
print "Midsquare method"

def H1(ID):
key=math.pow(ID,2)#Square the given key value
key1=int(key)#Convert it into integer to eliminate decimal point
number=str(key1)#Integer is converted to string for indexing purpose
length=len(number)#Finding the length of the string
number2=number[3:length-3]#Slicing the string to eliminate 3 digits from both ends
return number2

print "k=6713","square(k)=",pow(6713,2),"\tH(6713)=",H1(6713)
print "k=4409","square(k)=",pow(4409,2),"\tH(4409)=",H1(4409)
print "k=5835","square(k)=",pow(5835,2),"\tH(5835)=",H1(5835)
print "Folding method"
#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
def H2(ID):
ID1=str(ID)#Convert it into string in order to slice it
key1=ID1[0:2]#Split the string into two halves. First part in key1
key2=ID1[2:]#Second half is stored in key2
print key1,"+",key2,"=",
key=int(key1)+int(key2)#Convert these into int in order to perform addition
key3=str(key)#To eliminate the carry,convert it back to string
length=len(key3)#Since here each part contains only 2 digits, a carry means the presence of a third digit.
if length==3:
res=key3[1:]#If length is 3 , eliminate the leftmost digit
return res
else:
return key#If it is less than 3, print it as such
print "6713=",H2(6713)
print "4409=",H2(4409)
print "5835=",H2(5835)

HASH FUNCTIONS
Employee IDs are 6713,4409,5835
L consists of 100 two digit address:00,01,.....,99
Division method
H(6713)= 6713 mod 97 = 20
H(4409)= 4409 mod 97 = 44
H(5835)= 5835 mod 97 = 15
Midsquare method
k=6713 square(k)= 45064369 	H(6713)= 64
k=4409 square(k)= 19439281 	H(4409)= 39
k=5835 square(k)= 34047225 	H(5835)= 47
Folding method
6713= 67 + 13 = 80
4409= 44 + 09 = 53
5835= 58 + 35 = 93


## Example 46:Page 161¶

In [9]:
print "Linear probing to overcome collision in the numbers 89,18,49,58,69"
memory=["" for i in range (0,10)]#An array indicating the memory space. Initially all the locations are empty

def h(n):
temp=n#Get a copy as we might change the value in the original variable
count=0#Initial collision count is zero
flag=0#Flag=1 indicates that the key has been placed in the memory. So initially it is zero
while flag==0:
num=n%10#10 is the number of buckets or partitions
if memory[num]=="":#Checks if the location is empty
memory[num]=temp#Inserts value if nothing is already present
flag=1#Indicates that the key is placed in memory
else:
count=count+1#If the location is not empty, the collision count is increased by one
def f(i):#Collosion resolution function
return i
n=num+f(count)#Facilitates linear probing by increasing the count by 1
#Hash the values
h(89)
h(18)
h(49)
h(58)
h(69)
print "MEMORY  |\t\tVALUE"
print "------------------------------------"
for i in range(0,10):#Print the hashed memory area
print i,"\t|\t",memory[i]
print "---------------------------------"

Linear probing to overcome collision in the numbers 89,18,49,58,69
MEMORY  |		VALUE
------------------------------------
0 	|	49
---------------------------------
1 	|	58
---------------------------------
2 	|	69
---------------------------------
3 	|
---------------------------------
4 	|
---------------------------------
5 	|
---------------------------------
6 	|
---------------------------------
7 	|
---------------------------------
8 	|	18
---------------------------------
9 	|	89
---------------------------------


## Example 47:Page 163¶

In [10]:
print "Quadratic probing in the numbers 89,18,49,58,69"
memory=["" for i in range (0,10)]#An array indicating the memory space. Initially all the locations are empty

def h(n):
temp=n#Get a copy as we might change the value in the original variable
count=0#Initial collision count is zero
flag=0#Flag=1 indicates that the key has been placed in the memory. So initially it is zero
while flag==0:
num=n%10#10 is the number of buckets or partitions
if memory[num]=="":#Checks if the location is empty
memory[num]=temp#Inserts value if nothing is already present
flag=1#Indicates that the key is placed in memory
else:
count=count+1#If the location is not empty, the collision count is increased by one
def f(i):#Collosion resolution function
return i*i
n=num+f(count)#Facilitates quadratic probing by squaring the count
#Hash the values
h(89)
h(18)
h(49)
h(58)
h(69)
print "MEMORY  |\t VALUES"
print "-------------------------------------"
for i in range(0,10):#Print the hashed memory area
print i,"\t|\t",memory[i]
print "-------------------------------------"

Quadratic probing in the numbers 89,18,49,58,69
MEMORY  |	 VALUES
-------------------------------------
0 	|	49
-------------------------------------
1 	|
-------------------------------------
2 	|
-------------------------------------
3 	|	58
-------------------------------------
4 	|	69
-------------------------------------
5 	|
-------------------------------------
6 	|
-------------------------------------
7 	|
-------------------------------------
8 	|	18
-------------------------------------
9 	|	89
-------------------------------------


## Example 48:Page 164¶

In [11]:
print "Double hashing in the numbers 89,18,49,58,69"
memory=["" for i in range (0,10)]#An array indicating the memory space. Initially all the locations are empty
r=7#Assume
def h(n):
temp=n#Get a copy as we might change the value in the original variable
count=0#Initial collision count is zero
flag=0#Flag=1 indicates that the key has been placed in the memory. So initially it is zero
while flag==0:
num=n%10#10 is the number of buckets or partitions
if memory[num]=="":#Checks if the location is empty
memory[num]=temp#Inserts value if nothing is already present
flag=1#Indicates that the key is placed in memory
else:
count=count+1#If the location is not empty, the collision count is increased by one
def h1(t):
return r-(t%r)#Assume

def f(i):#Collosion resolution function
return i*h1(temp)
n=num+f(count)#Facilitates probing
#Hash the values
h(89)
h(18)
h(49)
h(58)
h(69)
print "MEMORY  |\tVALUES"
print "-------------------------------------"
for i in range(0,10):#Print the hashed memory area
print i,"\t|\t",memory[i]
print "----------------------------------------"

Double hashing in the numbers 89,18,49,58,69
MEMORY  |	VALUES
-------------------------------------
0 	|	69
----------------------------------------
1 	|
----------------------------------------
2 	|
----------------------------------------
3 	|	58
----------------------------------------
4 	|
----------------------------------------
5 	|
----------------------------------------
6 	|	49
----------------------------------------
7 	|
----------------------------------------
8 	|	18
----------------------------------------
9 	|	89
----------------------------------------


## Example 49:Page 166¶

In [12]:
import math
magazine=30#Magazines are considered as pigeonholes
total_pages=61324#Pages are considered as pigeons. Assign each page to the magazine in which it appears
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

If 30 magazines contain a total of 61,324 pages, then one magazine must contain at least 2045 pages


## Example 50:Page 166¶

In [13]:
a=0
b=0
s=[[0 for i in range(13)]for j in range(13)]#Initialise the matrix
#If the summation turns out to be 13, then put them in a 2D array
for i in range(1,13):
for j in range(i+1,13):

if i+j==13:

s[a][b]=i
s[a][b+1]=j
a=a+1
#Print the 2D array containing the possible combinations
for i in range(0,a):
print "s",i+1,"=(",
for j in range(0,2):
print s[i][j],",",
print "),",
print "\n"

print "These are the combination of numbers between 1 and 12 those on summation will yield 13 as a result."
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 "
#According to pigeonhole principle

s 1 =( 1 , 12 , ),

s 2 =( 2 , 11 , ),

s 3 =( 3 , 10 , ),

s 4 =( 4 , 9 , ),

s 5 =( 5 , 8 , ),

s 6 =( 6 , 7 , ),

These are the combination of numbers between 1 and 12 those on summation will yield 13 as a result.
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


## Example 52:Page 166¶

In [14]:
import math
total_num=10#Total number of people volunteering
committee_num=3#Number of people to be there in the committee
print "Ten people come forward to volunteer for a committee of three"
print "Every possible committee of three that can be formed from these ten names is written on a slip of paper"
slips=(math.factorial(total_num)/(math.factorial(total_num-committee_num)*math.factorial(committee_num)))#Slips are compared to pigeons.By formula for combinations
hats=10#Hats are compared to pigeonholes
print "Total number of combinations to choose 3 out of ten is",slips
print "These possible ",slips, "slips, one slip for each possible committee and the slips are put in ",hats,"hats"
print "Therefore, One hat must contain at least",int((math.floor((slips-1)/hats)+1)),"or more slips of paper"

Ten people come forward to volunteer for a committee of three
Every possible committee of three that can be formed from these ten names is written on a slip of paper
Total number of combinations to choose 3 out of ten is 120
These possible  120 slips, one slip for each possible committee and the slips are put in  10 hats
Therefore, One hat must contain at least 12 or more slips of paper


## Example 53:Page 166¶

In [15]:
import math
types=12#Types of chocolates
choice=5#Types to choose from
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 "
c=math.factorial(types)/(math.factorial(choice)*math.factorial(types-choice))#By the formula for finding combinations
print "The customer can choose chocolates in ",c,"ways"
amount=175#In paise
print "we have",int((math.floor((c-1)/amount)+1)),"choices having the same cost"#By extended pigeonhole principle
print "Therefore, there must be at least two different ways to choose, so that the cost will be the same for both choices"

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 customer can choose chocolates in  792 ways
we have 5 choices having the same cost
Therefore, there must be at least two different ways to choose, so that the cost will be the same for both choices


## Example 54:Page 167¶

In [16]:
import math
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"
types=12#Total types of chocolates
choice=5#Customer can choose 1 from 5 types
c=math.factorial(types)/(math.factorial(choice)*math.factorial(types-choice))#By formula of finding combinations
print "The customer can choose chocolates in ",c,"ways"
amount=175#In paise
ans=int((math.floor((c-1)/amount)+1))#By extended pigeonhole principle
print "we have",ans,"choices having the same cost"
choice=(math.factorial(types+choice-1)/(math.factorial(ans)*math.factorial(types+choice-1-ans)))#Considered as pigeonhole
print "If repetitions are allowed, then we have 5 groups and there are C(12+5-1,5)=C(16,5)=",choice,"choices"
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"
#By extended pigeonhole principle

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
The customer can choose chocolates in  792 ways
we have 5 choices having the same cost
If repetitions are allowed, then we have 5 groups and there are C(12+5-1,5)=C(16,5)= 4368 choices
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


## Example 55:Page 167¶

In [17]:
import math
total=15#Total number of choices
choice=6#Number of choices to select
c=math.factorial(total)/(math.factorial(choice)*math.factorial(total-choice))
print "6 numbers out of 1 to 15 can be chosen in",c,"ways"#These are considered as pigeons
sum1=0#Initial sum of first 6 numbers is set to zero
sum2=0#Initial sum of last 6 numbers is set to zero
for i in range(1,7):
sum1=sum1+i#Calulates the sum of first six numbers
for i in range(10,16):
sum2=sum2+i#Calulates the sum of first six numbers
num_of_sums=(sum2-sum1+1)
print "Number of sums that can be generated is",num_of_sums#Considered as pigeon holes
print "There are",int((math.floor((c-1)/num_of_sums)+1)),"ways"#By extended pigeon hole principle
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"

6 numbers out of 1 to 15 can be chosen in 5005 ways
Number of sums that can be generated is 55
There are 91 ways
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


## Example 56:Page 167¶

In [18]:
import math
print "ABCD is the required square. Join AD and BC.Now we get 4 triangles,namely ACD,BCD,ABC,ABD."
print "If five points are selected in a square, two of them must belong to the same triangle."#According to pigeonhole principle
distance=math.sqrt(math.pow(1,2)+math.pow(1,2))
print "The largest distance in a triangle is",distance,"So the points must be no more than ",distance,"inches apart"

ABCD is the required square. Join AD and BC.Now we get 4 triangles,namely ACD,BCD,ABC,ABD.
If five points are selected in a square, two of them must belong to the same triangle.
The largest distance in a triangle is 1.41421356237 So the points must be no more than  1.41421356237 inches apart


## Example 57:Page 167¶

In [19]:
import math
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
sum=51#Actual sum of entries in A
rows=8#8*8 matrix
columns=8#8*8 matrix
row_ones=int(math.floor((sum-1)/rows)+1)#Minimum number of ones in a row by extended pigeonole principle
print "One row must have at least",row_ones,"ones"
column_ones=int(math.floor((sum-1)/columns)+1)#Minimum number of ones in a column by extended pigeonhole principle
print "One column must have at least",column_ones,"ones"
print "The sum of elements of row and column is",row_ones+column_ones
print "So, the sum of entries will add up to be more than 13"

The sum of entries in A cannot be more than 64
One row must have at least 7 ones
One column must have at least 7 ones
The sum of elements of row and column is 14
So, the sum of entries will add up to be more than 13