Multiple recursive functions
- Write a recursive method intmultiply(int a, int b) to multiply two positive integers together without using the * operator. To receive full credit, you algorithm must run in O(log a) time. (In other words, you may not just add a to itself b times.) . Show a proof for the time complexity. Submit complete code.
2. Write a recursive method intpow(int a, int b) to construct a recursive power function (i.e. pow(int a, int b) = ab). Show what is the time complexity of your problem ? Submit complete code.
3. Given the recurrence T(n) = 2T(n/2) + n , get a O estimate for T(n) using the recursion tree or recurrence method.
4. [15 Points] Stooge sort : Analyze the running time and correctness of the following recursive sorting algorithm:
A. If the leftmost item is larger than the rightmost item, swap them.
B. If there are 2 or more items in the current subarray,
(i) sort the initial two-thirds of the array recursively,
(ii) sort the final two-thirds of the array,
(iii) sort the initial two-thirds of the array again.
An example take a list {1,2,3,4,5,6} here first 2/3 rd is {1,2,3,4} and final 2/3 rd is {3,4,5,6}.
Provide the recursion equation for the Stooge sort. Submit sample code.
Analyze the recursion in terms of time complexity. Show the recursion formula and then solve it.
5. Find the time complexity for the following piece of code. Show your workout. :
t = 1 ;
for (int i=0 ; i< n ; i++) {
t = t++ ;
}
while ( t > 1 ) {
t = t / 2 ;
}
6. Show work out for the following list [7 6 8 2 4 3] [30]
i. Insertion sort [10]
ii. Merge sort [10]
iii. Quick sort [10]
Hint. Follow the pseudo codes or programs uploaded.
You must indicate the trace of the execution as follows.
(5 2) 8 4 6 3 9 –> compare 5 and 2, swap
5 (2 8) 4 6 3 9 –> compare 2 and 8, no swap
5 2 (8 4) 6 3 9 –> compare 8 and 4, swap
5 2 4 (8 6) 3 9 –> compare 8 and 6, swap
5 2 4 6 (8 3) 9 –> compare 8 and 3, swap
7. Given a two arrays sort them with any methods. Find the median of the two sorted arrays. Find the time complexity of your problem. Submit code.
Solution
importjava.util.Scanner;
public class assignment
{
public static void main(String args[])
{
inta,b;
Scanner sc=new Scanner(System.in);
System.out.println(“This is the driver program:”);
System.out.println(“\nQuestion 1 : Multiply a and b without using * operator”);
System.out.print(“Enter a :”);
a = sc.nextInt();
System.out.print(“Enter b :”);
b = sc.nextInt();
System.out.println(a + “*” + b + ” = ” + multiply(a,b));
System.out.println(“\nQuestion 2 : Find a power b”);
System.out.print(“Enter a :”);
a = sc.nextInt();
System.out.print(“Enter b :”);
b = sc.nextInt();
System.out.println(a + ” power ” + b + ” = ” + pow(a,b));
System.out.println(“\nQuestion 4 : Stooge sort”);
int n;
System.out.print(“Enter number of elements to be sorted :”);
n = sc.nextInt();
System.out.print(“Enter elements of the array :”);
int[] A = new int[n];
for(int i=0;i<n;i++)
{
A[i] = sc.nextInt();
}
System.out.println(” Sorted Array :”);
stoogesort(A,0,n-1);
for(int i=0;i<n;i++)
{
System.out.print(A[i]+” “);
}
Question7();
sc.close();
}
staticint multiply(inta,int b)
{
if(a == 0 || b == 0) return 0;
int temp = multiply(a/2,b);
if(a%2 == 0)
{
if(a >= 0) return temp + temp;
else return(-temp – temp);
}
else
{
if(a >= 0) return temp + temp + b;
else return( -temp – temp – b);
}
}
staticintpow(inta,int b)
{
if(b == 0) return 1;
int temp;
temp = pow(a,b/2);
if (b%2 == 0)
return temp*temp;
else
{
if(b > 0)
return a*temp*temp;
else
return (temp*temp)/a;
}
}
static void stoogesort(intarr[], int l, int h)
{
if (l >= h)
return;
// If first element is smaller
// than last,swap them
if (arr[l] >arr[h])
{
int t = arr[l];
arr[l] = arr[h];
arr[h] = t;
}
if (h-l+1 > 2)
{
int t = (h-l+1) / 3;
stoogesort(arr, l, h-t);
stoogesort(arr, l+t, h);
stoogesort(arr, l, h-t);
}
}
static void Question7()
{
Scanner sc=new Scanner(System.in);
System.out.println(“\nQuestion 7 : “);
int n1,n2;
System.out.print(“Enter number of elements in first array :”);
n1 = sc.nextInt();
System.out.print(“Enter elements of the first array :”);
int[] A1 = new int[n1];
for(int i=0;i<n1;i++)
{
A1[i] = sc.nextInt();
}
System.out.println(“Sorted first Array :”);
stoogesort(A1,0,n1-1);
for(int i=0;i<n1;i++)
{
System.out.print(A1[i]+” “);
}
System.out.println(“\nMedian of first Array :” + A1[n1/2]);
System.out.print(“Enter number of elements in second array :”);
n2 = sc.nextInt();
System.out.print(“Enter elements of the second array :”);
int[] A2 = new int[n2];
for(int i=0;i<n2;i++)
{
A2[i] = sc.nextInt();
}
System.out.println(“Sorted first Array :”);
stoogesort(A2,0,n2-1);
for(int i=0;i<n2;i++)
{
System.out.print(A2[i]+” “);
}
System.out.println(“\nMedian of second Array :” + A2[n2/2]);
sc.close();
}
}