The Complete Codes

Recurrences And Their Solution Methods Recursion Tree Just Simplification of Iteration method: Consider The Recurrences Second Example Example Three Master Method Cookbook solution for some recurrences of the form T(n) = a . T(n/b) + f(n) where a>=1, b>1, f(n) asymptotically positive Describe its cases 

Recurrences Recursive algorithms are described by using recurrence relations. A recurrence is an inequality that describes a problem in terms of itself. For Example: Recursive algorithm for finding factorial   T(n)=1     when n =1 T(n)=T(n-1) + O(1)    when  n>1 Recursive algorithm for finding Nth Fibonacci number T(1)=1     when n=1 T(2)=1     when n=2 T(n)=T(n-1) + T(n-2) +O(1)     when n>2 Recursive algorithm for binary search T(1)=1     when n=1 T(n)=T(n/2) + O(1)    when n>1 Techniques for Solving Recurrences We’ll use four techniques: Iteration method Recursion Tree Substitution Master Method   – for divide & conquer Characteristic Equation   – for linear Iteration method Expand the relation so that summation independent on n is obtained. Bound the summation e.g.    T(n)= 2T(n/2) +1  when n>1 T(n)= 1    when n=1 T(n) = 2T(n/2) +1           = 2 { 2T(n/4) + 1} +1           = 4T(n/4) + 2 + 1           =

C Program For Bubble Sort by Generating Random Numbers and Using time.h Function #include <stdio.h> #include <time.h> #include <stdlib.h> void bubble_sort ( int [], int ); int main () {     int list [ 100 ], n , i ;     time_t t ;     printf ( "Enter the max number \n " );     scanf ( " %d " , & n );     srand (( unsigned ) time (& t ));     for ( i = 0 ; i < n ; i ++)     {         list [ i ] = rand () % 100 ;     }     for ( i = 0 ; i < n ; i ++)     {         printf ( " %d \t " , list [ i ]);     }     bubble_sort ( list , n );     printf ( " \n\n Time taken to complete the bubblesort %u \n " , clock () / CLOCKS_PER_SEC);     printf ( " \n The sorted list is:" );     for ( i = 0 ; i < n ; i ++)         printf ( " %d \t " , list [ i ]);     return 0 ; } void bubble_sort ( int list [], int n ) {     int temp , i , j ;     for ( i = 0 ; i < n ; i ++)     {    

Bubble Sort Bubble sort is a very simple sorting technique. However, this sorting algorithm is not efficient in comparison to other sorting algorithms. The basic idea underlying the bubble sort is to pass through the file sequentially several times. Each pass consists of comparing each element in the file with its successor (x[i] with x[i+1]) and interchanging the two elements if they are not in proper order. Example: Consider the following file, 25          57          48          37          12          92          86          33 In first pass, following comparisons are made: x[o] with x[1] (25 with 57) No interchange x[1] with x[2] (57 with 48) Interchange x[2] with x[3] (57 with 37) Interchange x[3] with x[4] (57 with 12) Interchange x[4] with x[5] (57 with 92) No interchange x[5] with x[6] (92 with 86) Interchange x[6] with x[7] (92 with 33) Interchange Thus, after the first pass, the file is on the order: 25          48          37          

Insertion Sort An insertion sort is one that sorts a set of values by inserting values into an existing sorted file. Suppose that Iist[] is a list of n elements in memory. The insertion sort technique scans the list Iist[] from Iist[1] to list[n-1], inserting each element list[ k] into its proper position in the previously sorted sublist list[o], list[1], ..., list[n-1]. Illustration: Let list[] be an array of 7 elements: 25, 15, 30, 9, 99, 20, 26. Initial scenario, Step 1: list[1] Step 2:   list[2]>list[1] , so position of elements remain same. Step 3:   list[3] is less than list[2.],list [1] and list[o], thus list[3] is inserted at list[o] position and others are shifted by one position. Step 4:  list[4]>list[3] , so position of elements remain same. Step 5:   list[5] is less than list[4], list[3], and list[2], so list[5] is inserted at the position of list[2] and others are shifted by one position. Step 6:   list

Merge Sort Merging is the process of combining two or more sorted files into a third sorted file. Procedure: In merge sort, we divide the file into n subfiles of size 1 and then merge adjacent pair of files. We then have n/2 files of size 2. We repeat this process until there is only one file remaining of size n. Efficiency of Merge Sort Let us assume that the file size n is a power of 2, say n=2 m . Thus m=log 2 n. It is therefore obvious that there are no more than m or log 2 n passes in merge sort (since each pass divides the file into two parts), with each pass involving at most n comparisons. Thus, total number of comparisons in merge sort is at most = n*m = n*log 2 n. Hence the time complexity of merge sort = O (n Iog n). Average case complexity = Worst case complexity = Best case complexity = O(n log n). C Program For Merge Sort #include <stdio.h> void mergesort ( int a [], int i , int j ); void merge ( int a [], int i1 , int j1 , int

Selection Sort A selection sort is a sorting techniqlue in which successive elements are selected in order and paced into their proper sorted positions. By starting from the first element and using a nest of for loops, a pass through the array is made to locate the minimum value. Once this is found, it 1s placed in the first position of the array (position 0). Then the remaining elements is made to find the next smallest element, which is placed in the second position (position 1), and so on. Once the next to last element is compared with the last element, all the elements have been sorted into ascending order. The algorithm works as follows: Find the minimum value in the list. Swap it with the value in the first position. Repeat the above steps for the remainder of the list (starting at the second position and advancing each time). Algorithm for Selection Sort This algorithm sorts the array list with n elements Initialization, Set loc=o