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