What is performance measurement?

The goal of performance measurement is to ascertain the amount of time and space that a specific algorithm requires.

Differentiate subset paradigm and ordering paradigm

• subset paradigm ordering paradigm At each level a judgement is taken regarding whether a certain input is in an optimal solution (producing sub-optimal solutions) (generating sub-optimal solutions)
• When dealing with issues that do not require the selection of the optimal subset, we reach conclusions using the greedy method by taking into account inputs in a certain sequence.

Write an algorithm using the Recursive function to find the sum of n numbers

Algorithm RECURSIVE_SUM (A, n)

if (n ≤ 0) then
    return 0
else 
    return RECURSIVE_SUM (A, n – 1) + A(n)
end

Write the general procedure of dynamic programming.

The process of developing an algorithm for dynamic programming can be broken down into a series of four parts.

• Characterize the structure of an optimal solution.
• Recursively define the value of the optimal solution.
• Compute the value of an optimal solution in the bottom-up fashion.
• Construct an optimal solution from the computed information.

what is class P and NP?

• P is set of all decision problems solvable by deterministic algorithms in polynomial time.
• NP is set of all decision problems solvable by non deterministic algorithms in polynomial time.

Differentiate decision problem and optimization problem

• The term decision problem refers to any problem for which the answer might be either zero or one.
• An optimization problem is any problem that requires determining an optimal (maximum or minimum) value for a given cost function. The term “optimization problem” can be used to refer to any such problem.

Write the difference between the Greedy method and Dynamic programming.

Greedy Method	Dynamic Programming
Only one sequence of decision is generated.	Many number of decisions are generated.
It does not guarantee to give an optimal solution always.	It definitely gives an optimal solution always.

Write any two characteristics of Greedy Algorithm?

• Construct the answer from the candidates given in order to solve a problem in the most effective manner possible.
• The progression of the algorithm results in the accumulation of two more sets. One of these sets contains the candidates that have been considered previously and selected, while the other set contains the candidates that have been considered previously but not selected.