DAA- WEEK 1 ASSIGNMENT
DESIGN AND ANALYSIS OF ALGORITHMS
18CS42
SUBMISSION
DATE:01-04-2020
|
ASSIGNMENT
-1
|
||
|
Q.No.
|
Questions
|
Marks
|
|
1.
|
What
is an Algorithm? Brief the Properties.
|
5
|
|
1.
|
List
the steps to write an algorithm?
|
5
|
|
2.
|
Write
an algorithm using the specification
for computing gcd(m,n) using Euclid’s algorithm. and find the space
complexity for the algorithm.
[Note: The Euclid's algorithm (or Euclidean
Algorithm) is a method for efficiently finding the greatest
common divisor (GCD) of two numbers. The GCD of two integers
X and Y is the largest number that divides both of X and Y
(without leaving a remainder).]
|
5
|
|
3.
|
Define time complexity?Determine the no. of steps
needed by the algorithm using frequency
count and introducing count variable methods.
for
I;=1 to n do
for j:=1 to n do
for k:=1 to j
x:=x+1;
|
5
|
|
5
|
Define the
following notations with example:
1.
Big
Oh
2.
Little-oh
(REFER NOTES]
3.
Theta
notation
|
5
|
|
ASSIGNMENT-II
|
||
|
1.
|
Explain in brief any two types of problems that can be
solved using algorithm.
|
4
|
|
2.
|
Consider an element
uniqueness problem.
i.
Write
an algorithm.
ii.
Identify
the measure of input size.
iii.
Identify
the basic operation.
iv.
Find
efficiency class
|
7
|
|
3.
|
Mathematically
analyse the following recursive
algorithm to compute 2n based on the formula 2 n= 2n-1
+ 2n-1
|
7
|
|
4.
|
Mathematically
analyse the towe of Hanoi and find its time complexity.
|
7
|
Comments
Post a Comment