Anna University CS 2251 DESIGN AND ANALYSIS OF ALGORITHMS Two Marks unit 1
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 cornerstone of computer science.
2. What is 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?
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.
5. What is the formula used inEuclid
Euclid
Gcd(m,n)=gcd(n,m mod n) until m mod n is equal to 0, since gcd(m,0)=m.
6. What are the three different algorithms used to find the gcd of two numbers?
The three algorithms used to find the gcd of two numbers are
vEuclid
v Consecutive integer checking algorithm
v Middle school procedure
7. What are the fundamental steps involved in algorithmic problem solving?
The fundamental steps are
v Understanding the problem
v Ascertain the capabilities of computational device
v Choose between exact and approximate problem solving
v Decide on appropriate data structures
v Algorithm design techniques
v Methods for specifying the algorithm
v Proving an algorithms correctness
v Analyzing an algorithm
v 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
v Time efficiency: indicates how fast the algorithm runs
v 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
v Sorting
v Searching
v String processing
v Graph problems
v Combinatorial problems
v Geometric problems
v Numerical problems
12. What are the classical geometric problems?
The two classic geometric problems are
v The closest pair problem: given n points in a plane find the closest pair among them
v 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
v Measuring the input’s size
v Units for measuring running time
v Orders of growth
v 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 of a program implementing the algorithm?
The running time T(n) is given by the following formula
T(n) ≈ copC(n)
cop is the time of execution of an algorithm’s basic operation on a particular computer and C(n) is the number of times this operation needs to be executed for the particular algorithm.
16. What are exponential growth functions?
The functions 2n 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?
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?
A function t(n) is said to be in O(g(n)), denoted by t(n) ɛ 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 n0 such that
T(n) ≤ cg(n) for all n ≥ n0
22. Define Ω-notation?
A function t(n) is said to be in Ω(g(n)), denoted by t(n) ɛ Ω(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 n0 such that
T(n) ≥ cg(n) for all n ≥ n0
23. Define Θ-notation?
A function t(n) is said to be in Θ(g(n)), denoted by t(n) ɛ Θ(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 & c2 and some nonnegative integer n0 such that c2g(n) ≤ t(n) ≤ c1g(n) for all n ≥ n0
24. Mention the useful property, which can be applied to the asymptotic notations and its use?
If t1(n) ɛ O(g1(n)) and t2(n) ɛ O(g2(n)) then t1(n)+t2(n) ɛ max {g1(n),g2(n)} this property is also true for Ω 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
v Constant : 1
v Logarithmic : log n
v Linear : n
v N-log-n : nlog n
v Quadratic : n2
v Cubic : n3
v Exponential : 2n
v Factorial : n!
Explain about
• Understanding
• Ascertaining
• Choosing
• Deciding
• Designing
• Specifying
• Proving
• Analyzing
• Coding of an algorithm
2. Discuss the important problem types
Explain about
• Sorting
• Searching
• String Processing
• Graph Problems
• Combinatorial Problems
• Geometric Problems
• Numerical Problems
3. Explain Analysis framework with example
Explain about
• Measuring an input size
• Units for measuring running time
• Orders of growth
• Worst,Best and Average case efficiencies
• Recapitulation of the framework
4. Discuss the Asymptotic notations with efficiency classes and examples
Explain about
• Big-Oh notation
• Big-Theta notation
• Big-Omega notation
• Properties of notations
• Orders of growth
• Efficiency classes
Explain about
• Understanding
• Ascertaining
• Choosing
• Deciding
• Designing
• Specifying
• Proving
• Analyzing
• Coding of an algorithm
2. Discuss the important problem types
Explain about
• Sorting
• Searching
• String Processing
• Graph Problems
• Combinatorial Problems
• Geometric Problems
• Numerical Problems
3. Explain Analysis framework with example
Explain about
• Measuring an input size
• Units for measuring running time
• Orders of growth
• Worst,Best and Average case efficiencies
• Recapitulation of the framework
4. Discuss the Asymptotic notations with efficiency classes and examples
Explain about
• Big-Oh notation
• Big-Theta notation
• Big-Omega notation
• Properties of notations
• Orders of growth
• Efficiency classes
2 Marks
1. What is the need of 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 cornerstone of computer science.
2. What is 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?
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.
5. What is the formula used in
Gcd(m,n)=gcd(n,m mod n) until m mod n is equal to 0, since gcd(m,0)=m.
6. What are the three different algorithms used to find the gcd of two numbers?
The three algorithms used to find the gcd of two numbers are
v
v Consecutive integer checking algorithm
v Middle school procedure
7. What are the fundamental steps involved in algorithmic problem solving?
The fundamental steps are
v Understanding the problem
v Ascertain the capabilities of computational device
v Choose between exact and approximate problem solving
v Decide on appropriate data structures
v Algorithm design techniques
v Methods for specifying the algorithm
v Proving an algorithms correctness
v Analyzing an algorithm
v 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
v Time efficiency: indicates how fast the algorithm runs
v 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
v Sorting
v Searching
v String processing
v Graph problems
v Combinatorial problems
v Geometric problems
v Numerical problems
12. What are the classical geometric problems?
The two classic geometric problems are
v The closest pair problem: given n points in a plane find the closest pair among them
v 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
v Measuring the input’s size
v Units for measuring running time
v Orders of growth
v 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 of a program implementing the algorithm?
The running time T(n) is given by the following formula
T(n) ≈ copC(n)
cop is the time of execution of an algorithm’s basic operation on a particular computer and C(n) is the number of times this operation needs to be executed for the particular algorithm.
16. What are exponential growth functions?
The functions 2n 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?
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?
A function t(n) is said to be in O(g(n)), denoted by t(n) ɛ 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 n0 such that
T(n) ≤ cg(n) for all n ≥ n0
22. Define Ω-notation?
A function t(n) is said to be in Ω(g(n)), denoted by t(n) ɛ Ω(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 n0 such that
T(n) ≥ cg(n) for all n ≥ n0
23. Define Θ-notation?
A function t(n) is said to be in Θ(g(n)), denoted by t(n) ɛ Θ(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 & c2 and some nonnegative integer n0 such that c2g(n) ≤ t(n) ≤ c1g(n) for all n ≥ n0
24. Mention the useful property, which can be applied to the asymptotic notations and its use?
If t1(n) ɛ O(g1(n)) and t2(n) ɛ O(g2(n)) then t1(n)+t2(n) ɛ max {g1(n),g2(n)} this property is also true for Ω 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
v Constant : 1
v Logarithmic : log n
v Linear : n
v N-log-n : nlog n
v Quadratic : n2
v Cubic : n3
v Exponential : 2n
v Factorial : n!
16 Marks
1. Explain about the fundamentals of Algorithmic Problem solvingExplain about
• Understanding
• Ascertaining
• Choosing
• Deciding
• Designing
• Specifying
• Proving
• Analyzing
• Coding of an algorithm
2. Discuss the important problem types
Explain about
• Sorting
• Searching
• String Processing
• Graph Problems
• Combinatorial Problems
• Geometric Problems
• Numerical Problems
3. Explain Analysis framework with example
Explain about
• Measuring an input size
• Units for measuring running time
• Orders of growth
• Worst,Best and Average case efficiencies
• Recapitulation of the framework
4. Discuss the Asymptotic notations with efficiency classes and examples
Explain about
• Big-Oh notation
• Big-Theta notation
• Big-Omega notation
• Properties of notations
• Orders of growth
• Efficiency classes
16 Marks
1. Explain about the fundamentals of Algorithmic Problem solvingExplain about
• Understanding
• Ascertaining
• Choosing
• Deciding
• Designing
• Specifying
• Proving
• Analyzing
• Coding of an algorithm
2. Discuss the important problem types
Explain about
• Sorting
• Searching
• String Processing
• Graph Problems
• Combinatorial Problems
• Geometric Problems
• Numerical Problems
3. Explain Analysis framework with example
Explain about
• Measuring an input size
• Units for measuring running time
• Orders of growth
• Worst,Best and Average case efficiencies
• Recapitulation of the framework
4. Discuss the Asymptotic notations with efficiency classes and examples
Explain about
• Big-Oh notation
• Big-Theta notation
• Big-Omega notation
• Properties of notations
• Orders of growth
• Efficiency classes
0 comments:
Post a Comment