Content of Homework Should Start From This Page Only

Homework Title / No.
: ___2__________________________ Course Code : _________
Course Instructor : ______________________ Course Tutor (if applicable) : ____________
Date of Allotment : _____________________ Date of submission : ___________________
Student’s Roll No.____B35__________ Section No._G1007___________________

Declaration:
I declare that this assignment is my individual work. I have not copied from any other
student’s work or from any other source except where due acknowledgment is made
explicitly in the text, nor has any part been written for me by another person.
Student’s Signature :
tejinder pal__________
Evaluator’s comments:
_____________________________________________________________________
Marks obtained : ___________ out of ______________________
Content of Homework should start from this page only:
Q1- a)Specify with the example at least two advantages and disadvantages of
recursion over iterative algorithm.
Ans-The advantages and disadvantages of the recursion is given as

Advantages:
1. It is more used in the multitasking and multiprocessing environment.
2. You reduce size of the code when you use recursive call
3. It is very useful where user-defined function or sub-program or procedure required.
4. It is simple, easily under stable, concise and transparent to view the program.
5. Lesser number of programming statements required with the use of recursion.
6. It is very useful in solving the data structure problems like linked list, queues, stack,
tree, and merge sort etc.
7. It is very useful in solving mathematical, trigonometric, logical games and algebraic
problems. Like factorial, fibbonacci series, tower of Hanoi etc.
Disadvantages:
1. It requires more memory to store the automatic variable to solve the problems like
stack and so waste the memory space.
2. If properly recursion procedure is not checked, then it will create a problem for the
processing procedure run out of memory.
3. In some problems, it is a time consuming process and is not efficient.
4. It will create indefinite looping process, if condition not be applied at the proper place.
5. Recursive solution is always logical and it is very difficult to trace.(debug and
understand).
Q-1b) Code a problem of your choice with both recursion & iteration version &
report the complexity of both versions
Ans: The code of calculating the factorial using recursion is given as:
/* Factorial using the recursion */

#include<iostream.h>
#include<conio.h>
void main()
{
int n,val;
int fact(int );
clrscr();
cout<<"Enter the number=";
cin>>n;
val = fact(n);
cout<<"The factorial of "<<n<<"="<<val;
getch();
}
int fact(int n)
{
if(n==1)
return 1;
else
return n*fact(n-1);
}
Output:
Enter the number= 7
The factorial of 7=5040
The code of calculating the factorial using iteration is given as:
/* Factorial using the iteration */

#include<conio.h>
void main()
{
int n,val;
int fact(int);
clrscr();
cout<<"Enter the number=";
cin>>n;
val = fact(n);
cout<<"The factorial of "<<n<<"="<<val;
getch();
}
int fact(int n)
{
int fact=1;
for(int i=1;i<=n;i++)
fact = fact*i;
return fact;
cout<<"The factorial of"<<n<<"="<<fact;
}
Output:
Enter the number= 5
The factorial of 5=120
Q-2 Write an algorithm to find the height of the tree.
Ans: Algo to find the height of the tree
Count(LEFT.RIGHT,ROOT,DEPTH)
1. if(ROOT=NULL),then
setDEPTH:=0 and return.
2. Call Count(LEFT,RIGHT,LEFT[ROOT],DEPTHL).
3. Call Count(LEFT,RIGHT,RIGHT[ROOT],DEPTHR).
4. if(DEPTHL>DEPTHR), then
set DEPTH:=DEPTHL.
else
set DEPTH:=DEPTHR.
5. return.
Q-3 a) For a given Array of Integers devise an algorithm , that returns

th
K smallest element in the array. The algorithm should be essentially
recursive. Code the algorithm and report running times for various
problem sizes.
Ans: To solve the code is given as:
#include <iostream.h>
int small(int a[])

{
static int i;
int s;
s=a[i];
if(++i==6)
return s;
if(s>a[i])
s=a[i];
a[i]=s;
small(a);
}
void main()
{
int arr[6]={14,12,16,8,18,13};
int sm;
sm=small(arr);
cout<<”The smallest element is =”<<sm;
}
Output: The smallest Element is =8
b.) Also find Kth Smallest element both by sorting the array and by maintaining
the array as a Heap and extracting root K times.
Ans. The code for sorting the array is given as:

