Algorithms: Question Set – 09
Write algorithm using the iterative function to fine sum of elements of array A.
Algorithm SUM(A, n) S := 0 for i=1 to n do S := S + A[i] return S
State the requirement in optimal storage problem in tapes.
Finding a permutation for the n programs so that when they are stored on the tape in this order the MRT is minimized. This problem fits the ordering paradigm.
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 smaller values of n.
Define dynamic programming.
When a solution to a problem is considered as the consequence of a series of decisions, dynamic programming can be utilised as a method for the creation of algorithms. This method has many applications. It is a method for resolving issues that have subproblems that overlap with one another.
What are the features of dynamic programming?
- Optimal solutions to subproblems are retained so as to avoid recomputing of their values.
- Decision sequences containing subsequences that are sub-optimal are not considered.
- It definitely gives the optimal solution always.
What are the drawbacks of dynamic programming?
- Time and space requirements are high since storage is needed for all levels.
- Optimality should be checked at all levels.
What is the order of growth?
Measuring the performance of an algorithm based on the input size n is called the order of growth
Why is the need of studying algorithms?
It is essential, from a pragmatic point of view, to be familiar with a standard collection of algorithms drawn from several subfields of computing, in addition to having the ability to build and evaluate algorithms’ respective efficiency. The study of algorithms is the foundational component of computer science from a conceptual and theoretical perspective.
What is the formula used in Euclid’s algorithm for finding the greatest common divisor of two numbers?
Euclid‘s algorithm is based on repeatedly applying the equality GCD(m, n) = GCD(n, m mod n) until m mod n is equal to 0, since GCD(m, 0) = m.
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:
- Euclid’s Algorithm
- Consecutive Integer Checking Algorithm
- Middle School Procedure
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