Anna University CS 2251 DESIGN AND ANALYSIS OF ALGORITHMS Two Marks unit 2
ALGORITHM MaxElement(A[0..n-1])
//Determines the value of the largest element in a given array
//Input:An array A[0..n-1] of real numbers
//Output: The value of the largest element in A
a[0]ßmaxval
1 to n-1 doßfor I
if A[I] > maxval
A[I]ßmaxval
return maxval
2. What are the two basic rules for sum manipulation?
The two basic rules for sum manipulation are
cai = c ai
bi) =±(ai ai bi
3. Mention the two summation formulas?
The two summation formulas are
1 = u-l+1 where l u are some lower and upper integer limits
= = 1+2+3+…+n = n(n+1)/2 n2/2 (n2)
4. Write the general plan for analyzing the efficiency for non-recursive algorithms.
The various steps include
v Decide on a parameter indicating input’s size.
v Identify the algorithms basic operation.
Check whether the number of times the basic operation is executedv depends on size of input. If it depends on some additional property the worst, average and best-case efficiencies have to be investigated separately.
v Set up a sum expressing the number of times the algorithm’s basic operation is executed.
Using standard formulas and rules of manipulation, find av closed-form formula for the count or at least establish its order of growth.
5. Give a non-recursive algorithm for element uniqueness problem.
ALGORITHM UniqueElements(A[0..n-1])
//Checks whether all the elements in a given array are distinct
//Input :An array A[0..n-1]
//Output Returns ‘true’ if all elements in A are distinct and ‘false’ //otherwise
to n-2 doßfor I
I+1 to n-1 doßfor j
if A[I] = A[j] return false
return true
6. Mention the non-recursive algorithm for matrix multiplication?
ALGORITHM MatrixMultiplication(A[0..n-1,0..n-1], B[0..n-1,0..n-1])
//Multiplies two square matrices of order n by the definition based //algorithm
//Input : Two n-by-n matrices A and B
//Output : Matrix C = AB
0 to n-1 doßfor I
0 to n-1 doßfor j
0.0ßC[I,j]
0 to n-1 doßfor k
C[I,j] + A[I,k]*B[k,j]ßC[I,j]
return C
7. Write a non-recursive algorithm for finding the number of binary digits for a positive decimal integer.
ALGORITHM Binary(n)
// Input A positive decimal integer n
// Output The number of binary digits in n’s binary representation
1ßcount
while n>1 do
count + 1ßcount
n/2ßn
return count
8. Write a recursive algorithm to find the n-th factorial number.
ALGORITHM F(n)
// Computes n! recursively
// Input A non-negative integer n
// Output The value of n!
if n=0 return 1
else return F(n-1) * n
9. What is the recurrence relation to find out the number of multiplications and the initial condition for finding the n-th factorial number?
The recurrence relation and initial condition for the number of multiplications is
M(n)=M(n-1)+1 for n>0
M(0)=0
10. Write the general plan for analyzing the efficiency for recursive algorithms.
The various steps include
v Decide on a parameter indicating input’s size.
v Identify the algorithms basic operation.
Check whether the number of times the basic operation is executedv depends on size of input. If it depends on some additional property the worst, average and best-case efficiencies have to be investigated separately.
v Set up a recurrence relation with the appropriate initial condition , for the number of times the basic operation is executed.
v Solve the recurrence or at least ascertain the orders of growth of its solution.
11. Write a recursive algorithm for solving Tower of Hanoi problem.
ALGORITHM
To move nv>1 disks from peg1 to peg3, with peg2 as auxiliary, first move recursively n-1 disks from peg1 to peg2 with peg3 as auxiliary.
v Then move the largest disk directly from peg1 to peg3
v Finally move recursively n-1 disks from peg2 to peg3 with peg1 as auxiliary
v If n=1 simply move the single disk from source peg to destination peg.
12. What is the basic operation in the Tower of Hanoi problem and give the recurrence relation for the number of moves?
The moving of disks is considered the basic operation in the Tower of Hanoi problem and the recurrence relation for the number of moves is given as
M(n)=2M(n)+1 for n>1
M(1)=1
13. Write a recursive algorithm to find the number of binary digits in the binary representation of an integer.
ALGORITHM BinRec(n)
// Input A positive decimal integer n
// Output The number of binary digits in n’s binary representation
if n=1 return 1
else return BinRec(n/2)+1
14. Who introduced the Fibonacci numbers and how can it be defined by a simple recurrence?
Leonardo Fibonacci introduced the fibonacci numbers in 1202 as a solution to a problem about the size of rabbit population. It can be defined by the simple recurrence
F(n)=F(n-1)+F(n-2) for n>1
And two initial conditions
F(0)=0 and F(1)=1
15. What is the explicit formula for the nth Fibonacci number?
The formula for the nth Fibonacci number is given by
F(n)= 1/ ( n - n)
Where
=(1+ )/2
=(1- )/2
16. Write a recursive algorithm for computing the nth fibonacci number?
ALGORITHM F(n)
// Computes the nth Fibonacci number recursively by using the definition
// Input A non-negative integer n
// Output The nth Fibonacci number
if n 1 return n
else return F(n-1)+F(n-2)
17. Write a non-recursive algorithm for computing the nth fibonacci number.
ALGORITHM Fib(n)
// Computes the nth Fibonacci number iteratively by using its definition
// Input A non-negative integer n
// Output The nth Fibonacci number
0;ßF[0]
1ßF[1]
2 to n doßFor I
F[I-1]+F[I-2]ßF[I]
return F[n]
18. (log n) algorithm for computing the nth fibonacci number based on?QWhat is the
(log n) algorithm for computing the nth fibonacciQThere exists a number that manipulates only integers. It is based on the equality
= for n 1 with an efficient way of computing matrix powers
19. What is the general plan for the Empirical Analysis of Algorithm Efficiency?
The general plan is as follows
v Understand the experiment’s purpose.
v Decide on the efficiency metric M to be measured & the measurement unit.
v Decide on characteristics of the input sample
v Prepare a program implementing the algorithm for the experimentation
v Generate a sample of inputs
v Run the algorithm on the sample input and record the data observed
v Analyze the data obtained
20. Give the various system commands used for timing the program implementing the algorithm.
The system commands are as follows
UNIX time command
C & C++ function clock
Java method currentTimeMillis() in the System class
21. Mention the linear congruential method for generating pseudorandom numbers.
ALGORITHM Random(n,m,seed,a,b)
//Generates a sequence of n pseudorandom numbers using linear congruential //method
//Input A positive integer n and positive integer parameters m, seed, a, b
//Output A sequence r1,…..,rn of n pseudorandom integers uniformly distributed //among integer values between 0 and m-1
seedßr0
1 to n doßfor I
(a*ri-1+b) mod mßri
22. What are the guidelines in choosing the values of m, seed, a, b for linear congruential method
The recommendations are as follows
seed May be chosen arbitrarily and is often set to current date and time
m Should be large and may be conveniently taken as 2w where w is the computer’s word size
a Should be selected as an integer between 0.01m and 099m with no particular pattern in its digits but such that a mod 8=5
b The value can be chosen as 1
23. What is algorithm visualization?
Algorithm visualization is a way to study algorithms. It is defined as the use of images to convey some useful information about algorithms. That information can be a visual illustration of algorithm’s operation, of its performance on different kinds of inputs, or of its execution speed versus that of other algorithms for the same problem.
24. What are the two variations of algorithm visualization?
The two principal variations of algorithm visualization”
v Static algorithm visualization: It shows the algorithm’s progress through a series of still images
v Dynamic algorithm visualization: Algorithm animation shows a continuous movie like presentation of algorithms operations
25. What are the features that are desired in algorithm animation?
Peter Gloor, who was the principal developer of Animated Algorithms suggested the following desirable features
v Be consistent
v Be interactive
v Be clear and concise
v Be forgiving to the user
v Adapt to the knowledge level of the user
v Emphasize the visual component
v Keep the user interested
v Incorporate both symbolic and iconic representations
v Include algorithm’s analysis & comparisons with other algorithms for the same problem
v Include execution history
26. What are the applications of algorithm visualization?
The two applications are
v Research: Based on expectations that algorithm visualization may help uncover some unknown feature of the algorithm
v Education: Seeks to help students learning algorithms
Explain the algorithms
§ Max element
§ General Plan
§ Unique Elements
§ Matrix Multiplication
§ Binary Representation
2. Explain Recursive algorithms with suitable examples
Explain the algorithms
• Factorial
• General Plan
• Towers of Hanoi
• Binary Representation
3. Discuss about the empirical analysis of algorithms
Explain
• General Plan
• Pseudo random numbers
4. Discuss briefly about Algorithmic visualization
Explain
• Static algorithm visualization
• Dynamic algorithm visualization
5. Discuss about the Fibonacci numbers
Explain about
§ Explicit formula
§ Computation
§ Iterative algorithm
2 Marks
1. Give an non-recursive algorithm to find out the largest element in a list of n numbers.ALGORITHM MaxElement(A[0..n-1])
//Determines the value of the largest element in a given array
//Input:An array A[0..n-1] of real numbers
//Output: The value of the largest element in A
a[0]ßmaxval
1 to n-1 doßfor I
if A[I] > maxval
A[I]ßmaxval
return maxval
2. What are the two basic rules for sum manipulation?
The two basic rules for sum manipulation are
cai = c ai
bi) =±(ai ai bi
3. Mention the two summation formulas?
The two summation formulas are
1 = u-l+1 where l u are some lower and upper integer limits
= = 1+2+3+…+n = n(n+1)/2 n2/2 (n2)
4. Write the general plan for analyzing the efficiency for non-recursive algorithms.
The various steps include
v Decide on a parameter indicating input’s size.
v Identify the algorithms basic operation.
Check whether the number of times the basic operation is executedv depends on size of input. If it depends on some additional property the worst, average and best-case efficiencies have to be investigated separately.
v Set up a sum expressing the number of times the algorithm’s basic operation is executed.
Using standard formulas and rules of manipulation, find av closed-form formula for the count or at least establish its order of growth.
5. Give a non-recursive algorithm for element uniqueness problem.
ALGORITHM UniqueElements(A[0..n-1])
//Checks whether all the elements in a given array are distinct
//Input :An array A[0..n-1]
//Output Returns ‘true’ if all elements in A are distinct and ‘false’ //otherwise
to n-2 doßfor I
I+1 to n-1 doßfor j
if A[I] = A[j] return false
return true
6. Mention the non-recursive algorithm for matrix multiplication?
ALGORITHM MatrixMultiplication(A[0..n-1,0..n-1], B[0..n-1,0..n-1])
//Multiplies two square matrices of order n by the definition based //algorithm
//Input : Two n-by-n matrices A and B
//Output : Matrix C = AB
0 to n-1 doßfor I
0 to n-1 doßfor j
0.0ßC[I,j]
0 to n-1 doßfor k
C[I,j] + A[I,k]*B[k,j]ßC[I,j]
return C
7. Write a non-recursive algorithm for finding the number of binary digits for a positive decimal integer.
ALGORITHM Binary(n)
// Input A positive decimal integer n
// Output The number of binary digits in n’s binary representation
1ßcount
while n>1 do
count + 1ßcount
n/2ßn
return count
8. Write a recursive algorithm to find the n-th factorial number.
ALGORITHM F(n)
// Computes n! recursively
// Input A non-negative integer n
// Output The value of n!
if n=0 return 1
else return F(n-1) * n
9. What is the recurrence relation to find out the number of multiplications and the initial condition for finding the n-th factorial number?
The recurrence relation and initial condition for the number of multiplications is
M(n)=M(n-1)+1 for n>0
M(0)=0
10. Write the general plan for analyzing the efficiency for recursive algorithms.
The various steps include
v Decide on a parameter indicating input’s size.
v Identify the algorithms basic operation.
Check whether the number of times the basic operation is executedv depends on size of input. If it depends on some additional property the worst, average and best-case efficiencies have to be investigated separately.
v Set up a recurrence relation with the appropriate initial condition , for the number of times the basic operation is executed.
v Solve the recurrence or at least ascertain the orders of growth of its solution.
11. Write a recursive algorithm for solving Tower of Hanoi problem.
ALGORITHM
To move nv>1 disks from peg1 to peg3, with peg2 as auxiliary, first move recursively n-1 disks from peg1 to peg2 with peg3 as auxiliary.
v Then move the largest disk directly from peg1 to peg3
v Finally move recursively n-1 disks from peg2 to peg3 with peg1 as auxiliary
v If n=1 simply move the single disk from source peg to destination peg.
12. What is the basic operation in the Tower of Hanoi problem and give the recurrence relation for the number of moves?
The moving of disks is considered the basic operation in the Tower of Hanoi problem and the recurrence relation for the number of moves is given as
M(n)=2M(n)+1 for n>1
M(1)=1
13. Write a recursive algorithm to find the number of binary digits in the binary representation of an integer.
ALGORITHM BinRec(n)
// Input A positive decimal integer n
// Output The number of binary digits in n’s binary representation
if n=1 return 1
else return BinRec(n/2)+1
14. Who introduced the Fibonacci numbers and how can it be defined by a simple recurrence?
Leonardo Fibonacci introduced the fibonacci numbers in 1202 as a solution to a problem about the size of rabbit population. It can be defined by the simple recurrence
F(n)=F(n-1)+F(n-2) for n>1
And two initial conditions
F(0)=0 and F(1)=1
15. What is the explicit formula for the nth Fibonacci number?
The formula for the nth Fibonacci number is given by
F(n)= 1/ ( n - n)
Where
=(1+ )/2
=(1- )/2
16. Write a recursive algorithm for computing the nth fibonacci number?
ALGORITHM F(n)
// Computes the nth Fibonacci number recursively by using the definition
// Input A non-negative integer n
// Output The nth Fibonacci number
if n 1 return n
else return F(n-1)+F(n-2)
17. Write a non-recursive algorithm for computing the nth fibonacci number.
ALGORITHM Fib(n)
// Computes the nth Fibonacci number iteratively by using its definition
// Input A non-negative integer n
// Output The nth Fibonacci number
0;ßF[0]
1ßF[1]
2 to n doßFor I
F[I-1]+F[I-2]ßF[I]
return F[n]
18. (log n) algorithm for computing the nth fibonacci number based on?QWhat is the
(log n) algorithm for computing the nth fibonacciQThere exists a number that manipulates only integers. It is based on the equality
= for n 1 with an efficient way of computing matrix powers
19. What is the general plan for the Empirical Analysis of Algorithm Efficiency?
The general plan is as follows
v Understand the experiment’s purpose.
v Decide on the efficiency metric M to be measured & the measurement unit.
v Decide on characteristics of the input sample
v Prepare a program implementing the algorithm for the experimentation
v Generate a sample of inputs
v Run the algorithm on the sample input and record the data observed
v Analyze the data obtained
20. Give the various system commands used for timing the program implementing the algorithm.
The system commands are as follows
UNIX time command
C & C++ function clock
Java method currentTimeMillis() in the System class
21. Mention the linear congruential method for generating pseudorandom numbers.
ALGORITHM Random(n,m,seed,a,b)
//Generates a sequence of n pseudorandom numbers using linear congruential //method
//Input A positive integer n and positive integer parameters m, seed, a, b
//Output A sequence r1,…..,rn of n pseudorandom integers uniformly distributed //among integer values between 0 and m-1
seedßr0
1 to n doßfor I
(a*ri-1+b) mod mßri
22. What are the guidelines in choosing the values of m, seed, a, b for linear congruential method
The recommendations are as follows
seed May be chosen arbitrarily and is often set to current date and time
m Should be large and may be conveniently taken as 2w where w is the computer’s word size
a Should be selected as an integer between 0.01m and 099m with no particular pattern in its digits but such that a mod 8=5
b The value can be chosen as 1
23. What is algorithm visualization?
Algorithm visualization is a way to study algorithms. It is defined as the use of images to convey some useful information about algorithms. That information can be a visual illustration of algorithm’s operation, of its performance on different kinds of inputs, or of its execution speed versus that of other algorithms for the same problem.
24. What are the two variations of algorithm visualization?
The two principal variations of algorithm visualization”
v Static algorithm visualization: It shows the algorithm’s progress through a series of still images
v Dynamic algorithm visualization: Algorithm animation shows a continuous movie like presentation of algorithms operations
25. What are the features that are desired in algorithm animation?
Peter Gloor, who was the principal developer of Animated Algorithms suggested the following desirable features
v Be consistent
v Be interactive
v Be clear and concise
v Be forgiving to the user
v Adapt to the knowledge level of the user
v Emphasize the visual component
v Keep the user interested
v Incorporate both symbolic and iconic representations
v Include algorithm’s analysis & comparisons with other algorithms for the same problem
v Include execution history
26. What are the applications of algorithm visualization?
The two applications are
v Research: Based on expectations that algorithm visualization may help uncover some unknown feature of the algorithm
v Education: Seeks to help students learning algorithms
16 Marks
1. Explain Non-Recursive algorithms with suitable examplesExplain the algorithms
§ Max element
§ General Plan
§ Unique Elements
§ Matrix Multiplication
§ Binary Representation
2. Explain Recursive algorithms with suitable examples
Explain the algorithms
• Factorial
• General Plan
• Towers of Hanoi
• Binary Representation
3. Discuss about the empirical analysis of algorithms
Explain
• General Plan
• Pseudo random numbers
4. Discuss briefly about Algorithmic visualization
Explain
• Static algorithm visualization
• Dynamic algorithm visualization
5. Discuss about the Fibonacci numbers
Explain about
§ Explicit formula
§ Computation
§ Iterative algorithm
0 comments:
Post a Comment