CS2251 -DESIGN AND
ANALYSIS OF ALGORITHMS
UNIT –I
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
2.
State the Euclid
ALGORITHM Euclid
// Computes gcd(m,n) by Euclid
//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
m ß n
n ß r
return m.
3.
What are Sequential Algorithms?
The
central assumption of the RAM model is that instructions are executed one after
another, one operation at a time. Accordingly, algorithms designed to be
executed on such machines are called Sequential algorithms.
4.
What are Parallel Algorithms?
The central assumption of the RAM model does not hold
for some newer computers that can execute operations concurrently, i.e., in
parallel algorithms that take advantage of this capability are called Parallel
algorithms.
5.
What is Exact and Approximation algorithm?
The principal decision to choose solving the problem
exactly is called exact algorithm.
The principal decision to choose solving the problem
approximately is called Approximation algorithm.
6.
What is Algorithm Design Technique? Nov/Dec 2005
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.
7.
Define Pseudo code.
A Pseudo code is a mixture of a natural
language and programming language like constructs. A pseudo code is usually
more precise than a natural language, and its usage often yields more succinct
algorithm descriptions.
8.
Define Flowchart.
A
method of expressing an algorithm by a collection of connected geometric shapes
containing descriptions of the algorithm’s steps.
9.
Explain Algorithm’s Correctness
To
prove that the algorithm yields a required result for every legitimate input in
a finite amount of time.
Example:
Correctness of Euclid
10.
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
1)
Time Efficiency – Indicates how fast the algorithm runs
2)
Space Efficiency – Indicates how much extra memory the
algorithm needs.
11.
What is generality of an algorithm?
It
is a desirable characteristic of an algorithm. Generality of the problem the
algorithm solves is sometimes easier to design an algorithm for a problem posed
in more general terms.
12.
What is algorithm’s Optimality?
Optimality is about the complexity of the problem
that algorithm solves. What is the minimum amount of effort any algorithm will
need to exert to solve the problem in question is called algorithm’s
Optimality.
13.
What do you mean by ²Sorting”
problem?
The sorting problem asks us to rearrange the items of a given list in
ascending order (or descending order)
14.
What do you mean by ²Searching”
problem?
The searching problem deals with finding a given value, called a search
key, in a given set.
15.
What do you mean by ²Worst
case-Efficiency” of an algorithm?
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.
Ex: if you want to sort a list of numbers in ascending
order when the numbers are given in descending order. In this running time will
be the longest.
No comments:
Post a Comment