Design and analysis algorithm Theory of Automata.pptx

Good

1. Design and Analysis Algorithm

2. The Recurrence and its example and problem solutions * Presented by BSCS-E1 (girls) (Roll no 4,5,7,9,15,19, 20) Designed by Sara Yousaf

3. The Recursion For example: Fact(4)=24 Solution: 4*fact(3) 4*3*fact(2) 4*3*2*fact(1) 4*3*2*1=24 In recursion one function called itself, the number of parameters never changes only the parameter value changes The process in which the function calls itself is called recursion The corresponding function is called the recursive function . THE RECURSION

4. The Recursion Advantages: Recursion adds clarity to the code. It can reduce time complexity Reduce time to debug It is also used for analyzing and optimizing the algorithm Disadvantages: Uses more memory Recursion becomes slow A recursive program has a greater space requirement than an iterative program as each function in the program remains in the stack until the base case is reached

5. THE RECURRENCE Recurrence is an equation or an in-equality that describes the function in terms of its smaller inputs Recurrences arise when an algorithm contain recursive calls to itself. The simplest form is as follows: T(n)= T(n-1)+n

6. The Recurrence Binary Search: T(n)=T(n/2)+1 Input size T(n)=T(n/2)+1 Reducing of input size Signifies a function 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 2 3 5 7 9 10 11 12 lo hi mid Mid =[( lo+hi )/2] Exp; mid pt= 4 approx

7. The Recurrence Binary Search: Binary Search (A, lo, hi, x) if(lo>hi) return false mid ( lo+hi )/2 If x=A[mid] return True If(x<A[mid]) Binary-Search(A,lo,mid-1,x) If(x>A[mid]) Binary-Search(A,mid+1,hi,x) Example: A[8]={1,2,3,4,5,7,9,11} midpoint -lo=1 ,hi=8,x=7 mid=4, lo=5 , hi=8 mid=6, A[mid]=x Found! midpoint 1 2 3 4 5 6 7 8 1 2 3 4 5 7 9 11 1 2 3 4 5 6 7 8 1 2 3 4 5 7 9 11

8. THE RECURRENCE Exp-1: Simple code void fun(int n) { if(n>0){ for( i =0;i< n;i ++) { print(n);{ fun(n-1)} } T(n)=T(n-1)+2n+2 T(n)=T(n-1)+n n 1 n+1 n n-1 Exp-2: int binarySearch ( intarr [],int n , int key) { int low=0; int high=n-1; while(low<=high){ int mid=( low+high )/2; if( arr [mid]==key) { return mid; } else if ( arr [mid]<key) { low=mid+1; } else { high= mid-1; } } return -1; } //O(1) //O(1) //O(1) //O(log n) //O(1) //O(1) //O(1) //O(1) //O(1) //O(1) T(n)=O(1)+)O(1)+O( logn )*(O(1)+O(1)+O(1))+O(1) T(n)=O(1)+O(1)+O( logn )+O(1)+O(1) T(n)=O( logn )