# UNIT 1 QB .pdf

### File information

Original filename:

**UNIT-1_QB.pdf**

Author: r.vijayakumar91@gmail.com

This PDF 1.5 document has been generated by MicrosoftÂ® Word 2010, and has been sent on pdf-archive.com on 02/04/2017 at 07:07, from IP address 49.206.x.x.
The current document download page has been viewed 754 times.

File size: 333 KB (8 pages).

Privacy: public file

### Share on social networks

### Link to this file download page

### Document preview

UNIT – I

PART - A

1.

Define notation of an algorithm.

2.

Define Algorithm and list out its characteristics.

An algorithm is a sequence of unambiguous instructions for

solving a problem, i.e., for obtaining a required output for any

legitimate input in a finite amount of time.

3.

List out various steps in algorithmic problem solving.

4.

The fundamental steps are

Understanding the problem

Ascertain the capabilities of computational device

Choose between exact and approximate problem solving

Decide on appropriate data structures

Algorithm design techniques

Methods for specifying the algorithm

Proving an algorithms correctness

Analyzing an algorithm

Coding an algorithm

State the Euclid’s algorithm for finding GCD of two given

numbers.

ALGORITHM Euclid (m, n)

//Computes gcd(m,n) by Euclid’s algorithm

//Input : Two nonnegative, not-both-zero integers m and n

//Output: Greatest common divisor of m and n

while n 0 do

r m mod n

mn

nr

return m.

5.

Write an algorithm to find number of binary digits in the

binary representation of a positive decimal integer?

(APRIL/MAY 2015)

Algorithm : Binary(n)

//input:

A positive decimal integer

//output:

The number of binary digits in n’s binary representation

6.

7.

8.

Count 1;

while n > 1 do

Count Count + 1

n [n/2]

return Count;

Write the recursive Fibonacci algorithm and its recursive relation?

(NOV/DEC 2015)

Algorithm

int fib (int n)

{

if(n==0) return 0;

elseif (n==1) return 1;

else

return fib (n-1) + fib (n-2);

Recurrence relation

T(n) = T(n-1) + T(n-2) +θ(1)

What is Algorithm Design Technique? Nov/Dec 2005

An algorithm design technique is a general approach to solve

problems algorithmically, which is applicable to a variety of

problems from different areas of computing.

Algorithm’s Correctness

To prove that the algorithm yields a required result for every

legitimate input in a finite amount of time.

What is Efficiency of algorithm?

Efficiency of an algorithm can be precisely defined and investigated

with mathematical rigor. There are two kinds of algorithm efficiency.

I. Time Efficiency – Indicates how fast the algorithm runs

II. Space Efficiency – Indicates how much extra memory the

algorithm needs.

9.

How to measure an algorithm’s running time?

Let Cop be the time of execution of an algorithm’s basic

iteration on a particular computer and let C (n) be the number of

times this operation needs to be executed for this algorithm. Then

we can estimate the running time T(n) of a program implementing

this algorithm on that computer by the formula

T(n) ≈ Cop C(n)

10. Find the basic operation and its order of growth for the

following algorithm

algorithm sum(a,n)

{

s=0.0;

for i=1 to n do

s=s+a[i];

}

Basic Operation:

Addition

Order of Growth:

11. Design an algorithm for ﬁnding the distance between the two

closest elements in an array of numbers.

12. Write algorithm for finding uniqueness of array element.

13. Define recurrence relation.

A recurrence relation is an equation that recursively

defines a sequence, once one or more initial terms are given: each

further term of the sequence is defined as a function of the preceding

terms.

14. Define order of growth.

Order of growth in algorithm means how the time for

computation increases when you increase the input size. It really

matters when your input size is very large.

15. Differentiate big oh from Omega Notation.

1.

2.

3.

the worst case running time

for an algorithm.

the lowest valued function

that will always have a higher

value than the actual running

of the algorithm.

asymptotic upper bound

the best case running time for a

given algorithm.

the highest valued function that

will always have a lower value than

the actual running of the algorithm

asymptotic lower bound

16. Say the following equalities are true or false and prove that

10n2+5n+2 O (n2).

=

case 2;

False.

17. Find the complexity of the recurrence relation T(n)= = 8T(n/2) + n

2 with T(1) = 1

18. Give the general plan for analyzing time efficiency of nonrecursive algorithm.

Decide on a parameter (or parameters) indicating an input’s size.

Identify the algorithm’s basic operation. (As a rule, it is located in

the innermost loop.)

Check whether the number of times the basic operation is executed

depends only on the size of an input. If it also depends on some

additional property, the worst-case, average-case, and, if necessary,

best-case efﬁciencies have to be investigated separately.

Set up a sum expressing the number of times the algorithm’s basic

operation is executed.

Using standard formulas and rules of sum manipulation, either ﬁnd

a closed form formula for the count or, at the very least, establish its

order of growth.

19. Solve the recurrence relation X(n)=X(n-1)+5 for n>1, X(1)=0

20. Solve the recurrence relation X(n)=X(n-1)+n for n>0, X(0)=0

21. Solve the recurrence relation X(n)=3X(n-1) for n>1 X(1)=4

22. Solve the recurrence relation T(n)=8T(n/2)+n2 using Master’s

Theorem.

Mapping with general EQN. a = 8, b = 2, d = 2

bd = 22 = 4 So, a>bd then

log a

b

log 8

2

3)

23. Find the complexity of the recurrence relation

T(n)=2T(n/2)+n2

Mapping with general EQN.

a = 2, b = 2, d = 2

bd = 22 = 4 So, a < bd

log a

b

d

24. Solve the recurrence relation x(n)=x(n/3)+1

2)

25. Give the general plan for analyzing time efficiency of

recursive algorithm.

Decide on a parameter (or parameters) indicating an input’s size.

Identify the algorithm’s basic operation. (As a rule, it is located in

the innermost loop.)

Check whether the number of times the basic operation is executed

can vary on different inputs of the same size; if it can, the worstcase, average-case, and best-case efﬁciencies must be investigated

separately.

Set up a recurrence relation, with an appropriate initial condition,

for the number of times the basic operation is executed.

Solve the recurrence or, at least, ascertain the order of growth of its

solution.

26. Consider the following recursive algorithm and setup a

recurrence relation

Algorithm Q(n)

//input: a positive integer n

if n=1 then

return 1;

else

return Q(n-1)+2n-1

PART – B

1. Explain fundamentals of problem solving in details.

2. Elaborate Asymptotic Notation with examples. Write down the properties of

Asymptotic notations

3. Solve the puzzle tower of Hanoi and give its complexity

4. Write a recursive algorithm for sum of N numbers and compute its complexity.

5. Write the recursive algorithm for Fibonacci and compute the time Efficiency

6. Give the general plan for analyzing non recursive algorithm and write down the

algorithm to find largest element in an array and compute its efficiency

### Link to this page

#### Permanent link

Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..

#### Short link

Use the short link to share your document on Twitter or by text message (SMS)

#### HTML Code

Copy the following HTML code to share your document on a Website or Blog