#include<conio.h>
void main()
{
int a[100],i,temp,n,j;
clrscr();
cout<<"Enter how many elements ";
cin>>n;
cout<<"Enter the elements ";
for(i =0;i<n;i++)
{
cin>>a[i];
}
cout<<"Elements of the array= ";
for(i =0;i<n;i++)
{
cout<<a[i]<<"\t";
}
cout<<endl<<"After the sorting array =";
for(i=0;i<n;i++)
{
for(j =i+1;j<n;j++)
{
if(a[i]> a[j])
{
temp = a[i];
a[i] =a[j];
a[j]=temp;
}
}
}
for(i =0;i<n;i++)
{
cout<<a[i]<<"\t";
}
getch();
}
Output:
Enter how many elements 6
Enter the elements 12 3 5 56 1 9
Elements of the array= 12 3 5 56 1 9
After the sorting array =1 3 5 9 12 56
Q 3 c) Find the complexity of these algorithms.

Ans : the complexity of the sorting is given as
F(n) = (n-1)+(n-2)+…..+2+1 =n(n-1)/2 = O(n2)
Q-4 Imagine a grid of 100 horizontal and vertical lines having 100x100 points. A
rectangle is then specified by two points, Upper_Left and Lower_Right. The
rectangle is visualized by the diagonal connecting these two points and lines parallel
to grid axes. Given two arbitrary rectangles specify an algorithm to find rectangle
defined by intersection of the two rectangles.
Ans: The code for this is given as:
#include<conio.h>
void main()
{
int a[10][10],i,j,u,l;
static int n=1;
clrscr();
for(i =0;i<10;i++)
{
for(j=0;j<10;j++)
{
a[i][j] =n;
n++;
}
}
cout<<"The Array ="<<endl;
for(i =0;i<10;i++)
{
for(j=0;j<10;j++)
{
cout<<a[i][j]<<"\t";
}
cout<<endl;
}
cout<<"Enter the uper & lower value of edge";
cin>>u>>l;
for(i =u-1;i<l;i++)
{
for(j=0;j<10;j++)
{
cout<<a[i][j]<<"\t";
}
cout<<endl;
}
getch();
}
Output:
The Array =
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
Enter the uper & lower value of edge 2 7

11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
Q-5 a.) Implement a recursive algorithm to find all 2N- 1 binary numbers for a given
N.
Ans:
#include<conio.h>
#include<math.h>
Void main( )
{
Void BinToDec(int num, int base) ;
int n;
I int base = 2;
Cout<<”Enter the Number =”;
Cin>>n;
BinToDec(n, base) ;
}
void BinToDec(int num, int base)
{
if (num > 0)
{
BinToDec(num / base, base);
Cout<<base;
}
}
Output: Enter the Number =12

1100
b.) Implement a recursive algorithm to find all permutations of a given Word.
Ans: #include<iostream.h>
#include<conio.h>
void swap(char *p,char *q){
char c;
c=*p;
*p=*q;
*q=c;
}
void perm(char *a,int m,int n)
{
if(m==n){
for(int i=0;i<=n;i++)
cout<<a[i];
}
else
{
for(int j=n;j<=m;j++)
{
swap(a[j],a[n]);
perm(a,m,n+1);
swap(&a[j],&a[n]);
}
}
}
int main()
{
char *a = "banana";
perm(a,strlen(a)-1,0);
getch();
return 0;
}
Output:
ba b nab aa an nb na nn

Content of Homework Should Start From This Page Only

Uploaded by

Copyright:

Available Formats

Content of Homework Should Start From This Page Only

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Content of Homework Should Start From This Page Only

Uploaded by

Copyright:

Available Formats

Homework Title / No.

: _2________________ Course Code : _

Course Instructor : __________ Course Tutor (if applicable) :

Date of Allotment : ___ Date of submission : _

Student’s Roll No.B35______ Section No._G1007___________________

Ans-The advantages and disadvantages of the recursion is given as

/* Factorial using the recursion */

The code of calculating the factorial using iteration is given as:

/* Factorial using the iteration */

Q-3 a) For a given Array of Integers devise an algorithm , that returns

int small(int a[])

Output: The smallest Element is =8

Ans. The code for sorting the array is given as:

Q 3 c) Find the complexity of these algorithms.

Enter the uper & lower value of edge 2 7

Output: Enter the Number =12

b.) Implement a recursive algorithm to find all permutations of a given Word.

You might also like