Jawaharlal Nehru Technological University Hyderabad B.Tech III ALGORITHM DESIGN AND ANALYSIS Previous Question Paper (February/March - 2022 - R18)

An efficient algorithm is characterized by its ability to solve a problem using minimal computational resources, specifically time and space. The key features include:

• Input/Output: It must have zero or more inputs and produce at least one output.
• Definiteness: Each step must be clear, unambiguous, and precise.
• Finiteness: The algorithm must terminate after a finite number of steps for any valid input.
• Effectiveness: Every instruction must be basic enough to be carried out exactly and in a finite amount of time.
• Generality: It should be applicable to a range of inputs rather than a single specific case.

For example, consider the Binary Search algorithm. Compared to a linear search, it is highly efficient for sorted arrays because it reduces the search space by half in each step, resulting in a time complexity of O(log n). This demonstrates efficiency by minimizing the number of comparisons required to locate an element.

The control abstraction for the Divide and Conquer strategy represents the general structure of the algorithm, where a problem is split into subproblems, solved recursively, and then combined.

Algorithm DAndC(P) { 
  if (Small(P)) return S(P); 
  else { 
    Divide P into smaller instances P1, P2, ..., Pk; 
    Apply DAndC to each subproblem; 
    return Combine(DAndC(P1), DAndC(P2), ..., DAndC(Pk)); 
  } 
}

In this abstraction, Small(P) checks if the problem size is small enough to be solved directly, S(P) provides the direct solution, and Combine merges the results of the recursive calls.