Algorithms: Question Set – 05

Algorithms: Question Set – 05

Write an algorithm for straightforward maximum and minimum.

Algorithm MaxMin(a, n, max, min)
//set max to the maximum and min to the minimum of a[1:n]

max := min: = a[1];
for i = 2 to n do
    if (a[i] >max) then 
        max: = a[i];
    if (a[i] >min) then 
       min: = a[i];

Describe the recurrence relation for merge sort.

If the time for the merging operation is proportional to n, then the computing time of the merge sort is described by the recurrence relation:

T(n) = 2T(n/2) + n, n >1

T(n) = 0, otherwise

Explain the greedy method.

  • The greedy method is the most significant design methodology because it determines whatever option now appears to be in the best visual state.
  • It is necessary for us to have ‘n’ inputs before we can produce a subset that fulfils some requirements and may be considered a feasible solution.
  • The idea behind the greedy technique is that it is possible to design an algorithm that operates in phases, giving consideration to one input at a time.

Define feasible and optimal solutions.

  • If we are given n inputs and told to create a subset of those inputs in such a way that it satisfies the given requirements, we will have created what is known as a feasible solution.
  • The term optimal solution refers to a possible solution that either maximises or minimises the value of the specified objective function.

Define direct recursive and indirect recursive algorithms.

  • Recursion happens when the definition of an entity refers to the entity itself. When an entity refers to itself directly, this type of recursion is known as direct recursion.
  • When an entity refers to other entities that refer to it, this type of recursion is known as indirect recursion. When using direct recursion, a routine will call itself.
  • Indirect recursion can be seen in action through the use of mutually recursive procedures. A pointer to an instance of a data type is included within a (Directly) recursive data type.

What is the Greedy approach?

The method recommends constructing a solution through a sequence of steps, with each one expanding the partially constructed solution obtained up to this point, and continuing in this manner until a comprehensive solution is reached. At each stage, the choice that is made must meet the following criteria:

  • it must be feasible (that is, it must satisfy the constraints of the problem),
  • it must be locally optimal (that is, it must be the best choice locally available among all feasible choices at that stage)
  • it must be irrevocable (once made, it can’t be changed)

What is an algorithm?

A certain endeavour can be completed by adhering to a predetermined series of steps known as an algorithm. These steps are limited in number. In addition, all algorithms must satisfy the following criteria:

  • input
  • Output
  • Definiteness
  • Finiteness
  • Effectiveness.

write a general plan for analyzing non-recursive algorithms.

  • Decide on a parameter indicating an input’s size.
  • Identify the algorithm’s basic operation
  • Checking the number of times a basic operation is executed depends on the size of the input. if it depends on some additional property, then best, worst, and average cases need to be investigated
  • Set up a sum expressing the number of times the basic operation is executed. (establishing order of growth)