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"
```

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"
```

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)
```

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
```

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),
```

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)
```

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 "---------------------------------"
```

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 "-------------------------------------"
```

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 "----------------------------------------"
```

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
```

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
```

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"
```

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"
```

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
```

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"
```

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"
```

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"
```