DURGASOFT
0
factorial by using loop = 1
factorial by using recursion = 1
C:\prakashclasses>java Test
Enter n value
-9
Arey what happend to you factorial for -ve num not existed
C:\prakashclasses>
IMPLEMENT A PROGRAM TO CHECK WHETHER THE GIVEN NUMBER IS PRIME OR
NOT
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Algorithm:
1. read a number 'n' from the user.
2. apply logic
logic1:
by using loop
factors = 0
for(i=1;i<=n;i++)
{
if(n%i==0)
factors++;
}
if factors==2 then print "Yes" else "No"
logic2:
by using recursion
boolean isPrime(int n,int i) //i=n/2
{
if(i==1)
return true;
else if(n%i==0)
return false;
else
return isPrime(n,--i);
}
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
21 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
3. print the status "Yes" or "No"
implementation:
---------------
class Demo
{
static boolean isPrime1(int n)
{
//loop
int i,f=0;
for(i=1;i<=n;i++)
{
if(n%i==0)
f++;
}
return f==2;
}
static boolean isPrime2(int n,int i)
{
//recursion
if(i==1)
return true;
else if(n%i==0)
return false;
else
return isPrime2(n,--i);
}
}
class Test
{
public static void main(String[] args)
{
[Link] obj = new [Link]([Link]);
[Link]("Enter n value");
int n = [Link]();
for(int i=2;i<=n;i++)
{
[Link](i+"\t"+(Demo.isPrime1(i)?"Yes":"No")+"\t"+(Demo.isPrime2(i,i/2)?
"Yes":"No"));
}
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
22 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
}
}
IMPLEMENT A PROGRAM/ALG TO GENERATE FIBNOCCI NUMBERS
----------------------------------------------------
sum of previous two numbers, where the series starts from 0,1
0, 1 ----> 0, 1, 1, 2, 3, 5, 8, 13, .....
algorithm:
----------
1. read n value from the user.
2. Create Array List object
3. push all the calcualte fib seq, into array list
logic:
a = 0;
b = 1;
[Link](a);
[Link](b);
for(i=1;i<=n-2;i++)
{
c=a+b;
[Link](c);
a=b;
b=c;
}
4. print array list
implementation:
---------------
import [Link].*;
class Demo
{
static ArrayList<Integer> getFibonacciNums(int n)
{
int a,b,c,i;
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
23 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
ArrayList<Integer> al = new ArrayList<Integer>();
a = 0;
b = 1;
[Link](a);
[Link](b);
for(i=1;i<=n-2;i++)
{
c=a+b;
[Link](c);
a=b;
b=c;
}
return al;
}
}
class Test
{
public static void main(String[] args)
{
[Link] obj = new [Link]([Link]);
[Link]("Enter n value");
int n = [Link]();
[Link]([Link](n));
}
}
C:\prakashclasses>javac [Link]
C:\prakashclasses>java Test
Enter n value
5
[0, 1, 1, 2, 3]
C:\prakashclasses>java Test
Enter n value
10
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
IMPLEMENT A PROGRAM/ALG TO GENERATE TRIBONACCI NUMBERS
----------------------------------------------------
sum of previous three numbers, where the series starts from 0,1,2
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
24 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
0, 1, 2 ----> 0, 1, 2, 3, 6, 11, 20, ....
algorithm:
----------
1. read n value from the user.
2. Create Array List object
3. push all the calcualte trib seq, into array list
logic:
a = 0;
b = 1;
c = 2;
[Link](a);
[Link](b);
[Link](c);
for(i=1;i<=n-3;i++)
{
d=a+b+c;
[Link](d);
a=b;
b=c;
c=d;
}
4. print array list
implementation:
---------------
import [Link].*;
class Demo
{
static ArrayList<Integer> getTribonacciNums(int n)
{
int a,b,c,d,i;
ArrayList<Integer> al = new ArrayList<Integer>();
a = 0;
b = 1;
c = 2;
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
25 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
[Link](a);
[Link](b);
[Link](c);
for(i=1;i<=n-3;i++)
{
d=a+b+c;
[Link](d);
a=b;
b=c;
c=d;
}
return al;
}
}
class Test
{
public static void main(String[] args)
{
[Link] obj = new [Link]([Link]);
[Link]("Enter n value");
int n = [Link]();
[Link]([Link](n));
}
}
C:\prakashclasses>javac [Link]
C:\prakashclasses>java Test
Enter n value
10
[0, 1, 2, 3, 6, 11, 20, 37, 68, 125]
performance of an algorithm
~~~~~~~~~~~~~~~~~~~~~~~~~~~
we can measure performance of an algorithm by using the following two
components.
1. space complexity
2. time complexity
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
26 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
space complexity:
-----------------
=> the space complexity of an algorithm is the amount of memory, it needs to run to
complete task.
=> space complexity of any algorithm is calculate as,
s(p) = fixed_part + variable_part
=> fixed part --> independent of instance characterstics
--> space for variables, space for constants etc
=> variable_part --> dependent of instance characterstics
--> looping variables, arrays etc
Ex: addition of three numbers.
------------------------------
algorithm addition(a,b,c)
{
return a+b+c;
}
space complexity ----->
a ---> 1 unit
b ---> 1 unit
c ---> 1 unit
-------------
total: 3 units
--------------
sp(addition) = 3 units
Ex: area of circle
------------------
algorithm areaofcircle(raidus)
{
result = 3.147*radius*radius;
return result;
}
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
27 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
space complexity ----->
radius ---> 1 unit
3.147 ---> 1 unit
result ---> 1 unit
------------------
total: 3 units
------------------
sp(addition) = 3 units
Ex: area of circle
------------------
algorithm areaofcircle(raidus)
{
return 3.147*radius*radius;
}
space complexity ----->
radius ---> 1 unit
3.147 ---> 1 unit
------------------
total: 2 units
------------------
sp(addition) = 2 units
bits/bytes/kb/mb/gb/tb/pb etc
2 x 4 bytes = 8 bytes
int a = 5;
sp(alg) = 1 unit
Ex:
String s = "java";
sp(s) = 1 unit
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
28 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
c---> 1
py -> 1
java-> 1 unit
Ex:
int i = null;
1 unit
Ex: sum of 'n' natural numbers
------------------------------
algorithm sum_of_n(n)
{
s=0;
for(i=0;i<=n;i++)
{
s=s+i;
}
return s;
}
space complexity ------>
n ----> 1 unit
s ----> 1 unit
i ----> 1 unit
--------------
total-> 3 units
---------------
Ex: sum of elements in an array 'a'
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
algorithm sum_array(a,n)
{
s=0;
for(i=0;i<n;i++)
{
s=s+a[i];
}
return s;
}
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
29 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]
DURGASOFT
space complexity ------>
a ----> n units
n ----> 1 unit
s ----> 1 unit
i ----> 1 unit
-----------------
sp ---> n+3 units
------------------
Ex: sum of elements present in an array by using recursion
----------------------------------------------------------
algorithm sum_of_elements_recursion(a,n)
{
if(n<0)
return 0;
else
return sum_of_elements_recursion(a,n-2)+a[n-1];
}
space complexity ----->
Rsum(a,n) -----> 1(a[n-1]) + 1(n) + 1(return) ---> 3 units
Rsum(a,n-1) ---> 1(a[n-2]) + 1(n) + 1(return) ---> 3 units
.
.
.
.
Rsum(a,n-n) --> 1(a[n-n]) + 1(n) + 1(return) ----> 3 units
-----------------------------------------------------------
total space complexity ----> 3(n+1) ===> 3n+3
-----------------------------------------------------------
Ex: Factorial of the given number using recursion
-------------------------------------------------
algorithm fact(n)
{
if(n==0)
return 1;
DURGASOFT, # 202, 2nd Floor, HUDA Maitrivanam, Ameerpet, Hyderabad - 500038,
30 88 85 25 26 27, 72 07 21 24 27/28 | [Link]
Maii: durgasoftonline@[Link]