QUESTION BANK
231CSC402T- DESIGN AND ANALYSIS OF ALGORITHMS
UNIT- IINTRODUCTION
PART-A
1. What is the need for studying algorithms?
A standard set of algorithms from different areas of computing must be known, in addition
to be able to design them and analyze their efficiencies. From a theoretical standpoint the
study of algorithms in the comerstone of computer science.
2. Define algorithmics?
The study of algorithms is called algorithmics. It is more than a branch of computer science.
It is the core of computer science and is said to be relevant to most of science, business and
technology.
3. What is an algorithm?. (June 06,07,May 13,17,Dec 18)
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for
obtaining a required output for any legitimate input in finite amount of time.
4. Give the diagram representation of Notion of algorithm.
Problem
Algorithm
Input "Computer" + Output
5. Mention the Euclid's algorithm for finding the greatest common divisor of two
numbers? (NOV/DEC 2019)
Euclid's algorithm for computing gcd(m, n)
Step 1 If n = 0, return the value of m as the answer and stop; otherwise,
proceed to Step 2.
Step 2 Divide m by n and assign the value of the remainder to r.
Step 3 Assign the value of n to m and the value of r to n. Go to Step 1.
Euclid's algorithm is based on repeatedly applying the equality
Ged(m,n)=-Gcd(n,m mod n) until m mod n is equal to 0, since ged(m,0)=m.
6. What are the three different algorithms used to find the ged of two numbers?
The three algorithms used to find the gcd of two numbers are
Euclid's algorithm
$ Consecutive integer checking algorithm
Middle school procedure
7. What are the fundamental steps involved in algorithmic problem solving?
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
8. What is an algorithm design technique?
An algorithm design technique is a general approach to solving problems algorithmically
that is applicable to a variety of problems from different areas of computing.
9. What is pseudocode?
A pseudocode is a mixture of a natural language and programming language constructs to
specify an algorithm. A pseudocode is more precise than a natural language and its usage
often yields more concise algorithm descriptions.
10 What are the types of algorithm efficiencies?
The two types of algorithm efficiencies are
* Time eficiency: indicates how fast the algorithm runs
& Space efficiency: indicates how much extra memory the algorithm needs
11. Mention some of the important problem types?
Some of the important problem types are as follows
Sorting
o Searching
String processing
Graph problems
Combinatorial problems
Geometric problems
8 Numerical problems
12. What are the classical geometric problems?
The two classic geometric problems are
The closest pair problem: given n points in a plane find the closest pair among them
* The convex hull problem: find the smallest convex polygon that would include all
the points of a given set.
13. What are the steps involved in the analysis framework?
The various steps are as follows
Measuring the input's size
Units for measuring running time
Orders of growth
Worst case, best case and average case efficiencies
14. What is the basic operation of an algorithm and how is it identified?
The most important operation of the algorithm is called the basic operation of the algorithm,
the operation that contributes the most to the total running time. It can be identified easily
because it is usually the most time consuming operation in the algorithms innermost loop.
15. What is the running time ofa program implementing the algorithm?
The running time T(n) is given by the following formula
T(n) c,C(n)
C, is the time of execution of an algorithm's basic operation on aexecuted
particularfor the
and C(n) is the number of times this operation needs be
algorithm.
16. What are exponential growth functions?
The functions 2 and n! are exponential growth functions, because these two functions grow
so fast that their values become astronomically large even for rather smaller values of n.
17. What is worst-case efficiency? (Nov/Dec18)
The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n,
which is an input or inputs of size n for which the algorithm runs the longest among all
possible inputs of that size.
18. What is best-case efficiency?
The best-case efficiency of an algorithm is its efficiency for the best-case input of size n,
which is an input or inputs for which the algorithm runs the fastest among all possible inputs
of that size.
19. What is average case efficiency?
The average case efficiency of an algorithm is its efficiency for an average case input of size
n. It provides information about an algorithm behavior on a "typical" or "random" input.
20. What is amortized efficiency?
In some situations a single operation can be expensive, but the total time for the entire
sequence of n such operations is always significantly better that the worst case efficiency of
that single operation multiplied by n. this is called amortized efficiency.
21. Define O-notation? (June 06,May 13) or
When is the function f(n) said to be O(g(n))? (Dec 18)
A function t(n) is said to be in O(g(n), denoted by t(n) e O(g(n), if t(n) is bounded above
by some constant multiple of g(n) for all large n, i.e., if there exists some positive constant c
and some nonnegative integer n, such that
T(n) < cg(n) for all nn,
22. Define l-notation? A function t(n) is said to be in 2g(n)), denoted by t(n) e R(g(n)), if t(n)
is bounded below by some constant multiple of g(n) for all large n, i.e., if there exists some
positive constant c and some nonnegative integer no such that
T(n) > cg(n) for all n no
23. Define O-notation? (Nov/Dec 14)
A function t(n) is said to be O(gn)), denoted by t(n) e (g(n), if t(n) is bounded both
above & below by some constant multiple of g(n) for all large n, i.e., if there exists some
positive constants C1 & c: and some nonnegative integer no such that C:g(n) s t(n) <
C1g(n) for all n no
24. Mention the useful property, which can be applied to the asymptotic notations and its
use?
If t.(n) [ O(g:(n)) and t(n) [ O(g:(n)) then ti(ntt(n) Emax (g.(n).g:(n)} this property is also true
for 2 and notations. This property will be useful in analyzing algorithms that
comprise of two consecutive executable parts.
25. What are the basic asymptotic efficiency classes?
The various basic efficiency classes are
Constant
Logarithmic : log n
Linear
& N-log-n nlog n
Quadratic
Cubic :n
& Exponential :2
Factorial :n!
[Link] 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.
[Link] are the two variations of algorithm visualization?
The two principal variations of algorithm visualizationl._Static algorithm
visualization: It shows the algorithm's progress through a series of still images_
o Dynamic algorithm visualization: Algorithm animation shows a
continuous movie like presentation of algorithms operations
[Link] is order of growth?
Measuring the performance of an algorithm based on the input size n is called order of growth.
[Link] the properties of asymptotic notations. (June 06, May 15)
Sum rule:0(f(n) ) +0 (g(n) =0 (max {f(n),g(n)})lTransitivity rule : f(n) = 0(gtn) and
g(n) = 0(h(n) then f(n) = O(h(n)| Reflexivity: f(n)= 0(f(n)l Any constant value is
equivalent to O (1).lPolynomial Rule: Let f(n) be any polynomial in n, with kbeing the
highestl exponent. f(n) = O(nk)
PART -B
1. Explain the fundamentals of algorithmanalysis.
2. What are the steps need to be followed while designing and analyzing an algorithm? Brief
it
3. Define the Asymptotic notations used for the best case, average case and worst case
analysis of algorithms.(NOV/DEC 2019)
4. How do we judge the efficiency of an algorithm? Explain the terms: Average case and
Worst case complexities of an algorithm.
5. Write an algorithm for finding maximum element of an array, perform best, worst and
average case complexity with appropriate order notations.
6. an algorithm to perform a linear search of an array. Perform the best, worst and
average case complexity, defining the notations used for each type of analysis.
7. Derive the recurrence equation for Fibonacci series. Perform Complexity analysis for the
same.
8. State and prove the properties of the Big -Oh notation. Explain in detail about the
recurrence equation with example.
9. State the general plan for analyzing the time efficiency of recursive algorithm with an
example (NOV/DEC 2019)