dedications

A post as a dedication to all the teachers who teach programming and to my teachers who have thought me to program. PSM sir, Mohan Sir, KVB, Lalitha Kumari , Thaygraj sir,  Julie Zelenski, Neelesh , David Evans and my friends. I thank them for teaching me programming in class , through the videos or at home.

Search a sorted array for first occurance of K

Find the first occurrence of a given element in the sorted list.

Search + sorted  the way  to go ahead is with binary search. Binary search my default doesn't guarantee to return the first occurrence of the element in case of duplicates. So what to do? search for the element using binary search, check if the element at index-1 is equal to search element if yes rerun binary search from 0 to index-1 else we have our answer.

#------------------------------------------------------------------------------- # Name: fristKInSortedList # Purpose: Find the first occurace of an element in the sorted list # # Created: 10/09/2012 #------------------------------------------------------------------------------- def main(): sortedlist = [1,2,3,4,5,5,5,5,5,5,6,6,6,7,8,9,9,9,11,12,12,12,12,12,12,14,14,14,15,15,15,16] element=9 print(fristKInSortedList(sortedlist,element)) def fristKInSortedList(inlist,element): flag = True index = len(inlist) if inlist[0] == element: return 0 while flag or inlist[index-1] == element:#second part of or never executes the first time flag = False index = binarySearchRecursive(inlist,element,0,index-1) if index == -1: return index return index def binarySearchRecursive(slist,element,begin,end): if len(slist) <= 0: print("invalid list! Empty List!") return -1 if begin > end: return -1 mid=int((begin+end)/2) if slist[mid] > element: return binarySearchRecursive(slist,element,begin,mid-1) elif slist[mid] < element: return binarySearchRecursive(slist,element,mid+1,end) else: return mid if __name__ == '__main__': main()

Matrices Multiplication algorithm implementation in python

Matrices Multiplication implementation in python.

I always ignored questions on matrices i rather ran away from those never dared to accept them and code them, finally made up my mind. Next one in line is "inplace" transform of matrix.  Ns ran away ow that i have started programming matrices i feel better to have done something which i always ran away from.

#------------------------------------------------------------------------------- # Name: matrixmultiplication # Purpose: # # Created: 08/09/2012 #------------------------------------------------------------------------------- def main(): mat1=[[1,2,3,4],[3,3,3,4],[5,6,7,8],[5,6,7,8]] mat2=[[1,2,3,4],[1,2,3,4],[5,6,7,8],[5,6,7,8]] mat3=[[9,2],[6,2],[9,7],[5,6]] c = matmulti(mat1,mat2) print(c) def zeros(*shape): if len(shape) == 0: return 0 a = shape[0] b = shape[1:] return [zeros(*b) for i in range(a)] def matmulti(a,b): x=len(a) y=len(a[0]) m=len(b) n=len(b[0]) #print(x,y,m,n) if y != m: print("Canot multipy the matrices as the column count of multiplier is not equal to the row count of the multiplicand") return [] i,j,k,c=0,0,0,zeros(x,n) while i < x: j=0 while j < n: k=0 sum=0 while k < y: sum=sum+(a[i][k]*b[k][j]) k=k+1 c[i][j]=sum j=j+1 i=i+1 return c if __name__ == '__main__': main()

Square root of a number upto accurate 6 decimal points

Implement a fast integer square root function that takes in a unsigned integer and returns another unsigned integer that is the square root of the input correct up to 6 decimal places.

Solution:
Classic application of Binary search Algorithm to solve the square root problem. A question asked in FB interview. Coded in python one of my fav programming language cant believe i ditched C++ :(. I'm still novice in python but would love to code more and more in python.

I need a better solution to stop at after 6 places after the decimal point, one other obvious solution is to run the while loop six times, but i need a mathematical rule which controls the loop.

#------------------------------------------------------------------------------- # Name: SquareRoot.py # Purpose: Implement a fast integer square root function that # takes in a unsigned integer and returns another unsigned integer that is # the square root of the input correct upto 6 decimal places. # # Created: 09/09/2012 #------------------------------------------------------------------------------- def main(): number=334567 sqroot=findsqroot(number) print(sqroot) def findsqroot(number): i=0 for i in range(number+1):# for 1 and 2 special cases input we need number+1 product=i*i if product > number: break; elif product == number: return i print(i) rootbase=i-1 begin,end=rootbase,i mid=(begin+end)/2 product=mid*mid while ((mid-rootbase)*1000000%10) == 0: if product > number: end=mid elif product < number: begin=mid else: return mid mid=(begin+end)/2 product=mid*mid return mid if __name__ == '__main__': main()