DSL 11

Data Structure Lab:

Practical B11: 

a) Write a Python program to store roll numbers of student in array who attended training program in random order. Write function for searching whether particular student attended training program or not, using Linear search and Sentinel search. 

b) Write a Python program to store roll numbers of student array who attended training program in sorted order. Write function for searching whether particular student attended training program or not, using Binary search and Fibonacci search

   
 #author:sppucseguru  
   
 A=[]  
 while 'true' :  
  roll= int(input ("Enter roll no. of Students who attended training program "))  
  A.append(roll)  
  res=input ("Do you want to continue ? y or n ")  
  if res=='n':  
   break  
     
 print (A)  
 n=len(A)  
   
   
 #linear search  
 def LSearch():  
  while True:  
   flag=0  
   roll= int(input ("Enter roll no. of Students which you want to check "))  
   for i in range(n):  
    if A[i]==roll:  
     flag=1  
     break  
   if flag==1:  
     print ("Student is present for training program")  
   else:  
     print ("Student is absent for training program")  
   res=input ("Do you want to continue ? y or n ")  
   if res=='y':  
       LSearch()  
   else:  
       print("Search Completed")  
       break  
 
 #Sentinel Search  
 def SeSearch():  
   while True:  
      roll= int(input ("Enter roll no. of Students which you want to check "))  
      A.append(roll)  
      for i in range(n+1):  
        index=i  
        if A[i]==roll:  
          break  
      if index<n:  
        print ("Student is present for training program")  
      else:  
        print ("Student is absent for training program")  
      res=input ("Do you want to continue ? y or n ")  
      if res=='y':  
       SeSearch()  
      else:  
       print("Search Completed")  
       break           
       
 #*Remember for binary and fibonacci search we required elements in sorted form*  
       
 #Binary Search     
 low=0  
 high=n-1     
 def BiSearch():  
   low=0  
   high=n-1   
   roll= int(input ("Enter roll no. of Students which you want to check "))  
   flag=0  
   while (low<=high) :  
     mid=(high+low)//2  
     if roll==A[mid]:  
       flag=1  
       print ("Student is present for training program")  
       break  
     elif roll<A[mid]:  
         high=mid-1  
     else:  
         low=mid+1  
   if flag==0:  
     print ("Student is absent for training program")  
   res=input ("Do you want to continue ? y or n ")  
   if res=='y':  
     BiSearch()  
   else:  
     print("Search Completed")     
    
 # Fibonacci Search  
 def FibSearch():  
   roll= int(input ("Enter roll no. of Students which you want to check "))  
   fib1=fib2=1  
   fib=2  
   while fib<n:  
     fib2=fib1  
     fib1=fib  
     fib=fib1+fib2  
   i=0  
   offset=-1  
   flag=0  
   while fib>1:  
     i=min(offset+fib2,n-1)  
       
     if A[i]<roll:  
       fib=fib1  
       fib1=fib2  
       fib2=fib-fib1  
       offset=i  
       
     elif A[i]>roll:  
       fib=fib2  
       fib1=fib1-fib2  
       fib2=fib-fib1  
         
     else:  
       flag=1  
       print("Student is present for training program")  
       break  
         
   if flag==0:  
     print ("Student is absent for training program")  
   res=input ("Do you want to continue ? y or n ")  
   if res=='y':  
     FibSearch()  
   else:  
     print("Search Completed")   
   
 while True:  
   res=input("""Enter algorithm you want to use  
          a. Linear Search  
          b. Sentinel search  
          c. Binary Search  
          d. Fibonacci Search  
          e. exit\n""")     
            
   if(res=='a'):  
     LSearch()  
     break  
   elif(res=='b'):  
     SeSearch()  
     break  
   elif(res=='c'):  
     A=sorted(A)  
     BiSearch()  
     break  
   elif(res=='d'):  
     A=sorted(A)  
     FibSearch()   
     break  
   elif(res=='e'):  
     break  
   else:  
     print("Wrong Respond")